AOJ JOI 2008 - シュレーディンガーの(ry 揉んでみるまで柔らかいかどうかは分からない

今日は予選4問、本選1問解けました。予選はなんとか通れそうですが本選がやっぱりたいへんです。部分点は解ける感じなんですけど満点解法がやっぱり難しい

秒に合わせて計算する。

ソートすると楽になれる

実装ミスってRuntime errorの原因が判明するのに糞時間掛かった。全通り試す。

DFSで解けます

解けなかったです。普通にやると制約大きすぎてどうにもならない。n枚目からm枚目って二つの要素つくってってシャッフルする。アイデアまでは思いついたけど、実装が分からなかった。前から何枚とか三つの配列に分けてやればいいのかな。

DPらしいです。AOJだとTLEになり、通らないことが多い。解説の意味が分からない。部分和問題の解の組み合わせ数。

解けてない。一個飛ばしでIの数とOの数を数えてO(m)とか。KMP法とかでも解けるらしい。

にぶたん。初めて二分探索の問題を解いた。

解けてない。横棒を一本ずつ隠して線をたどってくと、O(mk)で解けない。線を一本隠すと二本の縦棒の点数が入れ替わる。全ての横棒で右左それぞれどの番号、点数につながってるかメモる。あとはそこを入れ替えてく。O(m)で完成

解けてない。DPで解けるらしい。N-1回目までの散歩で各交差点を通る回数が分かると南か東か分かる

Rの上限が一万なのでそれぞれのグリッド毎にlevel[10001]という配列をもち、r部屋行くために必要レベルをlevel[r]に入れる。プライオリティーキューを使うといい

やっぱり2008年からはレベルが高くなるってのはほんとだったようですね。難しい