hotpepsiの練習帳

SRM 528 Div1

20:20

Easy (250) Cut

問題

• Fox Cielは年末の記念に蒲焼を食べることにした。
• 長さ10にカットされたうなぎだけを蒲焼にすることができる。
• maxCuts回だけカットできるとき、蒲焼の最大数を求める。

方針

• 10で割り切れるやつを最初に
• 切断したあと10残ったら結果+1
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_528/Cut.cpp

Div2 Hard (1000) Mosquitoes

問題

• 位置と速度が異なる蚊がN匹いる。
• 半径Rで炸裂する爆弾があるとき、殺せる蚊の最大匹数を求める。

方針

• 条件が変化するとき＝2匹の蚊の距離がちょうど2Rの前後
• 全ての2匹の組み合わせで全探索
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_528/Mosquitoes.cpp

結果

x-- -25pt rating 1231 -> 1093

うなぎに当たった。もうちょっと丁寧にやろう。

SRM 527 Div1

20:28

Easy (275) P8XGraphBuilder

問題

• N個のノード(node)をN-1本の辺(edge)でつないだグラフを作る。
• グラフは連結グラフである。すなわち、任意の2つのノードは辺により接続されている。
• あるノードから別のノードで出ている辺の本数を次数(degree)とする。
• 次数毎のスコアの配列が与えられる。
• グラフのスコアは、各ノードの次数に応じたスコアの和である。
• 最大スコアを求めよ。
• なお次数のスコア表のサイズ+1がノード総数である。

方針

• 連結グラフでN-1本しか使えないので、木になる(閉路はない)
• 構成可能な木の組み合わせのうち、最大スコアを求める問題
• ある個数Xのノードを使った全ての木の組み合わせが試せればよい
• 本番では木の下に複数の木がある組み合わせができなくて爆死
• kinabaさんのを見て、葉+木のパターンだけ試せばよい理由がわからなかったので図を描いた
  
• 図のAとDを交換しても、次数の組み合わせは変化しない
• 図でいうと右下の部分は必ず葉
• 「部分木が最も右側以外にある場合、右下の葉と交換」という操作を繰り返すと、任意の木が、根+(葉+木(葉+木(葉+木...)))という形に変形できる
• やっとできた...
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_527/P8XGraphBuilder.cpp

Div2 Hard (950)

問題

• 貨幣価値が2の累乗になっているN種類の硬貨がある。
• ちょうどcoins_count枚の硬貨で、合計をcoins_sumをにしたい。
• 辞書順最小の組み合わせを求める。

方針

• この問題での辞書順最小の定義は、最も貨幣価値の低い貨幣を最小にすることである
• 最低価値の貨幣だけの状態からスタートして、coins_countを超えている場合には、貪欲にひとつ上の貨幣に交換していく
• 最後の交換の結果、coins_countと一致していなければ失敗
• 証明はAnalysisを読んだ
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_527/P8XCoinChangeAnother.cpp

結果

x-- 0.0pt 511st rating 1243 -> 1231

とりあえずeasyだけ通すのが目標だったのだが2回目でdiv1の壁に当たった。

ストーリーなしでいきなりグラフかよ!とちょっとだけ思った。まあ今回はストーリーつけづらい感じではあった。

Codeforces 98 Div2

02:42

A. Postcards and photos

問題

• 2種類の文字からなる文字列を受け取る
• 先頭から、連続する同じ種類かつ5文字以内の文字列を除去する
• 最小手数を求める

方針

• すごく短く書けそうだが...
• ベタに書いた
• 同じかつ5文字ならflush、違う文字ならflush、ループ終了後flush

B. Permutation

問題

• 不完全な数列が与えられる
• 1からnまで1ずつ単調増加する数列に直す最小手数を求める

方針

• 最大5000しかないのでフラグで持ってしまってよい

for (i = 0; i < n; ++i) {
	f[x[i]] = 1;
}
int ans = n;
for (i = 1; i <= n; ++i) {
	ans -= f[i];
}

C. History

問題

• 区間(開始年,終了年の組)の配列が与えられる
• ある区間が別の区間に含まれている総数を求める

方針

• std::pairで格納
• 開始年でソート
• ある区間iと、その次の区間jのみを見ればよい
• 区間iの終了年より区間jの終了年が手前ならカウント+1
• そうでなければiにjを代入
• 区間jの開始年は区間iの開始年よりあとなので、終了年の判定だけでよい
• 区間iより区間jの終了年がうしろならば、それよりあとの区間は区間iを判定に使わなくて良い

sort(x.begin(), x.end());
for (i = 0; i < (n-1); i = j) {
	for (j = i + 1; j < n; ++j) {
		if (x[j].second >= x[i].second) {
			break;
		}
		++ans;
	}
}

結果

oox-- 406+674=1080pt 586th rating 1568 -> 1493

CがTLE。複雑な木で持たないといけないかと思ったが、場合わけしてみると結果的にはすごく単純で良かった。

素直に書くのがなかなか難しい。

Codeforces 97 Div2

17:28

登録だけはしていたが初参加。

A Presents

問題

• プレゼントを渡す先が配列で与えられる
• 誰からもらったかの配列に変換して返す

方針

• 特にひねりなし

B Ternary Logic

問題

• 3進数のXOR
• A XOR B = CにおいてAとCからBを求める

方針

• 1桁の中で引き算すればよい
• 「複数の解があれば」とあるが、一意なので存在しないはず

C Replacement

問題

• 1以上の整数からなる配列が与えられる
• そのうちの1つだけ変更したもののうちの最小のものを求める
• 必ず1つだけ変更すること
• 違う数値に変更しなければならない

方針

• 最大の数を1に変更する
• しかし1しか含んでいない場合は、末尾を2に変更する
• 0-based indexで先頭に1を入れておく
• 1-based indexでもらったものをソートして入れて、末尾を消す
• 全部1の場合だけ特別扱い

D Rectangle and Square

問題

• 8つの点が与えられる
• 4点で正方形、残りの4点で長方形(または正方形)ができるかどうかを求める

方針

• 本番中は任意の2点から辺を作って判定
• system test failedのため解きなおし
• next_combinationで4点を選ぶ
  (next_permutationでも40320回なので、TLEしないかも)
• 判定回数は8C4=70回
• 4点の重心(中央)から4点までの距離が全て等しければ長方形(または正方形)
• 両4点が長方形のとき、最初のものが正方形ならOK
• 正方形かどうかは、任意の2点と残りの2点が交差するかどうかで判定
  これにもnext_permutaion使った。

結果

ooox- 2642pt 380th ratings 1568

pretestは親切設計。Cの全部1のときはpretestがなかったら気がつかなかった。

Dはnext_permutationでも十分間に合うと計算すべきだった。

next_combinationはじめて使った。楽ちん。

後半にいくほど問題文のストーリー性がなくなっていくのが面白い。

SRM 526 Div1

00:45

Easy (250) DucksAlignment

問題

• 升目状の盤面にアヒルが何匹かいる
• 位置はばらばらで、列または行に最大でも1匹しかいない
• 水平または垂直に、連続するように並べたい
• 最小の手数を求める

方針

• 全体としては、水平と垂直それぞれで最小手数を求めて、少ないほうを答える
• 盤面を90度回転させて水平判定を呼べば、水平に並べる関数だけでもいける
• なので水平に並べることだけを考える
• マンハッタン距離なので、垂直方向と水平方向の移動は完全に別で考えてよい
• まずY座標をそろえることを考える
• 全試行して通したが、平均値求めればいいだけだった。ただし小数点の扱いはバグりそう
• 次にX座標
• こちらは単純な平均値ではないので全試行。位置を加算したやつで平均とればよさそうだったが落ち着いて書けそうになかったのでやめた

実装

• 書き直した
• 水平と垂直を独立した配列に保持してソートしておく
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_526/DucksAlignment.cpp

Div2 Hard (1000) SumOfLuckiness

問題

• ある数の10進数表記での4と7の個数の差の絶対値を、その数の幸運値とする。
• AからBまでの数の幸運値の総和を求める。

方針

• 3桁単位で足す (ださい)
• ほんとは4と7の個数についてDPすればよいっぽい
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_526/SumOfLuckiness.cpp

結果

o-- 103.10 347th 1227 -> 1243

途中まで壮大に無駄なコードを書いたりしていてとても遅かった。

なんとかdiv1には残れた。

easyは(div2だけど)SRM 509から16連続通っている。これを続けるのとmedium解きたい。