hotpepsiの練習帳

SRM 541

00:23

Div1 Easy (250) AntsMeet

問題

• 直交座標系に蟻が何匹かいる。
• 蟻は縦または横に移動していて、全ての蟻の速度は同じである。
• 蟻同士が出会うと、その場で消滅する。
• 蟻の座標と向きが与えられる。
• 最終的に残る蟻の数を求める。

方針

• シミュレーションしてみる
• 割とすぐ書けたが、実行したら10秒くらいかかった
• 高速化のため、ぶつかる時間を求めてみる
• ある蟻Aと蟻Bの組を考えてみると、それがぶつかるチャンスは1度しかない
• 蟻がぶつかる可能性がある時刻は高々2500個なので、記憶しておく
• 時刻順にシミュレーションし、生き残っていればぶつかる
• お互いに向かってくると位置が0.5単位になるので2倍しておく
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_541/AntsMeet.cpp

Div2 Easy (250) AkariDaisukiDiv2

問題

• 以下のような形式に文字列を分解するあかり関数f(X)を考える。
• 「わーい ○○ あかり ○○ 大好き」
• ここで「わーい」「○○」「あかり」「大好き」は、それぞれ1文字以上の文字列である。
• 「○○」には同じ文字列が入る。
• 与えられた文字列に対して、あかり関数を満たすのは何通りか求める。

方針

• 総当り
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_541/AkariDaisukiDiv2.cpp

結果

o-- 92.77 446th rating 1377 -> 1420

easyを4回連続で落としていたので、そろそろ通さなければと思っていた。シミュレーションしたら全く間に合わなかったので書き直したらバグがずっと取れずに70分かかった。しかしプラス点なのは非常に良かった。2倍していない人がばたばた落ちていたけど、解くのに精一杯で気がつかなかった。

赤い人のコードがシミュレーションだったので手元で試してみたら、VC++の/O2だと間に合わないが、/Oxだと一瞬で終わって衝撃を受けた。といっても最初に書いたコードはいちいちstd::mapに突っ込んで判定していたので、どの道間に合わないものではあった。

div1は撃墜祭りだったが、div2も正答率があまり良くなかったようだ。TopCoderの参加者は計算問題とかが得意で、泥臭い文字列処理は苦手な印象。

div2easyとdiv1mediumは問題文が面白すぎ。