「っこ」のブログ

っこがプログラミングに関しての記事を書くブログ

PCK2016予選(9/11(土))参加記

久しぶりのブログ更新です。色々心に残ったので書きます。

@の後はtwitterのIDです。

僕、っこ@sujinbemani_79c(3年)はゲド@gedotinku(2年)とチーム名「ゲっこド」として出ました。

同じ久留米高専からの主要チームとしては、
・らて@LatteMalta(3年)とうぃんじー@wing3196(3年)のガチプロチーム
・つよっしー@TSUYOSSHI_(2年)と電柱@himajin4491(2年)
・川さん@kawakawa0826(3年)とカフェオレ@HMSR73(3年)
カービィさん@sai_55220(2年女子)とふなちさん@hu_nachi(2年女子)
とかが出ました。

開始前

昼ごはんをコンビニで買ったら、千切りキャベツに箸が無くてつらい。

ゲドと序盤どういう風に攻めるか軽く打ち合わせる。
前日の深夜に競プロしてた感じ、競プロの感覚忘れすぎててWAしまくってて、本番でWA重ねるのが怖くなったので、
1~5問目のやるだけをゲドに任せて、6問目から僕が考察することにした。

13:30~14:00

6考察するもわからん。
その間にゲドが2問目でWAしてしまう。

あと、向かい側の机でうぃんじーが爪切り出した。

6わからんから5~8問目を見てみる。

5問目 自明。速い実装法を思いついたので実装も自分にやらせてくれとゲドに申し出る。

7問目 この時点では「やばそう」という感想だった

8問目 問題が読めない

うんこにいきたくなったので、うんこにいった。
某O.J.先輩のことも考えると、SJ教室の右前のほうでPCK予選に行くとトイレに行きたくなるのかもしれない。
(該当記事は消されているので悲しい)

14:00~14:40

帰ってきたらゲドが3問目で2WAしてた。
まぁどうせこのチームはWA勝負はできないと思ってたので8完するしかないと思った。

ゲドが4解いてる間に7問目が自明DPだと気付く。
8問目の問題解読も終了。
9も一応目を通した。

ゲドが4までをACして交代。
僕が5と7を解く。その間ゲドには6と8を考えてもらった。
5と7結構速く実装が終わったのにWAなしでACしたので良かった。

二人で話し合って、8は凸法(知ってはいるけどやったことない)+最小全域木でいけそうということが分かる。
6は貪欲考察、8は実装なので、特性的に、僕が6、ゲドが8をやることに。

14:40~15:40

パンケーキを裏返した回数によって焼きあがるの意味わからんし、回数が多いほど固くなってしまうのも意味わからんしそもそも一つだけ裏返せるヘラを買え

そんなこと言ってても仕方ないので考えます。
普通にいろいろ考えても思いつかなかったので、制約から解法を察する感じで行こうとしました。

N<=5000なので、O(N)っぽい問題に見せかけて、実はO(N^2)なのでは?と思ったが、データセットの数が100となっていたので、その線を消す。
なぜO(100*N)なのにNを10^5などにしないか考える。
もうひとつ数字があるじゃないか。「パンケーキを裏返さなければならない数」。
それに、AGCで似た問題が出たおかげで、端っこが1個でひっくり返せない問題なら、貪欲的に決められることはわかっていたので、
端っこを一つで裏返す回数を仮定すればいいと分かった。
端っこを一つで裏返す回数は0~3の4つの値を取り、それが左右にあるのでO(N*(4^2)(*データセットの数100))

9をちょっと考察するが、平衡二分木っぽさを自分で実装する問題と思ってしまったのでやめて、ゲドのコーディングを見守る。
ゲドがバグらせる(コンパイルできない)
じゃあ俺が6実装するかってなった途端ゲドが気付いたので直す
ゲドがバグらせる(答えが違う)
しかしここでデバッグの神様が降りてきました。多分トイレの神様でもあると思います。
なんと、サンプルケースを投げた時の出力を見ただけで、
・凸法部分の辺の長さが2乗のままになっている。
・凸法の最後の辺の長さが足されていない。
ということに気付いたのです。
天才か俺は。
ゲドが直す。AC

15:40~16:05

6の実装を僕がするため、交代。
9,10は解ける見込みがないものと思っていたので、ゲドには9,10を考えさせずに、コーディングを見守ってもらう。
(明らかにやばい実装ミスを探してもらう。)

自分が通せば本戦が見えるということで、緊張でタイピングもままならないほど手が震えてました。
落ち着け。

実装してる途中、「10分くらいは経ってしまったかなぁ」と思うたびに大体3分しか経ってませんでした。
競プロコンテスト終盤でよくあるこれを、僕は「クロノスタシスしっぱなし現象」と呼んでいます。
クロノスタシスってかっこいいよね。

実装終わった!サンプルもあってる!提出するで!
 →WA
私、本日初WAでございます。

バグ探してたら、p[N-1]としなければいけないところをp[1]としていて「は?」って感じだ。
直す。AC

16:05~16:30

やれることはやった。
順位表凍結時点で11位だったが、凍結後に8問目を解いたので、凍結時点のランキング表でいえば9位に当たる位置である。
2チームも抜いてないことを願う。

一応9,10を見てみる。
10はなにかしらやばいもの。二分探索かDPは使いそうとか感じてた。
ゲドが蟻本見てたら、9が平衡二分木ではなく、めんどめのセグ木で解けることがわかる。
めっちゃいそいで写経するがもちろん間に合わず終了。

終了

8完4WA(62点)

問題について
・よく考えたら6は仮定するのは片方だけでよかったことに気付く。
・10はDPをうまくゴニョゴニョやるらしいが、例年のPCK最終問題よりは楽らしい。

周りのチームについて
・らてとうぃんじーが予選トップ通過を果たした。
・つよっしーのところが123457の6完。
・ほかの主要チームは12345の5完、7に挑戦しようとしたがバグった、わからなかったなど。
・感触的にも順位表見てもやはり7より6のほうが難しそう。


最後に
 本戦行きてぇ
 通っててくれ

追記9/21
9/16に発表がありました。落ちてました。
正直、地域枠多すぎやろ。どうせ今年も本選0完みたいなのでまくるんやろな。
8完で落ちたチームが僕ら含め1~2チームだけらしいです。(8完で10位入らなかった沖縄は地域枠ですくわれた。)
もうひとつの本選優勝します。