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

脳log[20200602] AtCoder Beginner Contest 006/D 問題 トランプ挿入ソート | AtCoder Beginner Contest 006/B 問題 トリボナッチ数列



2020年06月02日 (火)

最終更新: 2020-06-18T09:50+0900

[AtCoder] AtCoder Beginner Contest 006D 問題 トランプ挿入ソート

ちょっと日記に書きたくなるような、適度に歯応えのある問題だった。問題は、例えば

2 4 6 1 3 5 

のような数列が与えられたときに、

1 2 3 4 5 6

のように昇順に並べ替えるためには、いくつの要素を移動する必要があるか、その最小を答えるというもの。

 1. 連続する2要素に注目して増加しているか減少しているか見てみたら?

例えば、「2 4 6」「1 3 5」の並びは2要素間の関係において増加しているのでそのまま温存して答えにできるのではないか、逆に、「6 1」の並びは減少しているので必ず介入して解消しなければいけない。

しかし2つの増加列の関係に注目すると、「2 4 6」と「1 3 5」の位置関係が前後しているために、 2 と 4 と 6 の3要素または 1 と 3 と 5 の3要素を移動しなければ答えになりそうにない。

 2. 数列全体から最長の増加列(※要素は連続してなくていい)を1つだけピックアップしたものが答えの一部になるのでは?

たとえば初期数列が以下の通りだったら、

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要素だけ。

 3. どのようにして最長の増加列の長さを知るか。ツリーを作る?

たとえば、以下の初期数列に対して、先頭の要素から順に継ぎ足して木を作るとする。

1 3 2 5 4 6

しかしこれは網羅してないながらすでにして冗長。(画像ソース:verbose graph.dot)

ここが思案のしどころ。

  1. ある要素の後ろにいくつの要素が続くかは、その要素の値によって決まる。
  2. だから 4 と 5 と 6 が複数回出現しているが、最も深いところの1つ以外は無用。
  3. くっつけられる場所を見つけるために、そのうちのどこにくっつけるのが最善かを知るために、都度都度葉を根まで(あるいは根から葉まで)たどるのはいかにも無駄。
  4. 知りたいのは深さだけ、それも最大の。中途半端はいらないし、経路もいらない。
  5. どの枝がどれだけ伸びうるかは 1 に書いた通り。さらに言えば値は小さいほど良く、小が大を兼ねる。
  6. 深さごとに最善の要素(最小の値)を1つ記憶しておけば足りる。
  7. たとえば上の画像に対応する作業配列は [1,2,4,6] になる。2番目の深さにおいて最善の要素は 2 であり、その他の 3, 4, 5 の後ろが 2 の後ろより長くなることはない。
  8. 新しい要素は作業配列の末尾に付け加えられたり、既存の要素をより小さい値で置き換えたりする。

    数列を先頭から処理するときの作業配列の変遷:[1][1,3][1,2][1,2,5][1,2,4][1,2,4,6]

 提出 #13936266 (AC / 227 ms / 4348 KB)

提出一覧を見ると 227 ms というのはいかにも遅い。

Ruby による提出(実行時間昇順)

ちらちらスクリプトの中身を見てると、二分探索の使用が目につく。それで気をつけて作業配列を見てみると、どの時点でもソート済みの状態が保たれているようだった。

できるだけ増加列の長さを伸ばしたいから、作業配列の末尾から更新位置を探していたし、更新位置が見つからない場合も想定していたけど、どちらにも無駄があった。位置探索はソート済みなのを活かして対数時間で済ませられるし、書き込む位置は必ず見つかる。

たぶん値の重複のあるなしで二分探索の使い方が変わるけど、この問題では重複なしが制約に含まれている。最近「bsearch_index の使い分けが見事」と評したのはこの提出>#13393878。lower_bound とか upper_bound とか -1 とか。Ruby には区別がないけど。

 提出 #13936659 (AC / 41 ms / 2556 KB)

凡人は一足飛びに答えにたどり着いたりはしない。しかしたどり着ける難易度ではあり、さらには提出した後でも発見があった。思わず日記に書きたくなる楽しさ。

 AtCoder Beginner Contest 165F 問題 LIS on Tree

特になんということもなかった。作業配列を深さ優先探索のあいだ使い回しするだけだった。

 提出 #14435898 (AC / 707 ms / 259260 KB)

問題名で解説記事を検索してみると、LIS() に関して色々な方法があるなかで、自分が唯一知っている方法がぴたりとはまる幸運があったと言えそう。

トランプ挿入ソートの解説記事を読むといやでも目に入るよね>LIS。ストレートな知識問題だって書いてるところがあったけど、知らなくても解けるし、むしろ問題を通して教えてもらえる、ありがたくも教育的な問題だった。

最終更新: 2020-07-10T21:58+0900

[AtCoder] AtCoder Beginner Contest 006B 問題 トリボナッチ数列

Ruby による提出(実行時間昇順)

2番目が 60 ms のところ、1番速い提出が 16 ms で済ませてしまっている。いったいどんな魔法を使ったのか、読んでみた。

 提出 #1163397 (nejiko96 さん / 16 ms / 4732 KB)

といっても、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 メソッドであるのだと思う。

これぞ線形代数って感じ(すくなくとも自分がイメージできる範囲の)。

 Tribonacci Numbers - GeeksforGeeks

素朴な手法から順番に紹介されている。1.再帰 2.配列メモ 3.三変数使い回し 4.行列の累乗

  1. A simple solution is to simply follow recursive formula and write recursive code for it,
  2. Time complexity of above solution is exponential. A better solution is to use Dynamic Programming.
  3. Time complexity of above is linear, but it requires extra space. We can optimizes space used in above solution using three variables to keep track of previous three numbers.
  4. Below is more efficient solution using matrix exponentiation.

 蟻本にはすべてがあるような気がしてくるな。

実際は自分の到達点の低さの反映に過ぎない。

最初に読んだときは動的計画法のラッシュで頭がパンクして「もういいです……」と本を閉じた。

その次に開いたときは実装したことのあるグラフアルゴリズムの登場に気をよくしていたところで、ここからが中級だ、と新しいチャプターが始まって、「もう無理です……」と本を閉じた。

182ページのコラムから

もっと高速な漸化式の計算

実は、m 項間漸化式の n 項目は行列を用いるのではなく、各項を初項の線形結合で表して繰り返し二乗法を行うことにより、O(m^2log(n)) で計算することも可能です。興味のある人は考えてみるとよいでしょう。