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

繋がらない人のブログ

こうせん5ねん

PCK2014プログラミング部門予選参加記

お久しぶりです。

更新していた間、新しいことは何もやってなかったですかね。

さて、9/13(テスト期間中)にあったPCK予選の参加記を書こうと思います。

相方はじゃくしぃ君(@otama_jaccy)です。

方針としては、僕がWAについてビビリまくってたので、始めのほうは二人で読んで、僕が解き、実装時間が掛かり始めたらもう一人は別のを煮詰めて行くって感じでした。

1問目

担当:Pelkira
まあ、普通にAC
なんか、緊張してて問題文の読解に時間が掛かりました。

2問目

担当:Pelkira
これも普通にAC

3問目

担当:Pelkira
サクッとMOD取りたかったんだけど、なんか無駄に時間が掛かってしまった。
0のときの処理が上手くいく方法は無いか...と考えていたら相方が"0のときだけ場合わけすれば..."って言ってきて、ここで自分の緊張を実感しました。
まあ、ちょっと時間かかってAC

4問目

担当:Pelkira
始め入力をh1,h2とか取ってたけど、一緒に入れて問題ないという相方からの指摘。
おかげで修正がめんどくさくて以降ずっとh1という配列名でした。
こういうのは問題文を読みきる前にコードを書き始めてしまう悪い癖なんだろうなあと。

そんで、サクッとソートしてSample通してから、重複は省いていいことに気づく。

ここの処理も相方がサッと提示してくれました。

Sample通ったので提出。AC

時間掛かったと思ってたけど、この段階で2位だったみたい。

5問目

担当:Pelkira
問題見て、"こっからかな..."と意気込んでしまった。
問題を軽く読んでから、ちょっと時間が掛かりそうだったので相方に6問目を考え始めてもらった。
しかし、すぐに最適解は絶対に通らない区間があり、スタート地点より左側に行って戻って右側にいく...というのを思いついた。

で、ちょっとして、その区間を全通り試すだけじゃんと思ってコーディングを始めたが、左回りと右回りの式を考えるときに少し詰まったので、ここで紙とペンを持ち、相方に6問目を書き始めてもらう。

6問目

担当:otama_jaccy
問題の絵を見た瞬間に、幅じゃんと思った。

8手しか見ないで良いという制約をわかっていながらもDFSで通ることが思いつかなかった。
じゃくしぃ君がqueueとstackを間違えてたけど面白かったから許した。
Sampleに苦戦してる間に、僕が5問目を整理できたので、交代。

5問目(2nd)

スタート地点を0とするだけで、式がものすごく簡単に。
でもSampleが通らない。
スタート地点から一方向にだけ進むケースを見てなかったので、そこだけ追加してSample通ったので提出。
Sample通ったので提出。AC

6問目(2nd)

ここで僕が相方のやってることを聞く。swapしてる回数だけみて、側面のswapを見てないことを指摘。その後僕は7,8問目に目を通す。

Sample通したらしく、提出。AC

"これ落ちたらつらいぞ..."って言い合ってました。良かったです。

7問目

担当:Pelkira
8にも目を通しましたが、計算量がn^2を超えたので先に7に行きました。
vector.erase()に線形時間が掛かることを知らずに、TLE2回。
本を見たら書いてあったので、こっから粘りました。
残り20分ぐらいで、"あっこれa小さいから、そのままいけるじゃん!"と相方が気づく。
焦りに焦ってそこからの単純なコーディングに時間が掛かる。

残り2分、提出

...しようとしたが、ページが重過ぎる。
最後のボタン(確認の[提出])をクリックするところまで辿り着くも、画面が切り替わるとそこにはログインの文字が。

あと一回画面遷移が少なければ提出できていた...

間に合わなかったことに気づき、解せなさと悔しさが込み上げましたが、どうやら部内1位、地域1位だったのでまあ本選はいけるかなと。

終了

結果は、6完(点数忘れた)WAなしでした。
ビビってただけあって、WA無かったのでまあ方針は良かったんじゃないですかね。

凍結段階で8位でした。
追記:通過しました。頑張ります。(14/09/19 15:00)

感想

問題は去年より好きでした。
7問目やるだけじゃないか
じゃくしぃ君に僕のしょうもないところ埋めてもらえた感じがありました。

本人は6しか書いてないとか言ってたけど、結構時間を短縮できる指摘をもらってとても感謝しています。

以上です。おつかれさまでした。