最終更新: 2020-06-15T23:25+0900
第三回まで過去問をやったけど(20200607p01、20200607p02)、やはり順当に解けるのは K 問題まで。L 問題が自分にとってのチャレンジ。そこまでの問題が漏れなく時間内に解ければ上級認定。今回時間をかけてでもこれが解けたのは、今日たまたま読んでいた蟻本で紹介されていたデータ構造を雰囲気で実装してみたことによる。(この日記は今日書いた>20200602p02.03)
ヒープ構造を使って冗長な情報を削ったら同時に保険がなくなって、雰囲気実装のふんわりした理解の穴が露呈してバグに苦しんだ。AC と AC のあいだに 3WA。
二分木におけるLCA
木の構造が定まっているので、bit演算で計算できる。
こんな感じでうまいことできないかずっと考えていたのだけど、バグが取れてみれば、１つか２つのノードを見るだけでは済まないみたいなのでもとから無理だったっぽい。
他の人(Ruby では２人いる)の提出を見ていたら不備に気がついた。
B,BL = A.map.with_index.to_a,1<<A.size.bit_length H = [nil]*(BL-1) + B + [B[-1]]*(BL-B.size)
こんな感じで配列 A のビット長をもとにしてヒープのサイズを決めてるけど、例えば A のサイズが２のべき乗でヒープの最下段にきっちり収まるとき、なぜか倍のサイズを確保してしまってる。
例えば A.size == 8 のとき、ヒープサイズは 8+4+2+1 の 15 で十分だけど、上の BL の定義ではヒープ H のサイズが 31 になる。無駄のない定義は BL=1<<(A.size-1).bit_length。-1 がキモ。
これはうまくないみたい。今回は値の更新がなかったけど、更新を遅延させて値の取得に合わせて伝播させるためには、上から下っていかないといけない。
更新を遅延させるとか、考えてもみなかった。
それに最下段の要素に直接アクセスできたのは今回の問題に限った特殊条件ではある。範囲が配列の添字、０から連続する離散値だっていう。
必要になるまで考えないでいいことは考えない方針で。
上に上るにしろ下に下るにしろ、自分が左右どちらの枝にいるかは考える必要がなくて、右ないし左に移動してから隣の階層に移動するだけで次の判断がつく。
右(左)に移動するとは、兄弟もしくは従兄弟ノードに移動するということ。最初に右の枝にいたか左の枝にいたか、そして右に移動したか左に移動したかで関係が違ってくるが、気にする必要がない。そのうえで上の階層に移動するとは、元のノードから見て親か伯叔父ノードに移動するということ。いとこの親ならおじさんである。
具体的なコードは次で。
| 提出 | コード長 | タイム | メモリ |
|---|---|---|---|
| とりあえず AC | 660 Byte | 1293 ms | 93824 KB |
| ちょっときれいに AC | 740 Byte | 870 ms | 61964 KB |
| 十分に詰めて AC | 707 Byte | 700 ms | 51032 KB |
単純にタイムを縮めるだけなら他に優れた解法がある。これは次にこのデータ構造を使う準備みたいなもの。
すっごく読みやすいね。実は答えを保持するスタックに push/pop するだけで答えになるらしい。しかも速い。
自分の最初の提出(TLE)がこれで、#14163100、素朴なやり方では無理なんだと思っていたのだけど、どういう違いが AC(速い) と TLE を分けたのか。
もっともらしいことを想像で書こうとしたのだけどよく解らなくなった。バグで無限ループしてるという方が納得できる。だって K の大小や D の大小に応じて、最小値を求める区間や回数はしっかり反比例してる。たしかに重たいケースで TLE になってるみたいだけど、他のケースの10倍20倍も時間がかかるというのは解せない。
D が小さくて A 数列がほぼ昇順に並んでるときに、N の上限の20万要素ちかい範囲から何度も最小値を選ばされる地獄を見ることがあるのか。いやあ、そんな意地悪な入力を与える人はいないと信じるよ。