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

土下座しながら探索中

主に競技プログラミング

ICPC 2015 国内予選 参加記

ICPC2015国内予選にXXXとして参加した。(チーム名は大人の事情があるので伏せる)
チームメンバーは:自分、後輩S、後輩T
自分以外は今日初めて競技プログラミングをした、という謎のチーム


午前

二限に授業があったため13時に会場集合ということに、
授業が終わり弁当を購入し完食後会場へ


プラクティス

後輩にICPCについて説明しつつプラクティスする
オーダー計算と用語説明をする
まだ1問も問題を解いたことがないので、とりあえず2012年のA問題を解いてもらう
=> 「エラトステネスするだけじゃないんですか?オーダーも10^6なのでいけますよね?」と発言した次の瞬間に通してしまう
強い、出来が違うな

エナジードリンクを購入して飲む
昨日電気を付けたまま寝てしまったこともあり、頭が痛い

そろそろ開始なのだが、監督が寝ていて起こして良いのか謎
とりあえず、そっとしておく

開始1分前、監督起床&到着


本番

全員でA問題を読む
自分 : 全く理解できない
後輩 : こういうことです
自分 : ????
... 数分経過
自分 : 全く理解できない、けど書く
... 実装開始&終了
サンプルチェック => 全く合わない
自分 : ???? 理解不能、意味不明
後輩 : いや、こういうことです、こうすれば良いのです
自分 : ?????
... 数分経過
自分 : 非常に良くない、愚直で重いけど明かな実装に変更する
... 実装開始&終了
サンプルチェック => 全く合わない、さっきと同じ
自分 : ん゙あ゙あ゙あ゙
後輩 : いやー、こうじゃなくてこうです
自分 : ごめん
... 数分経過&実装いじる
サンプルチェック => 一致 やったか!?
自分 : 投げるしかない、良いよね?
後輩 : まぁ...

A問題 submit => AC

自分 : 非常に申し訳ない、次の問題読めてる?
後輩 : 読めてます、こういうことです
自分 : おっ、理解できる分かりやすい 書きます
... 実装開始&終了
サンプルチェック => 一致

B問題 submit => AC

自分 : 順位!見ずにはいられない!
自分&後輩 : あっ(察し

自分 : C読めてる?
後輩 : こういうことです
自分 : thx(読解力すごいなー)
自分 : 分かりやすい、書けます、書きます
... 実装開始&終了
サンプルチェック => 一致

C問題 submit => AC

自分 : 順位見ますか...

順位 => 5?位

自分 : いやー本当に申し訳、いやー本当に、いやー
後輩 : D読めてます、こんな感じです
自分 : なんとなくわかる、こういう場合どうなるの??
後輩 : こうなります
自分 : なるー DPっぽいね、DPかな 状態どうしよう
自分 : 動的計画法というものをしたい
自分 : これとこれとこんな情報を持てば状態確定できるんだけど、多すぎるなぁ どうしたら良いのだろうね?
後輩 : ... (考察中)
... 考察 & 途中で自分は後ろの問題を読んでいく
自分 : 小銭がそれぞれ何個あるかという情報がある以上状態持てなくない?あれ??
後輩 : それは入りません、総額さえ分かれば良いです
自分 : ふぁっ!?それが本当なら解けるんだけど??本当に???
後輩 : それは間違えないです
自分 : (本当に?)本当に?まぁ、それが本当なら書けるなぁ
自分 : 自分は理解できてないが、話聞きながら書いてみますか
... 実装中
自分 : あとは遷移だけなんだけど、どうなるの?
後輩 : まず、1 <= P[i] <= 500 の場合は絶対に購入します
自分 : はい、(書く)
後輩 : それ以外の場合は3つパターンがあって、1つめはこうです
自分 : はい、(書く)
後輩 : 2つめはこうです
自分 : はい、(書く)
後輩 : 最後にこうです
自分 : はい、(書く)
自分 : じゃあ、できたのか?試してみるか
サンプルチェック => 1つ間違ってる
自分 : 両方0になってるケースがあるなぁ
後輩 : ちょっと待ってください... ( コードを読む )
後輩 : えーっと、ここはこうですね
自分 : ほむほむ... ( 修正 )
サンプルチェック => 変わらず間違ってる
自分 : うん?
後輩 : あれ、、
... プリントデバッグ開始
自分 : あれ、250なんて入力になくない? あっ(察し
自分 : ごめん、入力ファイル間違ってた
サンプルチェック => 別のところで間違い発生
自分 : んんー
後輩 : うんー、、
自分 : さっきとどう違うんだっけ? ここか? ここか?
自分 : あっ、この if 文消すとサンプル一致した!!どういうことだ?
後輩 : いや、その条件文は間違ってますよね、要りませんよ
自分 : ふぁ!?あ、そういうえば、あ、ごめん==じゃなくて!=だったね、書き間違えてた、ごめん
自分 : とりあえず、投げるしかないか(小銭周り理解できてないし、通るのか??)

D問題 submit => AC!!!!!

自分&後輩 : ヨッシャ!!!!!!
自分 : どうなった!?スタンディングどうだ!???

順位 => 2X位

自分 : きた!!!これは!!残り30分ないし、そうそう増えるわけがない!!
後輩 : 良かった、次どうしますか
後輩 : 小銭理解できてないなら説明しますか、それとも次の問題いきますか?
自分 : そうだね、まぁ、次の問題いくか グラフっぽい問題考えてみよう
自分 : こっちは自分読んだから、説明しよう
... 説明
自分 : というわけなんだけど、まぁ、もし会社が関係なければただのMSTで、
自分 : Kruskal法というもので解けるんだけど、
... Kruskal法の説明
自分 : こんな感じのアルゴリズム、わかった?
後輩 : なるほど、分かりました
自分 : で、これ会社のうちどちらかは最小で繋いだほうがよくない?
自分 : つまり、両方の会社とも最小でないような繋ぎ方って答えになりえなくない?
後輩 : どうなんでしょう...
自分 : 時間ないし、書いてみるか
後輩 : そうですね、どうせ間違っても今更影響はないですし
... 実装
自分 : あ、なんというか、どちらか片方を貪欲にするせいで-1になるケースありそう
後輩 : ありそうですね
自分 : あ、ごめん無理だ、後3分もない DPでもするのかぁ??
後輩 : うーん

      • コンテスト終了 ---

という流れでした
今日初めて競技プログラミングをした後輩のほうが自分より強かった件
予選突破してました
無事参加できそうです