国内予選

金曜はICPC国内予選にLittleBug(私とyosとviewlagoon)で出ていました.

前日

yosを下宿に召喚し,模擬国内予選で練習していました.ライブラリとかの確認しつつ,Aから解いていきます.

A

えーしー.

B

これはBFSじゃない,DFSだ!! 何やっていたんだろう.

C

はいはいDP.


このあたりで飽きてanybeatを遊び始め,yosはちゃんと家に帰り,略

準備

会場は3限目*1は別の授業をしているようだったので,自習室に逃げこみ,持っているコピーカードが残高10円であることを確認しつつ,新しいコピーカードを購入しつつ待ちました.iwiwi氏(大学のiMacが重いとか言ってなにやら難しい設定をしていた)とhos氏がいましたが,私は,1年間全く使っていなかったため家のと設定がかけ離れた.vimrcや.zshrcを移していました.そもそもTerminalがbashを起動する設定でしたし.

4限目になったので移動し準備の続き.Google Code Jamの自分の提出コードからライブラリを取ってきたり,nya3のチェックリストを取ってきたりしたものを1枚の紙にまとめて印刷しました.印刷の練習もこれで完了.あまりの残高10円のカードもちょうど消費.hos先生にライブラリを撃墜されたりしたので修正しました.INF=1001001001は既出だったらしい.こんな時間にライブラリを印刷しているのは「泥縄」*2でした.印刷を私以外でもできるよう,大学のアカウントを簡単なものに一時的に変更*3.あとは,チームメイトに電話したり,ファイルを退避したり,チームメイトにもう一度電話したり,家に「プログラミングコンテストチャレンジブック」*4を取りに帰りつつ着替えたりしていました.

A

かんたん.

B

かんたん.


ここで本郷で試験を30分で早退し,駒場に駆けつけていたyosが到着.

C

問題の読解に時間がかかったもののまあOKでした.ここまでは良かった,はず,そう信じたい.

E

なぜかDを難しいものとスルーし,すぐにDPが見えたEを書きました.

  • スライド和で混乱する
  • DP(メモ再帰)で再帰呼び出ししたあと片方しかmaxの更新処理をしていない

などにより時間がかかりました.


この時点で大学内順位がかなり厳しい状態になっていた気がします.

D

全探索でいいじゃん.ということで書きました.円の個数が24個なので,ビットで管理すればいいのですが,

if(flags&(1<<i)==0)

という凡ミスではまり,他にもいろいろあって,通したときには残り1時間.

F

幾何なのでyosに丸投げ.結局yosはある程度の時間で紙の上では解けていたようなので試験としての判断ミス.

G

viewが良い考察をしていて,その前処理のあと適当にやればできるという私の勘違いが通り,「わかんないけど実装してみよう」という愚かな判断のもと行動していました(このときyosはずっとFを解いていましたが,この時点でGのアルゴリズムの検証を頼むべきだったと思われます).ちょっとずつデバッグ出力をしながら書いていったり,マスの間の壁は座標を2倍したら扱いやすいとかいう方法を用いたりして,【Gにしては】順調に書きあがり(とはいえ,座標ミス他をviewに指摘されたり,今考えれば,疲れていたことが分かります),検証.


サンプルケースのうち1ケースだけ答えが違う…….しかも,最小32枚で可能が正解のはずが30枚で可能と間違えている,といういかにもアルゴリズムの間違いであるような結果が出てきました.ここらへんでyosを呼びアルゴリズムを説明したりしていましたが,yosも誤りを指摘できず.やけくそで提出を試みるも,Gの1番目の入力データの上の方がサンプルそのままの様子.とりあえず提出→当然WAとかいう無駄な時間を使いつつ終了.


答えを小さい方に間違えるはずがない,というところが誤りの本質で,うん,もうどうでもいいですよ.情報教育棟を出る頃におそらく正しいアルゴリズムに気づきました*5

山手

やけ食い……したかったけれど,そんなに食欲ありませんでしたよ.

*1:特性類の授業があったような…

*2:コーチ兼監督者のお言葉

*3:これがバレると大学に処分を受けるのではないか?

*4:少し前にようやく買ったのにまったく読んでいませんでした.お守り的役割

*5:でっていう