東京海上日動 プログラミングコンテスト2020

コンテスト名、全角スペースなの!?ともあれ今日は気温が下がって朝から心の調子が悪かった。コンテスト中も最初はモチベなくてびっくりした。まあ最後はDを書き切れるか通し切れるかでドキドキしてた。

A - Nickname

サンプルも最初の3文字を出力していて親切?substrに慣れないのでresizeした。いま気づいたけどこのサンプル高橋直大じゃん。

B - Tag

設定が多いのでそれ全部確認するのに時間をかけてしまう。まず、座標は差の絶対値だけが重要。そしてスピードが同じかそれ以下だと追い付けない。そうでないときT秒で(V-W)*Tだけ追い付ける。オーバーフローに注意する。文字にすればこれだけ。一つ一つの要素は簡単だが全てを間違いないようまとめ上げるのはかなりの負担だった。

C - Lamps

けっこう照らす範囲が広い。光の強さ0でも自分のことは照らしてる。自分を照らしてる個数が改めて光の強さになるので、かなり更新がきついというか、なんか次元の違うものを代入してる感が。シミュレーションをするならいもす法でできるが、ダブリングなどで高速化するのは無理そう。かなりの時間悩む(そのうち景色が見えてくるんだろうなあと思いながら悩むのコンテスト中よくある)。増えていきそうだなというのはわかる(サンプルもそれを示唆している)。実験をしてみるとやはりO(log(N))で全部Nになりそうだ。何回やれば十分かを考えるのは難しいので、全部Nになったらループを抜けることにした(いいムーブ)。操作回数がO(log(N))でいい証明はできなかったが、小さいケースの挙動を慎重に確認して提出した。

D - Knapsack Queries on a tree

今日は問題文読むのにむちゃくちゃ時間かかったなあ。根から葉まで最大で18個頂点が並ぶ二分木。番号はセグ木みたいな感じ(二分木に限っては0-indexedにしないほうが実装楽)。まず、二分木じゃなくて普通のナップサックを書く。その価値を実現する最小の重さというのも考えたが、この問題の価値は小さくないのでやはり普通にその重さの最大価値でDPだろう。DPテーブルを共有は無理にしても、上手いこと分岐させて計算量を削減できないか。難しそう。が、上9個(普通にDP)と下9個(2^9全探索)に分けてギリギリ間に合いそうだと気づいてしまった。解説PDFに合わせN=2^(2*K)-1, M=max(L)として、前計算がO(2^K*K*M)、クエリがO(2^K*K*Q)。計算量は落とせるはずと思っていたが、これでギリギリ通るとも思ったので実装に入る(ほんとは計算量を落とすパートが楽しそうだったけど仕方ないね)。

まず、O(M)のメモリを消費するDPを2^9個行う(実装して気づいたが2^8個だった)。子へ移動するときは、頂点番号を2倍して、何個目のDPかのビットを見て立っていたら1を足す。クエリは、番号が2^9より小さければ前計算したものを使わず普通に全探索。番号が2^9以上なら、葉から2^9以上の範囲を全探索して、残りは前計算を使う(初めて2^9未満になった親の番号から2^8を引けば何個目のDPを参照すればいいかわかる)。「重さj以下の最大価値」でDPしてある(ちょうどjではない)ので、重さの合計がWだったら重さL_i-Wの情報だけでいい(前計算の参照がO(1)で済む)。実装上は、何個分全探索するかを先に求めておいた。

提出して、TLEは免れたが、WA。1回くらいのWAは覚悟していた。2.5秒くらいかかっていて、思っていたよりずっとギリギリだった(ジャッジかなり速くなってるから大丈夫だと思ってた)。結果的に3WAからのACだった。子を辿るときビットを見る場所が逆だったのと、何個全探索するか調べて頂点番号を変化させるから元の番号を保存してたのに使ってなかったのと、前計算は9個でDPするけど番号は8回しか変化しないのが慣れない処理で間違ってたので3WA。落ち着いて見直せばペナルティを減らせたと思うけど、落ち着いて考えていたらコンテスト時間が終わってしまうので仕方ない。ACできないんじゃないかと怖がりながら(実際しょうもないミスを最後まで発見できなかったことが何度もある)、よくやったと思うよ。