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

レートがどんどん下がるみんなに抜かされていく 824th Perf=1672 1864->1846(-18)
そんなことも言ってられないのでちゃんと参加メモを書きます

A - Nickname

これはひねりがなかったのですぐ解けた S.substr(0, 3) をして終わり

B - Tag

逃げる方向とかを固定したかったので $A \lt B$ になるように矯正
すると、相対速度 $V-W$ と $T$ の積が $B-A$ 以上になっていれば捕まえられる。
これを適切に描いたらAC long long とかにしておかないと掛け算でオーバーフローするんじゃないかな

C - Lamps

思いつくまでに時間がかかってしまった
操作は $\mathrm{O}(\log N)$ 回くらいすると、全ての数列が $N$ になってしまう。
これだけ気づければもう終わりなんだよね…

こんな感じで理由を説明すればいいかな。
まず、とりあえず $1$ 回操作すると、全ての数列は $1$ 以上になっている。
その状態から、ほとんどの数の寄与が操作毎に $2 A_i + 1$ になっていくので、
$\mathrm{O}(\log N)$ 回くらいで全部 $N$ になるという見通しがつく。

端を考慮した証明してくれている人とかいるのかな

操作自体は imos法を使えばいいので $\mathrm{O}(N)$ でいける。
よって $\mathrm{O}(N \log N)$ である。

$41$ 回やると制約上で全部行けるらしい。

D - Knapsack Queries on a tree

これ通したかったな…

先祖だけしか見ないので、各クエリ毎に要素は最大 $18$ 個くらいしか呼ばれない。
ただナップザックは制限がない状態だと $\mathrm{O}(2^N)$ になっているので、まあここでやるとしたら半分全列挙くらいしか無いだろうって思う。実際に計算量を考えてもぎりぎり通りそうっていう感じ。これだけだと通らないんだけれども。 9 9 で分けても通らない。
ここで、もうひとつ事実に気づくべきなのは、根の方の要素の組み合わせは少ないので、こっちを前計算で求められるということである。
例えば深さ $10$ のノードそれぞれに対して全列挙を求めてあげても、 $10 \times 512 \times 2^{10} = 5242880$ くらいの計算量にしかならないので、こっちに半分全列挙の比重をかけてあげる。
そうしたら、残り $8$ 個に対しての列挙をしてそれで、 $10$ 個の方の列挙した奴に対してupper_boundとかかけて計算すればいいので、結構計算量が厳し目だが通る。