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

kyos1704活動記

適当に考えたことや調べたことを垂れ流すものです。質問等ありましたらtwitter:@kyos1704 に質問してください。

ICPC 2013 国内予選 kyos1704@(++c)-- 参加記

ICPC国内予選に参加しました
紺青氏(@konjo_p) と Aさん(仮名)と参加しました

結果:3問解いて61位でした。
感想:戦犯です!ゆるしてください!!!

準備編

紺青氏とAさんと話し合って週二回ぐらいなら練習できるんじゃねという感じになる

毎回数問問題を解く

環境になれるために私のパソコンを使った

AさんがA担当
紺青氏がB
私がC担当ということにする

解いてるうちに、CよりDのほうが行けるんじゃねという話になったけど
C解けないのはあれなので練習はCを解く

結局AOJの日本語で追加されてる問題の
AさんはAを全部
紺青氏はBを全部解けた

私は解けてない(だめじゃん

本番

以下 ここを参考に書いています (@not_522 さんありがとうございます)
https://docs.google.com/spreadsheet/ccc?key=0Ao_ilfIsS8SodFliUTUyT3REYmJ1ZjBTOTJLWXE5Q0E#gid=0

開始

とりあえず問題印刷してる間AさんがAを読む(横から覗きこんでたけどよくわからない

印刷した問題が届いたので、私はincludeとかのあたりのライブラリを打ち込んでいく。

ついでにわかってることをAさんに読みあげてもらう。割と簡単そう。

A実装はAさんにまるなげする予定だったので、
input部分とか書いて欲しい関数とかを横から口突っ込みながら
私はC,Dを読む。

C意味がわからないぞ・・・・?

Dがおもいっきり素数なので素数ライブラリを用意しておく(ページめくっただけ

この段階でAさんちょっと詰まっているのでお話する。

比較関数が必要なことと、150*150ぐらいなら全部ぶん回せばいいことの了承を得る

書いたのでサンプル通す

バグってる

比較関数のなかでなんでかグローバル変数(入力)と比較してたので修正

A Accepted!!! (1732秒=28分)

すぐに紺青氏と交代する

C意味がわからないのでAさんに全部まるなげする。
設定意味分からないだけっぽい匂いがするので
サンプルインプットとアウトプットがどうなってるか説明できるようにしてくれと頼む

私はDを見る
素数テーブルとマップ生成さえ出来れば深さ優先探索するだけっぽいと思う(真っ赤な嘘

紺青氏とAさんに A->B->D->Cで4完行けそうですとプレッシャーを掛ける(思えばここがフラグ

とりあえずDのマップ生成の法則を考える

向きを変えながら二回変わったら進む数増やすだけだなこれとか思って簡単そうと思う

余裕っぽいのでCの説明を受ける。設定めんどくさい・・・・

設定めんどくさいけどソートして足すだけっぽいねというふうな合意ができる

Bがバグったので交代

Dのために素数ライブラリをカタカタする

マップ生成のコードを書いている途中でBのデバッグ思いついたらしく

私がBのコードを変更する(席変わるより楽という主張により)

B: Accepted!!!! (4546秒=75分)

想定よりものすごく早かったので興奮した

Dのコーディングに入る

Aさんと紺青氏はCの解読をする

とりあえずDのマップ生成と深さ優先探索らしきコードが出来上がる

D:サンプルを通す→時間かかりすぎてヤバイ

えっ???って思ったけど余裕でO(n!)だったので間に合うわけ無いと思った
別に普通にメモ化すれば良いだけだったので(良かった!!!!!)
再帰をちょっと変更する

あとから指摘受けたけど O(3^n)っぽい、計算量の見積もりできなさすぎてヤバイ

D:もっかいサンプル通す→通らない

通らないのわけがわからない(原因も思いつかなかった)
のでCの説明を受ける。

よくわからんけど書いてる図は木だよねと言う→了承を得る
お互いどうすればいいかわからないので構造体か何か作ってそこにぶち込むということで了承する

話をしている間にそもそもマップのチェックしてないことに思い当たる

D:マップのチェック 1 2がない

よくわからんけどマップ生成がバグっているらしいのでよく見る
Cが書ける状態なら交代したけどそうじゃないっぽいので実機上(良くなかった

この状態で残り時間が1時間切ったので焦り始める
C書く暇ないかもしれないと紺青氏とAさんに伝える

実装時間を大雑把に見積もってもらう
30分ぐらいで行けそうらしい

D:マップ生成のバグ発見→訂正→サンプル通らない

残り時間40分弱
Dのバグは不明

紺青氏とAさんに相談する
そもそもD誤読してる可能性もあるし
Cは実装詰まってないけど書ける部分はあるので
そこを書いてる間に詰まってないところ考えることにする

C:実装開始

タイピングのスピードは私が早いのでコーダーは私がすることになった
言われるがままにクラスを書いて、
どう実装するかわかってないところ以外を書き上げる

書き上がった時点で
まだ未実装の部分についてどうすればいいかはっきりしていなかったので
どんな機能が必要なのか聞く

行けそうなのでそのまま書くと主張する
時間もないのでそれしかないということで賭けに出る(構文解析部分です:ちなみに練習で一回だけした)

思ったよりすんなりかけた

C:サンプル通す→通らない

ちっちゃいバグがあった 修正

C:サンプル通った

残り時間とか気にしてる余裕は無いのでとりあえずデータ落としてサブミット

C:Accepted!!! (10028秒=167分)

うおおおおおおおおおおおおおおおおおおおおお
とおったああああああああああああああああ

ハイタッチ(成功)する!!!

とりあえず目標は達成したので喜ぶ(3完が最低ラインとか話してた)

Dが通るかもしれないのでバグを必死に探す
見つからない・・・・・

timeup

ちゃんとした感想

3完が最低ラインで4完したいですねって話をしていたので、
最低ラインは突破できた

4完という目標を阻んだのは私なので戦犯っぽい
(バグッたと思ってたけど普通に出力するものを勘違いしていた可能性)

そもそもD書き上がった時点で提出できてたら
アジア予選選出28チーム枠には入れていたし
20チーム枠にギリギリ入れていたかもしれなかったので
それはとても悔しい
(climpetさんたちのチーム(// ato de namae wo kangaeru)がヤバイ成績をとっていたので2チーム出られたかもしれなかった・・・

D書き上がった時点で二時間たってなかったんだけどなぁ・・・・


ということで、上を見ると悔しい思いが大きい大会になりました
Aさんも紺青氏も私もしっかり働いて、チームとして動けたのでそれはとても良かったです

そもそも大会前に私が問題解けてないし準備段階からだめっぽいですね・・・・

来年はclimpetさんたちのチームと私達のチーム両方でアジア予選に出られるように頑張っておきたいと思います