らての精進日記

修行をします

PCK2016予選

うぃんじー(@wing3196)と出ました(´・ω・`)
奇跡的にペナルティ0だったので一位でしたが、全完までの時間で30分以上差をつけられたので精進します...


以下、コンテスト中のアレです。長いので気を付けてください

コンテスト開始前

飲み物をそこそこ買って徳を高める。

コンテスト開始

正直予選に出ているという実感がなかった。とりあえず1問目を開く

1問目

問題文が頭に入ってこない。

となりでうぃんじーが爪を切り始める。(←意味不明)

心の目で問題を読むと、分かった。適当に実装してAC

2問目

問題文を読む気がしなかったが、図などでなんとなく題意をつかんだ。楽しくなさの化身という感じ

3問目

暦系の問題。鳥肌が立つ。「パターン青 使徒です」みたいな気持ちになった。
賢くやる必要もないなあと思ったので、泥臭く場合分けする。絶対にWAを出したくないという思いからコードをにらむようにチェックしていた。

4問目

読む。敷き詰める正方形のサイズはバラバラでいいと思ったので、ユークリッドの互除法のイメージで埋めていく感じかなあと思った。
実装したがサンプルが合わないので、問題文を読み直したら正方形のサイズは全部同じだった。まあ4問目なのでしょうがないね

5問目

なんかやばそうな図が載ってる。幾何だと思い、やりたくなかったので相方に投げて6問目にいく。

6問目

あーdpするかーとなったが、相方に「端のやりかたを決めて貪欲すれば」と言われ、はいという感じでした

5問目

相方が「めっちゃやるだけ 10行くらいで終わりそう」と言っていたので、実装を任せる。
ホントにすぐACしたので問題概要を聞いたら、幾何じゃなかった

7問目

「あ、そういうのいいから・・・」ってなった。3分くらいでAC

8問目

問題文がダメ。題意が伝わってこない。めんどくさいので相方に任せよう・・・(←ダメ)

9問目

たまによく見るやつだ!みたいな感じ
どうせBIT持てばええんやろ・・・となったが、同じ得点のときの処理が思いつかない。
少なくとも(得点、チーム番号)の組を先読みしてリストアップし、番号を振りなおせばいける(めんどくさいけど)

ということで実装した。こういう実装力ゲーみたいなやつは得意なはずだが、サンプルが合わないのですぐに相方の8問目に代わる(泥沼にはまるのを避ける一般的なテク)

8問目

相方が凸包などを実装するのを温かく見守った。
アンドリュースキャンをする関数の名前を「SortReew」にしていて控えめに言ってウケた。

10問目をちらっと読んだがやばそうな気がしたので、相方が8を実装している時間は9のコードを目デバッグしていた。

少しの間サンプルが合わない時間が続いたが、協力してデバッグしてスムーズにACした
(相方がデバッグ出力などをしている間に僕がサンプルをノートにプロットしたりしていて、協力プレイ感があった)

9問目

問題文を読み直したら、「i番目のチームが現在何位か求める」問題だと思っていたら、「現在i位のチームが何番目のチームか求める」問題だった。
一瞬ヒヤッとしたが、大して変更箇所が多くなかったので良かった。修正したらサンプルが通ったので投げたらACした

10問目

ごちゃごちゃ考えてたらよくわからない二次元dp(更新にO(N)かかるので全体でO(MN^2))が生えた。(←嘘解法)
なにかしらのテクニックでdp高速化するやつやろwwwとなって、convex hull trickか??とか言っていた(単にconvex hull trickと言いたかっただけ)
どう考えても漸化式がconvex hull trickに適してないし、そもそもこのdp自体嘘っぽかったのでやめる。

とりあえずどのくらいの情報があればある状況を表現できるか考えると、
(どこまでの敵を倒したか、どこまでのアイテムを買ったか、所持金、パワー)
で表現できるなあと思った。「どこまでのアイテムを買ったか」という情報があれば今まで消費した金額が分かって、
「どこまでの敵を倒したか」という情報があれば今までに得た金額がわかるので、
所持金は持たなくてもいいと分かる。

所持金を最大化する問題なので、
dp[i][j]:=最大の所持金
みたいにやると思っていたが、どちらかというと本質はパワーの最大化なので、
dp[i][j]:=敵をi体倒して、アイテムをj個かったときの最大のパワー、とした。

更新にO(N)かかるので全体でO(MN^2)だが、実はうまくやると更新はO(1)でできると分かったので、やった
(アイテムを一気に買うのではなく、じわじわ買うといい)

全完後

正直全完できるとは思っていなかったので、盛り上がった。
しかも順位表みたら他に0WAのチームがいなくて、1位になってた。

お菓子を食べながら相方と順位表を眺めて遊んだ

終わり

問題についてですが、例年よりは簡単だったと思います。あと、後半にあまりクソ問がなかった(前半はクソ)
一昨年は2問しか解いてないし、去年は7完地域枠だったので、ちょっとは成長したかなあと思いました。

正直本選の後半の問題は解ける気がしないので、3位くらいを目指して頑張りたいと思います。