読者です 読者をやめる 読者になる 読者になる

AOJ JOI 2008

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

0532 Time Card

秒に合わせて計算する。

0533 Contest

ソートすると楽になれる

0534 Chain

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

0535 Crossing Black Ice

DFSで解けます

0536 Shuffle

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

0537 Bingo

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

0538 IOIOI

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

0539 Pizza

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

0540 Amidakuji

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

0541 Sanpo

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

0542 Authentication Level

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

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