AtCoder ABC217
ABC217参加しました。
簡単な問題は省略します。今回はD問題だけ。
D - Cutting Woods
解説 - AtCoder Beginner Contest 217
Submission #25625074 - AtCoder Beginner Contest 217
最初に思ったのは二分木で分解する方法。 つまり木のRootにすべてのxを保持し、その木が切られたら、切られた位置から左の木には、切られた位置より小さいxを、右の子には大きいxを割り当てる方法。
これだと、理論上は問題なく、実際クエリ2の検索も早いですが、木のノードが毎回xの配列を保持し、今回xは最大でL-1個($ \le 10^{9}$)あるので、ノードが増えるとメモリも食うし、木のノードを作るための配列コピーコストもかかります。
最悪、L=$10^{9}$でQ=$2 \times 10^{5}$(さらにクエリ1もだいたい同じぐらいある)の場合、木のノードもだいたいQあることになります。また木の深さの分だけ長さLの配列のメモリを取ることになります(顕密には、切った位置は含まれなくなるので違いますが)。木のバランスが悪い場合、つまり木の片方だけが伸びる場合、メモリ使用量も悪化し、1024MBでは到底足りません。64bitの整数型でMB単位での大雑把な見積もりを出したら10TBぐらい?
実際この方針だとREがでまくって、それがずっと解けずにいました。問題のサンプル入力だとどれもACなので、エッジケースでエラーが出たのかとかそこばっかり見てました。結局Lを大きくしたら上の問題が発覚したわけです。
そもそも解説にある通り、木のノードに毎回xの配列を保持する意味はないです。「切られた位置」が重要になります。
で、公式解答にある方法になります。なお自分で書いたACコードは以下のコードを参考にしたものです。
Submission #25599656 - AtCoder Beginner Contest 217
この方針だと切った位置しか知らないので、メモリ的にも無駄がないです。うまい。
感想
メモリ使用量にも気をつけよう。覚えなくても既知情報から計算で出せないかを考えるのって、実務でもよくある話ですね。ただ、今回は覚えておいたほうがデバッグが楽ではあった。
