FLYING

〈全日本・紀文豆乳飲料シリーズ「麦芽コーヒー」の500ミリリットルパックを扱う小売店が少ないことに遺憾の意を表明する会〉活動記録

情オリ本選 問1-4

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

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

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

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

20080219 Update

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

20080220 Update

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

20080220 Update

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