情オリ本選 問1-4

コードを書いて理解しなければ、セミナーに行った意味がない！

• joi2008.zip

という訳で、情報オリンピック本選・問1-4の暫定回答（にわかC++版）を恐れを知らずにうｐしてみる。会場にUSBメモリを持って行くのを忘れたから、ソースは帰ってからぐだぐだと書き直したもの。もちろん、とてもじゃないが読めたもんじゃない。

問題用紙に載っているインプットは試したが、他のインプットが正しく通るかどうかは不明。また、サイズの大きい問題が時間内に解けるかどうかも不明。残る問題は問5だけだが、セミナーの解説で言ってた座標圧縮とかのキーワードを理解できてないから放置するかも。

ちなみに、使ったアルゴリズムについてはこっちを、予選の方の回答についてはあっちを参照してほしい。

20080219 Update

公開された問題セットを実行してみたところ、問1,2,4に間違いを発見('A`) 今からバグ取りしてくる。

20080220 Update

バグ取り完了。vectorで適当に確保していたメモリをnewで確保するよう書き換えたから、きっと時間制限もクリアしてくれるはず。Linuxの環境だと問2の問題セットの出力とコードの出力が一致しないが、たぶん改行コードの違いに起因するものなので修正なし。

20080220 Update

最適化レベルをO2にすれば、vectorも普通の配列と同じくらいのスピードでアクセスできるらしいことが分かった。つまり、vectorは悪くなかった！ これからはスピードを気にせずにvectorを使いまくってやるぜ！ ただし、テンポラリバッファの代替としてだけど。