hotpepsiの練習帳

SRM 570

13:42

Div1 Easy (250) RobotHerb

問題

• ロボットがXY平面上を移動する
• 命令が数値の配列で与えられる
• 各命令では数値nだけ直進し、n回90度右回転する
• 命令列全体をT回実行後、スタート地点からのマンハッタン距離を求める

方針

• サンプル読んで、シーケンスa全体をT回繰り返すことを確認
• 実行後の向きは4通り
• aの実行後、向きが最初と同じなら、距離が単純に増加していく
• そうでない場合は次の実行でもまた角度が変わる
• よく考えたら4通りどのパターンでも、4回実行したら元の角度に戻る
• 4回愚直にaを実行して、結果の距離をT/4倍してから、T%4回実行すればよい
• 提出
• Passed System Test
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_570/RobotHerb.cpp

Div2 Hard (1000) CentaurCompanyDiv2

問題

• 株式会社ケンタウロスにはN台のサーバがある
• 会社を株式会社人間と株式会社馬に分割することにした
• 各サーバは木構造で接続されている
• 各サーバはそれぞれのどちらかに所属する
• 分割後、元々接続されていなかったサーバはケーブルが必要になる
• 馬は十分なケーブルを持っているが人間は持っていない
• 人間側がケーブルを必要とする分割はできない
• 有効な分割が何通りか求める

方針

• 木DPらしい
• なんと弟子がスライドを書いてくれた。わかりやすい!
• https://github.com/atkanon/TopCoder/raw/master/SRM570/srm570div2hard.pdf
• 大まかな手順としては、あるノードを親ノードPとして、P以下だけが選択された場合の数Kを求める
• DFSで子ノードCを親ノードとした場合の数Xを求める
• その子ノードを使わない選択肢もあるので、その子ノードについてX+1通り
• 全ての子ノードについて、あり得るパターンは掛け算なので、X+1の積を取る
• Kを記憶しておく
• Kの総和に、全てのノードを選択しなかった場合(全部馬)の1を加えたものが答え
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_570/CentaurCompanyDiv2.cpp

結果

o-- 198.96pt 246th/740 rating 1364 -> 1449 (+85)

div1 mediumが難しかったためeasyの速解き回。順位はとても良かった。久しぶりの1400台。

easyはアフィン変換でも解けるようなので試してみた。繰り返し二乗法で短縮可能。

div2 hardは問題文が面白い。馬って何だろうと考えてしまった。accumulateの初期値に0と書いたら戻り値がintになってしまいはまった。初心者すぎる。