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

土下座しながら探索中

主に競技プログラミング

ACM-ICPC 2016 国内予選 参加記

最後の国内予選なので参加記を残そうかと
チームは私と後輩Sと後輩Tです。(イニシャルだけだと去年と同じだけど後輩Tは去年とは別の人
[追記]後輩Tではなく後輩Mでした、後輩Mさんごめんなさい 

リハーサル

後輩Sは2,3限に授業があるため不参加
後輩Mとともに会場準備とプリンタの設定を行う
お菓子とMAXコーヒーとレッドブルとT島屋で買った100g1670円のブルーマウンテンを挽いていれたコーヒーを飲む
自己紹介を書いたりする
TwitterのTLを眺めながら後輩らの精神状況が不安定であることを確認する
コンテスト中のチームの動きを確認する
コンテスト開始を待つ

コンテスト

A問題

ソートするだけっぽい
絶対AでWAを出したくないので後輩Sに「本当にそれだけ?」とn回確認した
「条件どうこういってたけど、それはなんだったの?」「本当にそれだけ??」「えっ」
コードを書く、サンプルは通る
まぁ投げてみる => AC
良い感じ
1完

B問題

後輩Mから概要を聞く
全探索で良いみたい
書く=>サンプルが合わない
バグとりを二人でする
入力に現れる立候補者の他に1名立候補者を入れる必要があることが発覚
入れる、それに合わせてループを修正
サンプルは通る
まぁ投げてみる => AC
ちょっとつまったけど良い感じ
2完

C問題

後輩Sから概要を聞く
「エラトステネスの篩です、以上」
この説明から概要がつかめなかったで問題文に目を通す
なるほど、エラトステネスの篩っぽいものを書けば良いようだ
書く=>無限ループ
悲しい気持ちになりつつもデバッグ
無限ループは止まった
でもサンプルは合わない
後輩Sと色々話しながらバグを探す、修正
サンプルは通る
まぁ投げてみる => AC
プログラムを実行してからアウトプットが終わるまで2、3分かかっていて辛い感じだったけどまぁ通ったし良い感じ
3完

D問題

概要を聞く前に解けそうか聞いてみる
二人から分からないと返事が返ってきて悲しい気持ちになる
概要を聞く
「あれ、超見たことあるこれ絶対区間DPだゾ(適当」

という発言したはいいもののはっきりとした方針が浮かんでこない
とりあえず後ろの問題に一通り目を通す
Fぱっとみ簡単そう、でもさすがにDのほうが楽そう
Dをやることにする

冷静に考えて、bool memo[L][R]みたいな感じで全て消すことのできる区間を列挙してあとは
dp[i]:=iまでで作れる最大値 みたいなDPすれば良い

書く=>めっちゃバグる=>辛い気持ちになりつつ後輩Mと共にデバッグをする
暗黒時代の幕開け
後輩Mが正しい方針を示すもそれとは全く違う実装をして時間を無駄にする
頑張る
暗黒時代が終わる
サンプルは通る
まぁ投げてみる => AC
スコアボードを確認するとまぁ良いでしょみたいな順位にいたので良い感じ
4完

とりあえず残りの問題のどれに挑戦するか話し合う
E ... 一番ダメそう
F ... 一番いけそう
G ... 自分には無理そう、後輩Sは挑戦したいらしい
H ... 二番目にいけそう

というわけで自分はFを書き、
後輩SはGを考え、
後輩MはHを考えることに

F問題

内包関係をグラフにするとそれは木になるし、だったらあとは木の同型判定でしょ
まだ1時間以上あるしいける木がする
実装開始と共に暗黒時代が幕を開ける
残り1時間 => まだまだ書くことがある
残り30分 => まだまだまだ書くことがある
残り10分 => まだまだまだまだ書くことがある、なんだこれは

コンテストが終わった
実装力が足りていない(もしくはコーダーが足りていない

感想

アジアに向けてコーダーを育てようと決意