脳log[20210522] エイシングプログラミングコンテスト2021（AtCoder Beginner Contest 202）／E 問題 Count Descendants

2021年05月22日 (土) 怖くて見てなかったけどこの前の ARC (20210510)のパフォが 300 台だった！えー、つまり灰パフォ？これが初めてではないし、むしろ大体そうなんだけど、ARC の傷を癒すには ABC１回では足りないぜ。なんなら ABC の D 問題にだってたまに……ときどきやられる。■明日の ARC (20時から！)のお誘いメールが来ない……。A 問題から 400 点なのはたいへん厳しい。ARC の 400 点は五分五分だ。

最終更新: 2021-06-08T14:41+0900

解けてしまった問題とまるで歯が立たなかった問題は、日記にならなくて困るという点で共通する。E 問題で Ruby の AC 提出をざっと見たら他の人の解法が異なっていたのでそれを。

ちなみに F 問題の提出(Ruby)はなかった。ゼロだった。まずね、凸包がよくない。それは自分の人生とは一切関わることのない専門用語(だということにしてこれまで無視してきたもの)なので。

話は E 問題。こちらはやること自体は明白で、読めばわかる。木が与えられて、深さを調べるのも、親を辿るのも、基本操作だ。この問題の問題は制約にあって、ノード数もクエリの数も、上限が20万だというところ。定数時間でクエリに答えたい。

あるノード U の子孫ノードを深さごとに数えておこうか。
深さを調べる深さ優先探索のついでにそれはできるけど、子ノードが記録した配列をマージするのが大変。ほぼノードの数だけマージ操作が必要。マージテク？
実装しなかったのでこれがアリなのかわからない。子ノードのうち底が深くないものから深い方へ、順番に足し合わせていくとどうなるか。

一直線の木で Σk 個の要素を処理するような実装でなければアリなのか。

これはマージしないでいいように１つの深さ記録配列を共有する実装。ただしノードごとに Array#dup した配列をスナップショットとして持っている。配列の要素数の合計がギガ単位になるけどどうかな、と期待して出したけど全然ダメだった。AtCoder の入力マジえげつない。上限は飾りじゃないのよ。

基本形はさっきのと同じ。クエリを先読みして必要なものだけ記録するようにした。TLE から 22 分経過していてコンテスト終了まで残り 10 分。あぶなかった。

これは他の人の AC 提出を読んで知った方法。二分探索を使うらしい。オイラーツアー？

深さ優先探索で深さを調べると同時に、あるノードに降りてきたタイミングと上っていくタイミングを記録しておく。
クエリがきたらノード U の両タイミングの間に処理をしたノード(=子孫ノード)のうち、ある深さ D にあるノードの数を答える。
タイミング配列をなめて深さを確かめる線形時間の処理は許されない。どうする？
(３つの提出を読んだのに思い出せない) どうする？
タイミング配列を深さごとに分けておくのかな。
クエリが指定する深さのタイミング配列を取り出して、そこからクエリが指定するノードの子孫にあたる範囲を二分探索で切り出すと、答えがわかる……かな？実装して AC をもらってないので不確か。

確かなことはこのあたりの提出を読めばわかる。(提出の早い順)

メモリ消費にけっこう差があって、自分の提出は最も多い部類。正直どこが原因なのかわからない。