TopCoder SRM541
writer やってました。
Div2 Easy(250) AkariDaisukiDiv2
f(X) = Waai + X + Akari + X + Daisuki なる string -> string の関数を考える時、S = f(X) なる (Waai, Akari, Daisuki, X) の組の数を求めよ。
問題名とかいろいろおかしいですが(ivan さんに「"Waai" "Akari" "Daisuki" って何？」って聞かれました)、2箇所の X の位置を決め打ちして比較するだけで解けます。
Div1 Easy(250) / Div2 Medium(500) AntsMeet
蟻がいて動いている。ぶつかったら消える。もはやぶつからなくなったときの蟻の数を求めよ。
最初は x, y の上限が10億で、それだとオーバーフローして悪質なので1億になりましたが、それだとこの問題セットでは難しすぎるので上限を 1000 として、0.5秒ごとに進めて試すだけで解けるようになりました。
しかし、1 秒ごとで試している人が非常に多く、想像以上の challenge ゲーになってしまいました。ちなみに、Example 2 を見ると 0.5 秒ごとで考えないといけないことがわかります。
Div1 Medium(550) AkariDaisukiDiv1
Div2Easy と同様に f(X) を定める。Waai, Akari, Daisuki は与えられる。f^k(S) = f(f(…f(S)…)) (fはk回) の中に、部分文字列として F は何回現れるか求めよ。
難しいとは思いませんでしたが、非常に tricky らしいので 550 になりました。
tricky なのでテストケースをかなり親切にしました。そうしたら正答率がけっこう高くなりました。Correct % は Easy のほうが低いです。これなら 500 でもよかったかもしれません。
まず操作をして S を F より長くします。すると、部分文字列を考えるべきパターンが Waai--S, S--Akari--S, S--Daisuki だけになります。これは、S の左/右 |F|-1 文字を覚えておくとやりやすいです。
これをやると漸化式のような形になります。 k が 1000万 もあるので、最後まで試すわけにはいきませんが 50 くらいからはもはや漸化式の定数部分が変化しなくなるので、そこから先は適当にやると解けます。
Div2 Hard(1000) NonXorLife
ライフゲームのようなことをする。1 秒ごとに、各マスについて、「そのマスおよび周囲4マスのうち、少なくとも1マスでも生きているなら次生きる」というルールで状態を変化させる。 K 秒後に生きているマスの数を求めよ。
K が 1500 しかないので、K^2 くらいのメモリを確保しても足ります。累積和のようなことをしたり、DP のようなことをしたりすると解けます。
Div1 Hard(1000) XorLife
Div2Hard とほとんど同じだが、ルールが「そのマスおよび周囲4マスのうち、奇数マスが生きているなら次生きて、さもなくば次死ぬ」に変わる。
問題名の通り、ルールは「排他的論理和」です。(これがネタバレだったという説もありますが、ルール見れば少なくとも操作が xor であることは自明なはずです) このルールにはよい性質があり、2 秒後の状態は「自マスと、そこから上下左右に 2 マス離れたマス」にのみ依存します。
これを使うと、2n 秒後の状態を求めたいときは、盤面を mod 2 で座標が一致するもの同士で分けてしまい、n 秒後の状態を求めることで対処できるようになります。
奇数秒の場合でも、1 秒進めてやると偶数になるので、同じことができます。
これをそのまま使うだけだと何もうれしくないですが、これをやると盤面がどんどん小さくなり、途中から高々 3*3 にしかならなくなるので、(盤面, 秒数) でメモ化すると解けます。(秒数も、log K 個くらいしか考えなくてよいです)
実装は難しくなく、この方針なら多分適当にやっても（例えば、map に vector
この問題を最初に出した時は、盤面が8*8で、「生存マスが M を超える最小の時間を求めよ」という問題でしたが、上の問題でも十分に難しいと言われたのでこっちになりました。結局 1 人しか通していないので、やっぱり十分難しかったようです。
