Hatena::Grouptopcoder

思考錯誤 - By evima

プログラミングコンテスト参戦記。本番中のメモを公開します
過去のコンテストへの出題一覧 / TopCoder / Codeforces / Twitter

2012-09-18天下一プログラマーコンテスト 2012 本戦

本番8日前、コンテストの詳細メールに衝撃的な内容が…。


  • 「ニュース7の取材が来るよ。邪魔にならないよう気をつけてもらうから了解してね」
  • ………
  • …マジで!?!?
  • 人生最大のピンチを迎えてしまった
    • 私にとって、テレビカメラ以上に怖いものはない
  • ………しょうがないか

【本番前夜】

  • 寝れない
  • 羊を576匹数えて疲れたところでやっと寝れた
  • 4時間半くらいしか寝ていない。9時間寝るつもりだったのに…

【本番当日】

  • 夏合宿のコンテスト1の開始1時間後、抜け出してKLab本社へ
  • ここでマウスを持って行き忘れる。痛恨のミス!
  • 集合時間ちょうどにビルに到着
  • 「偶数階にしか止まらないエレベーター」で22Fへ
    • 私のような俗人が所属する場所ではありませんね
  • 出場者カード(首からぶら下げる)を受け取る
    • 本名と一緒に書かれると、evimaって恥ずかしいハンドルだな…
      本名の一部をハンドルにしている方が羨ましい
  • 会場に入室
    • 普通の教室風の部屋だ。窓の外の光景(22F)以外…
  • マウスを貸してくれないか訪ねてみる
    • あっさりOK
    • なんと、私が使っているのと同じマウスが出てきた!運がいい
  • semiexpさんがNHKのインタビューを受け始めた
    • やばい、変な映り方をしたら大変だ。寝よう!
  • もう集合時間を大きく過ぎているのに始まらないぞ…?
    • 「2人道を間違えた方がいるのでもう少々お待ちください」
  • あ…しまった
    • 受付で渡された、交通費の領収書(白紙)をなくしてしまった!
      • 受付->席->トイレ->席 としか動いていないのに、いつなくしたんだ…?
    • 仕方がないので、マウスの件と同じ方に伝えてもう一枚もらう。恥ずかしい…
      • コンテスト後にパソコンの下から出てきました
      • この方には、さらにトイレへの道を2回教えていただき、
        4度もお手数をお掛けしてしまった。申し訳ありません
  • 結局、道を間違えた2人が不在のままでコンテストの説明スタート
  • 部屋前方のスクリーンに順位表が!
    • 緊張が限界を超えてきた。泣き出しそう
  • でも、決勝のURLはコンテスト中は公開されないみたいだ。良かった
    • 間違い。実はTwitterで順位表のページだけ公開されていて、家族にも見られていた
  • 問題数はまさかの5問!誤答ペナルティはいつもの1/3の5分
  • いよいよか…
    • パソコンのスクリーンの明るさをMAXに
  • 3!2!1!0!

【コンテスト本番】

  • まずは全部の問題に目を通す
    • どの問題も、内容を理解するのは簡単だ。おや…?
  • 前方のスクリーンの順位表、semiexpさんの問題Aの欄に「お待ちください」と言いたげなアイコンが
    • 表示が変わった。「100 01:57」
    • …速過ぎないか!?
  • その後も正解続出、5分で7人も。やばい、全く分からない…。
    B以降の問題の難易度を吟味しながら、Aを具体例で考えていく
  • 結局、Aは考えうる最も簡単な方法で解けるらしい
    • 0:14に正解。私より遅かったのは4人のみ、うち1人は遅れて入ってきた方で、
      もう1人は明らかに他の問題に取り組んでいる
  • とりあえずBに取り掛かる
  • 最初の20点は全探索で取れる
    • しかし、残りはどうするんだ?
  • 本番が終わった今となっては理由がわからないが、ダメな選び方の数を数えて全体から引く、
    という方法を思いつかず、お手上げ
    • 本当に、なんでこんな基本的なことが分からなかったんだ!?
  • 仕方ない、20点取って撤収だ
    • 0:28に提出、一時的に2位に。全く意味のない2位だが
  • Cには唯一部分点がなく、All or Nothing。ややこしそうなDPだが、逃げるわけにはいかない
  • 各敵と戦い始める時点での自分の状態(HPと連続攻撃の威力)でDPを書けばいいはず
    • でも、敵との戦いは単純なようでかなり複雑だ…
  • Dは明らかに異様な問題。おそらくこれがタイブレークで、満点はとてつもなく難しいのでは
  • Bと同じく、20点は全探索で取れる
  • こういう問題の経験はほぼないので、1.9秒の間ランダムに三角形を作り続けることにする
    • …が、C++でランダムに配列の要素を並べ替える方法が分からない
      • bool comp(int a, int b){ return rand()%2; } でソートしてみたが、変な要素が紛れ込む
  • Googleで「randomsort」で検索
    • SRM402の同名の問題ばかり引っかかる…
  • 検索ワードを「ランダムソート」に変える
    • 今度はあっさり"random_shuffle"という関数が見つかる
    • これで何分無駄にしたことか…
  • 71:21にDに提出。N=18のケースでも2点くらいは取れそう
  • 結果は20点。う0ん、ダメか
    • 後で気づいたが、N=18ならDPで解ける。高橋君が乱数を使うからといって、
      こちらも乱数を使う必要はなかった
    • これはBとは違い、しっかりと心理的な罠にかかってしまった
  • Eは複雑すぎる。挑戦すれば25点くらいは取れるだろうが、そうするとCが解けなくなる。もうCしかない
  • 各敵との戦闘開始時点での自分の状態でのDPを諦め、敵のHPDPの状態に加える
    • こうするとループが発生してしまいまずいが、本番ではそんなことは頭になかった
  • 残り30分、順意表氷結
    • もう6位は不可能だ。Cを解いて意地を見せるしかない
  • サンプルケースに正解!99:07、Cに提出
  • 判定:ランタイムエラー
    • 実際はREの他にWAのケースも
  • あまり考えられないが、配列の範囲外を参照したりしているのかも?
    • もうペナルティの数などどうでもいい、配列の範囲を超えた要素を参照しないようにして再提出(105:05)!
  • またRE。しかもさっきは正解したケースの一部でもREやWA
    • もうやけくそだ!配列のマイナス番目の要素をアクセスしている可能性を潰し、3度目の提出(110:20)
  • またまたRE。…これは、スタックオーバーフローか…?
    • 最後の望みを掛けて、高速化用の場合わけを外して4度目の提出(112:20)
  • …判定変わらず。ダメだ、多分スタックオーバーフローで間違いない。終わった
  • …負け、か
  • もうCの100点は諦める。あと2点を狙い、Dに一度出したプログラム(ランダム選択)を再提出(118:22)
  • …20点のまま。2点くらい取れてもおかしくないだろうが!最後の最後にもう一度だけ提出(119:56)
  • 結果が出る前にコンテスト終了 (氷結された順位表)

【コンテスト終了後】

  • 最後の提出は…得点にならず
    • いいところなしで終了。この成績では出られなかった人に申し訳ない…
  • chokudaiさんに「この問題数だと問題との相性もあるから」と慰めてもらう
  • 「ビットDP」という言葉が聞こえるが、何のことだ?(まだDの心理の罠の中)
  • 表彰式
    • 夏合宿の人で、天下一決勝に出場していない人も加わる
  • スクリーンに氷結された順位表が…
    • 下位から順に、最後の30分で提出された部分が明かされる
  • 私は得点が増えず、15位→17位/22 (最終順位表)
    • 下から6位か。なんというオチだ
  • Dで22点が3人、24点が1人…くやしい
    • まあ、その4人も全員「心理の罠」にはまっているのだが
  • Dの満点は不可能かと思っていたが、Top3は全員満点か
  • 懇親会
  • KLabの社員の方に、単刀直入に「なんでこんなに羽振りがいいの?」と尋ねてみる
    • 「知名度向上のため」とのこと。NHKの取材も入ったし、成功ですね
  • ここでニュースが。なんと、その日の19時から今日のコンテストが放送されるらしい
    • 今日かよ!!見たくないが、見ないわけにもいかない。家族に録画を頼む
  • 私にマウスを貸してくださった方にお会いする
    • トランプマジックを披露され、同じトランプ(新品)を頂いた。ラッキー!
  • 天下一は来年も開くらしい。絶対帰ってきます、と社員の方に宣言して終了
  • その日の夜
  • ニュース7のサイトをチェックすると、なんとWeb上でコンテストの部分が公開されている
  • 恐る恐る見てみる
    • …げ、めっちゃ映ってる
    • おまけに、順位表の「17位 evima」の部分まで移ってる。余計なとこ映すな!

以上、一生にまたとない経験でした。