CODE FESTIVAL 2018 に参加しました

CODE FESTIVAL 2018 に参加しました。
昨年は予選 C のギリギリで引っかかって通過したのですが、今度は予選 A で決められてよかった。

本選前

会場近くをうろうろしてました。
ちょうど同時期に開催されたきらら展の様子。


昨年と同じだったため、会場には迷わず行けました。
OP 映像に、昨年は見つけられなかった自分のハンドルネームを見つけて満足。

本戦

A

beta.atcoder.jp
いきなり難しそうな見た目をしている。
300 点であることを信じて制約に目を向けると、辺長の下限が大きいため条件を満たすには a と b、b と c が隣接する必要があると分かります。このような 3 頂点の数え上げでは、真ん中（ここでは b）を固定すると見通しがよくなることを思い出すと、解くことができます（4:08）。

B

beta.atcoder.jp
普段あんまり見ない設定の問題。
300 点なので 5, 6 分考えれば解けるはずと思ったのですが、分からなかったため一旦飛ばして C をやりました。
G まで解いてから戻ってきて再び考察したところ、まず単調な条件での最小化なので二分探索が使えそう。さらに分母を適宜適量払いながら計算するとオーバー / アンダーフローを回避できることに気づき AC（151:16）。
実際には、式の両辺の対数をとって積を和に変換するのがいいらしい。たしかに、そっちのほうが汎用性がありそう。

C

beta.atcoder.jp
今回のコンテストの 300 点問題 3 つ中だと、一番競技プログラミングっぽい気がする。
まず問題文中に、目を引く強い仮定（全てのプラン i に対して、通話時間が A_i 分の場合には他のどのプランよりも通話料金が 1 円以上安くなることが保証されます。）があることに気づきます。これをなんとか活かしたい。
ある人に注目すると、その人の通話時間より A が大きいプランに関しては、かかる金額は B です。よって、そのようなプランの中で一番得なプランは簡単に見つけられます。通話時間より A が小さいプランに関しては、上述の仮定がなければいろいろな情報を考慮しなければならないのですが、仮定のおかげで A が大きいものほど得であると分かります。よって前者の最適値を適当な前処理やデータ構造で見つけ、後者の最適値を二分探索で見つけ、そのうちの小さい方が答えになります（20:51）。

D

beta.atcoder.jp
600 点の E より難しいと話題になっていた D。
略称の候補それぞれについて、いくつの文字列に採用できるか数える O(52^3 * N ≒ 4.2 * 10^9) でも通ってしまいます。
自分は O(52^2 * N) で解いた気になっていたのですが、今見たら O(52^3 * N) でした。
52 の指数を 2 に減らせるらしいのですが、よく分かりません。難問（56:28）。

E

beta.atcoder.jp
どこか（蟻本）で見たような問題ですが、微妙に設定が違います。ただ、基本的なアイデアは似てると思います。
いろいろと解法があるらしい。
自分の場合、水を注いでもらうだけなら無料、飲むときにお金が発生すると考えて、基本的に常に水を K 本持ち歩きつつ、今の街でもらえる水よりコストがかかる水は全て捨て、そのあともらえるだけ水をもらう、という貪欲なアルゴリズムを考えました。
これは deque を使えばうまく実装できます（75:53）。
提出コード
beta.atcoder.jp

F

beta.atcoder.jp
E と同じく、とりあえず全て食べて、あとで都合が悪くなったら美味しさの小さいものからなかったことにすればいいのでは、と貪欲に考えたのですが WA を出してしまう。一旦パスして G と B を解きました。
考察に戻り、コンテスト終了 10 分前にようやく、それだと不都合があることに気づけたのですが、満足に考察する時間はなく未着手。難問。

G

beta.atcoder.jp
適当にひよこの振り分け方を 1 つとります。その振り分けにおいて、あるかご x にはかご y より多くのひよこがいるとします。このとき、もしかご x に、かご y のいずれかのひよこより大きいひよこがいたとすると、この振り分け方は最適ではありません。なぜならば、そのようなひよこ同士をスワップすることで、ストレスの総和を小さくできるからです。
このことに気づくと、適切なひよこの振り分け方は、小さいひよこから何匹かを 1 つのかごに、残ったひよこのうち、小さいひよこから何匹かを 1 つのかごに、といったものと分かります。また、このようにして作られていくかごに含まれるひよこの数は、単調非増加とも分かります。
前者の性質のみを使うと、愚直計算量 O(N^3) の DP を作ることができます。後者の性質も鑑みると、一度にあまりたくさんひよこを含むかごを作る必要がなくなります（たくさん含みすぎると、今まで作ったかごにそれより真にひよこの少ないものがあることになる）。よって、DP[i][j] := 小さい方から i 番目のひよこまでで j 個のかごを作るときのストレスの総和の最小値、とすると、このテーブルの二次元目を埋める計算時間が O(NlogN) に落ちるため、全体で O(N^2logN) で解くことができます（130:34）。

H 以降

読んでません。

結果

自分の予想を大きく上回る？ 22 位で終わることができました。賞金は全く狙っていなかったのですが、もうちょっとでもらえたと思うと少し悔しい。パーカーも無事手に入れることができました。

チームリレー

恒例のチームリレーです。本戦の順位が思いの外よかったため、図らずも難しい問題を担当することになりました。


我々のチームの基本戦略は、前半の問題はペアで取り組み確実に解く、残った後半の問題は臨機応変に解いていく、というものでした。
自分はペアとしては C を考え、H を考察・実装する役割でした。
C 問題については、自分が計算量の見積もりを間違えるも（すいません）全探索で行けそうと分かり、チームメンバーに実装をお願いし AC。
C が終わってからは H 問題を考えました。なんか高速ゼータ変換（確認したら高速メビウス変換だった）的なあれで高速化をすればなんかうまく数え上げれそうな気がすると気づくも、実装が重そうな上実装キューも詰まっていたため、他の問題も見てみたり、デバッグに加わろうと試みたりしていました。そのままコンテストは終了。上位 3 チームのみ口にできる高級牛肉は味わえませんでしたが、代わりに（？）ピザや寿司を食べました。

まとめ

本戦もチームリレーも、昨年の反省を活かし（？）、少しはよく立ち回れたような気がしました。
来年も参加したいか問題なのですが、競技プログラミングの競技レベルが爆発的に上昇してる現状もあるので、謙虚にコツコツ予選突破を目標にしてやっていこうと思います。