/ 最近 .rdf 追記 編集 設定 本棚

脳log[20200610] 第二回 アルゴリズム実技検定 過去問



2020年06月10日 (水)

最終更新: 2020-06-15T23:25+0900

[AtCoder] 第二回 アルゴリズム実技検定 過去問

 自分のすべての提出

第三回まで過去問をやったけど(20200607p0120200607p02)、やはり順当に解けるのは K 問題まで。L 問題が自分にとってのチャレンジ。そこまでの問題が漏れなく時間内に解ければ上級認定。今回時間をかけてでもこれが解けたのは、今日たまたま読んでいた蟻本で紹介されていたデータ構造を雰囲気で実装してみたことによる。(この日記は今日書いた>20200602p02.03)

 L 問題。清書しようとしたらバグに苦しめられた。

  • 最初の AC 提出 #14164516 (AC / 1293 ms / 93824 KB)
  • 清書した AC 提出 #14183943 (AC / 870 ms / 61964 KB)

ヒープ構造を使って冗長な情報を削ったら同時に保険がなくなって、雰囲気実装のふんわりした理解の穴が露呈してバグに苦しんだ。AC と AC のあいだに 3WA。

二分木におけるLCA

木の構造が定まっているので、bit演算で計算できる。

こんな感じでうまいことできないかずっと考えていたのだけど、バグが取れてみれば、1つか2つのノードを見るだけでは済まないみたいなのでもとから無理だったっぽい。

 せっかく清書したけど

他の人(Ruby では2人いる)の提出を見ていたら不備に気がついた。

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 のサイズが2のべき乗でヒープの最下段にきっちり収まるとき、なぜか倍のサイズを確保してしまってる。

例えば A.size == 8 のとき、ヒープサイズは 8+4+2+1 の 15 で十分だけど、上の BL の定義ではヒープ H のサイズが 31 になる。無駄のない定義は BL=1<<(A.size-1).bit_length。-1 がキモ。

 値の取得を最下段から遡ってやってるけど

これはうまくないみたい。今回は値の更新がなかったけど、更新を遅延させて値の取得に合わせて伝播させるためには、上から下っていかないといけない。

更新を遅延させるとか、考えてもみなかった。

それに最下段の要素に直接アクセスできたのは今回の問題に限った特殊条件ではある。範囲が配列の添字、0から連続する離散値だっていう。

必要になるまで考えないでいいことは考えない方針で。

 図を見てたらまだ理解が不十分で無駄なところがあった。

上に上るにしろ下に下るにしろ、自分が左右どちらの枝にいるかは考える必要がなくて、右ないし左に移動してから隣の階層に移動するだけで次の判断がつく。

右(左)に移動するとは、兄弟もしくは従兄弟ノードに移動するということ。最初に右の枝にいたか左の枝にいたか、そして右に移動したか左に移動したかで関係が違ってくるが、気にする必要がない。そのうえで上の階層に移動するとは、元のノードから見て親か伯叔父ノードに移動するということ。いとこの親ならおじさんである。

具体的なコードは次で。

 まとめ
提出コード長タイムメモリ
とりあえず AC660 Byte1293 ms93824 KB
ちょっときれいに AC740 Byte 870 ms61964 KB
十分に詰めて AC707 Byte 700 ms51032 KB

単純にタイムを縮めるだけなら他に優れた解法がある。これは次にこのデータ構造を使う準備みたいなもの。

 L 問題。Python で速い人の提出 #12961808 (279 ms / 61868 KB)

すっごく読みやすいね。実は答えを保持するスタックに push/pop するだけで答えになるらしい。しかも速い。

自分の最初の提出(TLE)がこれで、#14163100、素朴なやり方では無理なんだと思っていたのだけど、どういう違いが AC(速い) と TLE を分けたのか。

もっともらしいことを想像で書こうとしたのだけどよく解らなくなった。バグで無限ループしてるという方が納得できる。だって K の大小や D の大小に応じて、最小値を求める区間や回数はしっかり反比例してる。たしかに重たいケースで TLE になってるみたいだけど、他のケースの10倍20倍も時間がかかるというのは解せない。


D が小さくて A 数列がほぼ昇順に並んでるときに、N の上限の20万要素ちかい範囲から何度も最小値を選ばされる地獄を見ることがあるのか。いやあ、そんな意地悪な入力を与える人はいないと信じるよ。