VKPC 2011 参加記

高専生OnlyのVKPCに参加してきました。

どういうコンテストかは↓

【GUMI】VKPC主題歌「Nijigens;Gate」【オリジナル】 ‐ ニコニコ動画:GINZA

結果は9完の1位/40人くらい で、なんだかんだで初めてコンテストで1位とりました。

no title

[-00:01] 開始前

なんかだらだら筆記用具とか持ってくる。正座。

[00:00] 開始

  • Aを読む。→「え・・・厨二はUTPCでおなかいっ(ry何これ難しい・・・。というかよくイメージできない・・・。」
  • 冷静になろうとがんばるけど、理解できなくてプルプルしている。
  • 冷静になって問題文を理解。とりあえずn次元なら、m倍すると体積はm^n倍になるなら、nが分かってないんだからnで全探索ほげだろう
  • 書いた。サンプル合った。

[00:06] A AC.

  • 遅くて涙目と思っていたら以外に通している人少ない。参加者数もあるんだろうけど。
  • Bを読む。→数分考えるもサンプルが理解できない(間違っていたらしい)。
  • ひとまず飛ばしてCを読むことにする。問題文ちょびっと難しい・・・。hyon死んだか。全探索やるだけじゃない?と思って書く。サンプル合った。提出

[00:12] C WA.

  • なんでだ・・・。理由が分からない。
  • long longにしてみる。

[00:15] C WA(2).

  • 悩む。凡ミスしてないかと思ったらなんか最初に余計なものをaという変数に読み込んでいる。
  • 訂正

[00:16] C AC(2WA).

  • 良かった・・・。あれ、First Acceptanceだ。でもB通している人がいるなぁ。
  • 相変わらずBのサンプル分からないのでFを読む。→「KUPC Practice A」の難しい版じゃないのこれ・・・。komiyamさんが考察していたような・・・?
  • まああ適当にsetとか使ってガリガリ書いてみる。サンプル合った。

[00:26] F WA.

  • 一部TLEしている。こっそり"KUPC Practice A"の効率的な解法をググる。ハッシュ使っているやつが見つかる。ただちょっとフォーマットが違うので諦める。
  • めんどうくさくなって、自明な枝狩りっていうか、定数項の改善加えたらも解けるんじゃねとか思う。

[00:32] F WA(2).

  • 未だにTLEする。ただあと少しっぽい。break追加!

[00:34] F AC(3).

  • 712msで通った・・・。テストケース弱くて良かった・・・。(追加とかされませんようにと願う)
  • I読む。どうみてもやるだけに見える。書いた。

[00:42] I WA.

  • あ、提出ソース間違えた・・・。もう一度。

[00:42] I WA(2).

  • 最後の方だけWAしている。long longかなあ?

[00:45] I WA(3).

  • long longでも駄目でした。「ADD X 1000」【「ADD X Y」「ADD Y X」】の繰り返しで指数的に増えるよなぁとか思う。
  • 多倍長持ってくるかぁ・・・。自分のライブラリを持ってくるもマイナスに対応していないことに気づく。
  • Spaghetti sourceの多倍長を使ってみるも、埋め込んでみたらマイナス対応してなかった・・・。
  • いろいろがんばってググるけど、C++のよさげな多倍長が見つからない。

[01:00] 決断

  • Java使おう・・・。必死にJavaの使い方をググったり、多倍長の使い方ググったりscannerの使い方をググる
  • いろいろがんばってゴリ押し実装する。(Unknown Language Roundのときの気持ちである。)
  • (string同士で==はできないとか、scannerで抜け出す条件はhasNextメソッド使うとかいろいろ混乱して泣く。)

[01:33] I AC(3WA).

  • 通ったやったー!1時間身動きできなかったのでやばいなぁと思う。
  • B読む。サンプルが訂正されて分かりやすくなっている!!すぐに書く。
  • サンプルあったー。

[01:38] B WA.

  • なんでWAすんだヨ!(半分くらいWA)っている。
  • あ、「no」の時最後の改行してない・・・。

[01:39] B AC(1WA).

  • 通ったー。さっきから無駄なWA出しすぎな気がするなぁとか思う。
  • L読む。問題文が難しい・・・。
  • とりあえず問題文を理解するのと平行してシミュレーションするソースを書いてみる。
  • あ、これ約数の個数関係あるやつだよね。平方数数えるってやつ。ほら明らかにsqrtと関係している!(PKUに類似問題あった気がするし)
  • 細かい値がsqrt(N)と1つ違うのは制約のせいだろ。適当に書いて提出。

[01:54] L AC.

  • 通ったー。うちの先輩がLだけ通している・・・。
  • K読む。問題文難しすぎ。謎な単語(シュタゲ関係らしい)が説明なしに使われていて困ったのでclarを飛ばしてみる。
  • G読む。阿部さん・・・。
  • 嘘っぽいけど、十分確率が小さくなったら切り捨てればよいからtは2^32も要らない。AOJのBenTohみたいな。(とても嘘)
  • とりあえず、"直前に会った"という記述を"前に会った"という記述と勘違いして2^50の状態数があって無理ゲーじゃねとか思うが、一応実際の状態数は少ないのではという期待を込めて実装してみる。
  • 一応がんばって書いた。AC具合を見てtの切り捨てる範囲を調節しよう!とか思う。

[02:24] G WA.

  •  全 滅 。 Acceptedが無い・・・。さすがに一回諦める。
  • 実はさっきからチラチラ読んでて、面倒くさそうだなあと飛ばしていたDを読む。冷静に時間軸を紙とかに書いてみると、適当にソートして、完成した時間記録しているだけで通りそう。

[02:34] D AC.

  • 良かった通った・・・。こういう問題は苦手だ・・・。
  • 阿部さんにリトライだー。なんか似たソースを出してみる。

[02:40] G WA(1).

  • さすがにWAで全滅。ここで"直前"という記述をようやく理解できる。これだったら[今の場所][前の場所][残り]で残りを適当に設定してやれば・・・。とか思う。
  • 提出してみよう。

[02:48] G WA(2).

  • やっぱり全部WAじゃないか(大激怒)
  • tの上限を弄ってみて効果があるか試そうとする。

[02:54] G WA(3).

  • 駄目でした。
  • そこから10分くらいがんばってもやっぱり分からんので、諦めてEを読む。
  • 「問題文難しかったので図を描いてみると、通ったといわれた時が一番面倒くさくて、テーブルを更新しようとするとコストが掛かるなぁ・・・。」とか思う。
  • テーブル更新しないためには、部分的にテーブルをDPしてやればよいということは分かったけど、実はこれでも時間が掛かると思っていて気が進まない(最悪n*m*(n+m)掛かると思っていた)。とりあえず実装してみる。
  • 通った位置をx・yの順番でソートしてやれば、この問題の制約の場合次に通った位置が一意にわかるのでソートする。
  • とりあえず書けたけどサンプルが合わないという事態に陥る。悩む。入力形式を勘違いしていたことに気づいて修正。
  • サンプル合った。TLEしそうで提出しようか悩む。
  • 累積和を使って、ある区間に障害物が存在してないか判定できれば、高速にnCrを計算しようとか思ったけど、実装がめんどい。とりあえず提出してTLEしたらそれしようとか思う。

[03:32] E AC.

  • hyksmさんが追い上げてきていてやばい。natriumさんがぱない速度でソースを提出している(まとめての提出だったぽい)。恐い。
  • あれ、500msくらいで通ってしまった。予想外。まあいいや。
  • G再び着手。いろいろやってみる。

[03:54] G WA(4).

  • やっぱり全滅。駄目らしい。悲しい。三度目の諦め。
  • Hを読んでみる。簡単そうに見えて分からない。うまく周期を見つけてやればよいのかな?と思ったけど分からない。悩む。
  • Jを読んでみる。幾何無理。解かないのは申し訳ないがパス。
  • 再びHを考えてみたり、実験してみるもこればっかりはよく分からない。「線形合同法 0にする」とかいう舐めたキーワードでググったりする。
  • そういえば結局Kを読んでいないことに気づく。読んでみる。
  • Kの問題文が難解すぎてかなり悩む。twitterで愚痴ったりする。移動すると相対的に時間やダイバージェンスが動くと思っていてさらに絶望する。
  • 冷静に考えてみると、移動する時間・ダイバージェンスは固定であることに気づく。状態数的にも幅優先探索でOKということが分かる。
  • 無駄な実装をしつつ、書き上げてサンプル一致。提出。

[04:33] K WA.

  • Oh....なんでだ。移動可能な条件を勘違いしていた。

[04:35] K WA(2).

  • またWAかこわれるなぁ・・・・。
  • 悩む・・・。10^6を100000だと勘違いしていることに気づく。
  • 訂正。提出。

[04:37] K AC(3WA).

  • 10^6を勘違いするのはしょっちゅうあって、なんでこんな勘違いをするのかが全く分からないけど勘違いしてしまう自分が嫌になる。
  • 残り時間は、Hを考えるもよく分からないため、Gがどういうケース与えられているのか確認するために害Submitをしまくる。
  • H通してる人がいる・・・「すごい。実は自分にも解けるのかなぁ?」とか思ってしまうも時間がなさそうだったのでGに害submit継続。
  • 結局よく分からなかったのでHの嘘解法でどれだけACもらえるか試してみるためにHでWAが出る害submitを再び開始。

[05:00] コンテスト いず おーばー

  • ぬわあああああんちかれたもぉぉぉぉぉぉん(迫真)
  • 2位に200点差をつけて1位だ!やったーとか思う。多倍長のクソゲーを1時間掛けてがんばったおかげだとか思ったり。

結果

  • (A,B,C,D,E,F,[G],[H],I,[J],K,L)の9完([]内は解けていない)
  • 900/1200
  • 1位/40人くらい
  • C,F,I,KでFirst Acceptanceもらってうれしい。

no title

感想

  • はじめてこういうので1位取ったので嬉しい。
  • 問題文がぱなくて読みづらかったが、程よい難しさだった。
  • ストーリーと主題歌が変な気合が入っていて笑った。特にストーリー面白かった。
  • 良い問題だったので、高専生だけじゃなくて他の人も参加できるともっと盛り上がったと思う!
  • 運営のかたがたオツカレサマデシタ!

ソース

別記事:VKPC2011のソース - kyuridenamidaのチラ裏