最終更新: 2020-06-18T09:50+0900
ちょっと日記に書きたくなるような、適度に歯応えのある問題だった。問題は、例えば
2 4 6 1 3 5
のような数列が与えられたときに、
1 2 3 4 5 6
のように昇順に並べ替えるためには、いくつの要素を移動する必要があるか、その最小を答えるというもの。
例えば、「2 4 6」「1 3 5」の並びは2要素間の関係において増加しているのでそのまま温存して答えにできるのではないか、逆に、「6 1」の並びは減少しているので必ず介入して解消しなければいけない。
しかし2つの増加列の関係に注目すると、「2 4 6」と「1 3 5」の位置関係が前後しているために、 2 と 4 と 6 の3要素または 1 と 3 と 5 の3要素を移動しなければ答えになりそうにない。
たとえば初期数列が以下の通りだったら、
5 6 7 1 2 3 4 8 9
できるだけ長くなるようにピックアップした増加列は「5 6 7 8 9」と「1 2 3 4 8 9」の2本で、最長は6。
移動せずに済ませられるのが6要素で、他は必ず(ちょうど挿入ソートがソート列の中に挿入先を探して移動するのと同じように)移動させられる。仮に長さ6の増加列が2本あっても、移動せずに済ませられるのは6要素だけ。
たとえば、以下の初期数列に対して、先頭の要素から順に継ぎ足して木を作るとする。
1 3 2 5 4 6
しかしこれは網羅してないながらすでにして冗長。(画像ソース:verbose graph.dot)
ここが思案のしどころ。
[1,2,4,6]
になる。2番目の深さにおいて最善の要素は 2 であり、その他の 3, 4, 5 の後ろが 2 の後ろより長くなることはない。新しい要素は作業配列の末尾に付け加えられたり、既存の要素をより小さい値で置き換えたりする。
数列を先頭から処理するときの作業配列の変遷:[1]
→ [1,3]
→ [1,2]
→ [1,2,5]
→ [1,2,4]
→ [1,2,4,6]
提出一覧を見ると 227 ms というのはいかにも遅い。
ちらちらスクリプトの中身を見てると、二分探索の使用が目につく。それで気をつけて作業配列を見てみると、どの時点でもソート済みの状態が保たれているようだった。
できるだけ増加列の長さを伸ばしたいから、作業配列の末尾から更新位置を探していたし、更新位置が見つからない場合も想定していたけど、どちらにも無駄があった。位置探索はソート済みなのを活かして対数時間で済ませられるし、書き込む位置は必ず見つかる。
たぶん値の重複のあるなしで二分探索の使い方が変わるけど、この問題では重複なしが制約に含まれている。最近「bsearch_index の使い分けが見事」と評したのはこの提出>#13393878。lower_bound とか upper_bound とか -1 とか。Ruby には区別がないけど。
凡人は一足飛びに答えにたどり着いたりはしない。しかしたどり着ける難易度ではあり、さらには提出した後でも発見があった。思わず日記に書きたくなる楽しさ。
特になんということもなかった。作業配列を深さ優先探索のあいだ使い回しするだけだった。
問題名で解説記事を検索してみると、LIS(※) に関して色々な方法があるなかで、自分が唯一知っている方法がぴたりとはまる幸運があったと言えそう。
※トランプ挿入ソートの解説記事を読むといやでも目に入るよね>LIS。ストレートな知識問題だって書いてるところがあったけど、知らなくても解けるし、むしろ問題を通して教えてもらえる、ありがたくも教育的な問題だった。
最終更新: 2020-07-10T21:58+0900
2番目が 60 ms のところ、1番速い提出が 16 ms で済ませてしまっている。いったいどんな魔法を使ったのか、読んでみた。
といっても、require 'matrix'
して pow
(power 累乗) して mul
(multiply 乗算) してるだけに見える。優れたコードはストレートで無駄がない。あえて mul を定義しているのは途中で mod を取りたいからなのかなんなのか。
require 'matrix'
には NArray や NumPy で得られるような恩恵はないと思う。累乗の高速化手法に掛け算の回数をおよそ log2(N) 回に減らす方法があって、最初の掛け算で2乗を作り、次に2乗と2乗で4乗を作り、という感じに倍々で N 乗に迫っていく。
途中の式がどんな掛け算と足し算と係数になるか想像もできないけど、トリボナッチ数列の第 N+3 項を求めるための N 回の計算を約 log2(N) 回に縮めるための行列であり、pow メソッドであるのだと思う。
これぞ線形代数って感じ(すくなくとも自分がイメージできる範囲の)。
素朴な手法から順番に紹介されている。1.再帰 2.配列メモ 3.三変数使い回し 4.行列の累乗
実際は自分の到達点の低さの反映に過ぎない。
最初に読んだときは動的計画法のラッシュで頭がパンクして「もういいです……」と本を閉じた。
その次に開いたときは実装したことのあるグラフアルゴリズムの登場に気をよくしていたところで、ここからが中級だ、と新しいチャプターが始まって、「もう無理です……」と本を閉じた。
182ページのコラムから
もっと高速な漸化式の計算
実は、m 項間漸化式の n 項目は行列を用いるのではなく、各項を初項の線形結合で表して繰り返し二乗法を行うことにより、O(m^2log(n)) で計算することも可能です。興味のある人は考えてみるとよいでしょう。