PCK2016予選　参加記録 - reppuu77 の　競プロ　の　ブログ(たぶんPCK2016だけ)

・前日まで

　・とにかくプロコンやってた思い出しかない。

　・なかなか眠れず寝たのは5時半

・始まる前まで

　・リポビタンD Proを飲んでゲン担ぎ

　・時間になるまで緊張を紛らわすためにいろんなことしていた

　・テンプレの準備とか

・競技(前半戦)

　・自分はとりあえず5問目までを0WA50分で通すことを目標にスタート

　・その間にもう一人が６問目以降を考察するという流れ

　・１問目から提出にいろいろ気を付けていたがさすがにやらかすことはなかった

　・２，３，４，５と続けてACしここでいったんストップ

　・６問目でどうすればいいか止まる

　・７問目の方が明らかに簡単そうだったのでそっちを実装しAC

　・ここら辺で１０問目を捨ててたような

　・６問目もよくよく見たらいけそうだったので実装してAC

　・ここまでを１時間２０分で終えることができた

　・いろいろうれしくてハイタッチしてた

・競技(後半戦)

　・１０問目は捨てたので８問目か９問目へ

　・相方曰く８問目は問題文が読めない＆９問目は実装が浮かばない

　・８問目は読めたら解ける可能性があったので８問目の解読へ

　・何とか解読できたはいいがどうすればいいかわからない

　・データ構造の本に明らかにこれを使えと言わんばかりの凸包

　・凸包を実装するが、本のサンプルがなぜかうまくいかない

　・８問目の問題文を見てるとそのまま直さずに流用できると気づく

　・ここからの闇が深い

　・問題文的に最少全域木を使うということは分かっていたが、うまい実装方法が思いつかない

　・あれはどう？といって席を替わり実装する。途中で壁に当たるをn回はする

　・まずそもそも生成途中のグラフでどうやって最少全域木作るんだってなる

　・すでに凸包によって作られている辺はコスト0にすればいいんじゃね？という相方の神の一声

　・サンプルを通ったのでAC　と思いきやWA

　・凸包がやはりまずかった？

　・出力がなんかまずそう？

　・とりあえずcoutをやめ、書式制御文字で小数点以下4桁に固定

　・でもまぁそれだけじゃ通らないでしょ

　・なんかいろいろいじる

　・時間内からとりあえず出してみるかぁ

　・AC

　・！？

　・ハイタッチ

　・９と１０を解く時間はなかったので動かない順位表に向かって祈りをささげる

　・ちらっとN高校の名前を見て驚く

　・競技終了　8AC1WA　成績枠どうなんだろって位置

・競技を終えて

　・Twitterへ集合

　・公式アカ見たりとかプロたちのツイート見たりする。

　・９問目と１０問目の解法を見てみる

　・えぇ・・・

　・たぶん、たぶん本選はいけるので頑張る。

・問題解説

　・１問目

　　なんか32ビットがうんぬんかんぬんっていう問題

　　要するに与えられた整数に32を掛けるだけ

　・２問目

　　日の出、日の入か昼間か夜間かを日の半径と水平線で求める問題

　　要するにif文の問題

　・３問目

　　西暦と和暦の相互変換

　　if文の問題その２だったが、凡ミスでWA出す人多そうな問題だった

　・４問目

　　土地を少ない数の正方形で余すことなく分ける問題

　　whileぶん回しで調べた

　・５問目

　　違うようで同じ情報が混ざってるから数えてってやつ

　　無難に小さい順に並び替えたのち完全一致があるか調べた

　・６問目

　　２枚同時にひっくりかえせるヘラで出来る限り少ない回数ですべてのパンケーキを必要ない回数ひっくりかえそう

　　ここで気をつけるのはヘラの回数ではなくパンケーキをひっくり返した回数

　　さまざまな方法があると思うが自分はメモ化再帰で

　・７問目

　　文字列Aから文字をいくつか抜き取って、左から見た時に文字列Bになっているパターンを数える

　　正直すぐにDPだとわかったのでメモ化再帰その２

　・８問目

　　まず集落を囲む道を作って、その後すべての集落に行けるように道を作る。使わない道は消す。できる限り道の合計が短くなるようにする。

　　なんか凸包っていうので集落を囲んだ後最少全域木を作る。

　　出力は普通にcoutだともしかしたらダメ？

　　printfで書式制御文字で小数点以下4位のみ出力するように固定してみた

　・９問目

　　プログラミングコンテストの順位を実況する。

　　なんか座圧とBIT使うらしい

　・１０問目

　　なんかゲームの中でアイテムがうんぬんかんぬん(問題ちゃんと見てない)