碧黴(あおかび)です。
11/25に開催されたCODE THANKS FESTIVAL 2018に参加してきましたので、その参加記をサクッと書きます。
予選
予選A: 218th ooo–
予選B: 295th ooo–
繰り上がりでTHANKSに通ったらしい。やったね。
朝
2時寝5時起きをかましてしまいクソ眠い。最悪だけど流石にもう寝れない時間なので新幹線で寝ることにする。
切符は当日とっても大丈夫やろと思い7時に仙台駅へ。一緒にいくゆきのんに30分待たされたのち、座席を確保し出発。帰りの指定席がほぼ埋まっているのを聞いて、そういえば世間は3連休なのかと気づく。祝日講義のある指定暴力団国立大学東北大学。
会場入り
若干早く東京に着いたので、新橋をテキトーに散策しながら問題の予想をする。まあ500までやし全完いけるやろ！wと高を括る。
受付開始ぴったりくらいにテレコムセンターに到着。備え付けのTシャツ(初ゲット)と持ってきたC++完全理解パーカーを着て気合を入れたのち、夏合宿で会ったTIkeさんやTABさん、Twitterで知っていたc7c7さん、らてあさんと話をしてたりした。
そんなとき、ふと背後を振り返ると━━━━━━
C++完全に理解した人がいるすごい pic.twitter.com/v6hcv4w5rf
— chokudai(高橋 直大) (@chokudai) November 25, 2018
AtCoder社長がカメラを構えていたのであった。
chokudaiさんとお会いしたのは初めてだったので、念願だった”アレ”をやる。
名刺交換に成功しました！！！！！！！@chokudai pic.twitter.com/pzNe81ATL6
— 碧黴(あおかび)@2日目西し-38a (@AokabiC) November 25, 2018
蟻本にサインしてもらうやつの話をしたら本人的には複雑らしいので遠慮しておいた。
競技
そんなこんなであっという間に開会式。気になるパーカーのボーダーはなんと上位50名。相対評価くんね
お弁当を食べる暇がなさそうなのはなんとなく察していたので、もらった瞬間に食べた。
競技スタート。Aはまあ100点なのでif文を3個書いたら終わった。
B。ボールの入った2つの箱から(1,3)個or(3,1)個取り出す操作を繰り返してちょうど0にできるかという問題。ペナルティがないのもあって、テキトーに剰余で判定したやつを投げたらWA。ちゃんと考察する。微妙に制約がデカいせいであんまり解法が降ってこない。操作の順番は関係ないので、とりあえずたくさん入ってる方から3個取り出し続けて同じ個数になったときに4の倍数かで判定。負数判定を忘れて若干詰まったものの、なんとかAC。連立方程式を解いてもよかったかも。
C。全ての2点間の絶対値の和を出力する問題。絶対値がイヤなのでソート。diff配列を用意して、それが何回加算されるかを左右から数えておわり。こういうのは絵をかくとすぐわかる。
D。2秒で浮かんだ貪欲を書いてAC。BとD逆やろこれ
E。問題の内容がさっぱり頭に入って入ってこない。1,…,i,…,Tの数字をそれぞれa_i個まで黒板に書ける。同じ数字iが2つあれば、その2つを消してi+1にできる。このとき、最後に数字がぴったり一つ残るような最初の数字の書き方は何通りありますか、という問題。Bで詰まって順位が低かったのもあって、結構焦る。操作的にビットっぽいなあと思ったりしたものの、実験してもよくわからない。
これ、参加記を書いてる今なら自明だなあと思ったけれども、小さい数字から順に消せるだけ消して、1個あまるとダメだから、割と簡単なDPで解ける。
i番目の数字がj個残ってるとき、i+1番目の数字はk個最初からあるとしてj/2+k個になる。つまり、
\(dp[i+1][j/2+k] += dp[i][j]\)
をやればいいことになる。計算量は\(O(T max(a)^2)\)
なんとなくDPっぽいことは察してたものの、”消せるだけ消す”操作を繰り返したときに計算量が結構大きくなるような気がしてて、うーんうーんと唸っていた。等比級数の和なのにね。
結果
B遅くてEも通らないとなると当然カスなので、90/97 位。めちゃくちゃ悔しかった。
懇親会ではわりと凹み気味だったけど、Twitterで知ってる各位や初めて会う方に名刺をばら撒いたりしてるうちにちょっと元気になった。寿司最高。
反省
Eみたいな設定の問題は、どれか1種類について独立して考えられないかを検討する。DPっぽいと思った時点でそれをやるべきだった。
3時間の使い方も正直微妙だった。Fも割と簡単だったので、そっちを検討するのに移るべきだったかも。
来年こそは本戦に出たい。