ACM-ICPC Japan Domestic Warm Up I

ICPC

私は腹を切って死ぬべきだと思いました。
以下、参加記録。

A: Traffic Analysis
  • あんまり問題読んでないけど、適当にvectorに突っ込んでソートしてみた。
  • 要素数が1個の時だけSampleが合わない。例外処理してSubmit。
  • WA。ここで初めて冷静に問題を読む。時刻0で計測開始ですね。
  • 例外処理を消してvectorの先頭に0を突っ込んでAccepted。落ち着け。
B: Cubes Without Holes
  • TopCoderで似た問題を見た気がする。
  • Bだから愚直に書いても許されるはずと思って入力サイズを見ずに塗りつぶし開始。
  • できた。ここで N = 500 だと気付いたけど、どうにかなるかなと思ってSubmit。
  • Complie Error. memset使ってるのにcstring入れるの忘れてた。ばーかばーか。
  • TLE. memsetをやめて使う分だけ初期化するようにしてもやっぱりTLE。これは予想外。
  • 結局vectorに突っ込んでsortしてuniqueしました。
C: Simple GUI Application
  • パーザー。Dに逃げようかとも思ったけど、とりあえず書いてみることに。
  • stringstreamから読み取ってパーズしてみたり、押されたパネルのポインタを返してみたりと新しい試みをしてみました。
  • 途中ICPC Programming Club入部希望という1年生に話し掛けられたので、アカウント作らせたり "Hello, World" 解かせてみたり。
  • そんなことをしているうちに完成。WA. この辺りから禁断のSubmitデバッグに走り始める。
  • プログラムを何度読み返してもおかしなところが見つからない。もう一度問題文を読む。
  • 出力すべきは「そのパネルの直接上」のパネルの数だ！再帰的に上の上まで調べてた・・・。
  • 直したら通った。引っ掛け問題だー。
  • tanakhさんが30分でここまで解いてるのを見て驚愕。さすがパーザーの偉い人。
D: Course Planning for Lazy Students
  • 可能な履修をDPで全通り調べてみよう。
  • (状態数) * (次に履修する科目) * (先修条件のチェック) で O(2^N * N^2)だ。ちょっと遅いか。
  • いやいやいや、先修条件のチェックはビット演算で一発だ。O(2^N * N) ならきっと間に合う。
  • それにしてもコーチはDPよりも探索の方が好きだったはずなんだけど・・・とか思いながら書く。できた。
  • TLE. 小手先の高速化を計るもやっぱり駄目。やっぱり探索だったか・・・。
  • DFSしてみたけど余計に遅くなって死亡。3問でした。

コンテスト後は、同じく鬱モードのid:iakasTと後輩Mとコーチとでガスト行ってきました。