平成２３年度副テーマ課題

「右方向直近上位要素発見問題に対する効率の良いアルゴリズムの開発」

最近のIT技術の急速な進歩によりメモリが大規模化したが，一方で問題サイズが巨大であるために記憶領域が十分に確保できずにアルゴリズム設計面で苦労することがある．大量のメモリを使うことに慣れてしまったプログラマにとっては制限されたメモリ環境でアルゴリズムを開発することは苦痛ですらある．ソフトウェア工学の分野では，スモールプログラムと呼ばれる概念の下に省メモリ・プログラミングの開発法も提唱されているが，アルゴリズム設計のレベルでも積極的な取り組みがあるかというと，そうとも言えないのが現状である．このような状況に鑑みて，本課題では，作業領域が制限された状況でのアルゴリズム設計について考える．
　具体的な問題として，右方向直近上位要素発見問題を考えよう．この問題では，配列A[1..n]に格納されたn個の要素それぞれについて，自分より大きな要素の中で，自分より右にあり（つまり自分より大きなインデックスをもち），かつ自分に（インデックス差の意味で）最も近い要素の位置（インデックス）を求めたい．たとえば，入力の配列が
A[1]=8, A[2]=4, A[3]=6, A[4]=3, A[5]=2, A[6]=1, A[7]=5, A[8]=7, A[9]=9
のとき，A[1]に対する右方向直近上位要素はA[9]=9であり，A[2]=4に対する右方向直近上位要素はA[3]=6である．
　問題１：　この問題をO(n)の作業領域を用いてO(n)時間で解くアルゴリズムを設計せよ．
　問題２：　この問題をO(1)の作業領域を用いてO(n log n)時間で解くアルゴリズムを設計せよ．
ただし，入力データを蓄えている配列A[ ]は読み出し専用であると仮定する．
下記の論文を参考にして，上記２問に答え，かつプログラムを作成せよ．

参考論文については副テーマ決定時に渡します．