計算速度が至上命令か 。本問題のプログラム実行制限時間はついに0.666秒に設定されてしまった。自分としては嫌なんだね、はっきりと。

アルゴリズムの優劣性については、実行速度がとても大事だが、可読性、そこからの発展性、理解しやすさ、など場面や用途によって様々なものがあっていいはず。ソートアルゴリズムについても、O(N)のものがあっても、ソートの本質を理解する上では、様々なものが用意されている。実行制限時間をきつく設定したら、アルゴリズムの強制採用にほかならない。大反対だね。

1. 問題文
n (1<=n<=10000) 個のデータ (整数、10進8桁以内、負数もありえる)が与えられている。さらに、様々な値m (1<=m<=n) が与えられ、m個のLISシーケンス(Longest Increasing Subsequence、最長単調増加シーケンス)をデータからピックアップして表示せよ、というのが問題の意味。なお、LISシーケンスはなるべくデータの先頭にあるものを選択しないといけない。

2. 実例
例えば、以下のn=10個のデータがあったとする。m=1,2,3,…10のLISシーケンスはそれぞれ以下の通り。

-3 19 12 -7 18 23 -5 0 11 22

m=1 LIS=-3

m=2 LIS=-3 19

m=3 LIS=-3 19 23

m=4 LIS=-3 12 18 23

m=5 LIS=-7 -5 0 11 22

m>5 LISは存在しない

3. 計算法
O(nlogn)バージョンのLISアルゴリズムを使う。ブログに紹介があるので、参照されたい。

つまり、n個のデータに対するそれぞれのLIS長をまず算出する。上の実例では、次になる。

data (-3 19 12 -7 18 23 -5 0 11 22)

LIS (4 2 3 5 2 1 4 3 2 1)

最長LISは5という結果も上のLISテーブルから分かる。

つぎに、それぞれのmに対して、そのLISシーケンスをピックアップする。

m=1 LIS1=4 >= 1 なので、data1=-3がその結果。
m=2 LIS1=4 >= 2、LIS2=2 >= 1 しかも data2=19 > data1なので、-3 19が結果になる。
m=3 LIS1=4 >=3、LIS2=2 >=2 しかも data2 > data1、data2=19がLISシーケンス2番目のものになる。さらに、LIS3=3 は 1以上だが、値はdata2以下なので、却下。LIS4, 5も同様の理由で却下。LIS6=1が1以上だし、値data6=23は19よりも大きいので、3番目はdata6になる。
m=4については、data2=19のLIS2は2なので、3よりも小さいことから、2番目にはならない。隣のdata3=12が2番目になる。つぎの12よりも大きく、LISの値が2以上のものは18なので、3番目になる。4番目は18よりも大きく、LISの値が1以上のもの、つまり、23となる。
m=5については省略するが、先頭からまずLISの値が5よりも大きいものを探し、-7を取る。つぎに-7よりも値が大きく、LISの値が4よりも大きいものを取る。

全体の実行時間は、LISテーブルの算出にO(nlogn)、LISシーケンスの抽出にO(n)でできるので、全体でもO(nlogn)になる。

4. 結果
入力部分を工夫して、最終的にランク1位の実行速度と同じにした。出力部分はprintf()をつかったままなので、まだ余力は残っているが、誤差範囲内の時間(0.01秒)を縮めても意味ないので、そのままにしておいた。

ともかく、スピードが命という風潮に強く警告したい気持ちでいっぱい。いくらなんでもやり過ぎだな。

Comments are closed.

Post Navigation