第７回日本情報オリンピック　予選４

2007年12月16日
情報オリンピック日本委員会

解説

反復を用いた基本的な問題である．どのような繰り返しを用いるかという点で少しだけ工夫を要するかもしれない．

基本的には，すべての平行移動の仕方を一つずつ試して，一致する個所を見つけたら出力すればよい．ただし，「すべての平行移動の仕方」は無限にあるので文字通りにすべてを試すのは不可能である．探すべき星座の中の任意の1点を選んで特別扱いし，この点が写真の中の n 個の星の一つに一致するように平行移動する方法をすべて考えれば，平行移動の仕方として高々 n 通り試せばよいことがわかる．

n 通りの平行移動の仕方を一つずつ試すと決まれば，実際に必要なことは，平行移動後の星座のすべての点が写真に含まれるかどうかを調べることである．含まれていれば平行移動した量を出力して終了し，含まれていなければ次の平行移動の仕方を試せばよい．

素朴に写真の星の座標を与えられたまま長さ n の配列で記憶した場合，ある点が写真に含まれるかどうかを調べるのに O(n) 時間かかるので，星座全体が含まれるかどうかを調べるには O(mn) 時間かかる．平行移動の仕方は O(n) 通りあるので，全部で O(mn²) 時間かかることになる．この方法で，各入力に対し高々10秒程度プログラムを実行すれば解ける．

予選では実行時間に制限がないので，この方法で満点を取るのは難しくないはずである．

発展

少し工夫することで，上に述べた方法より高速なアルゴリズムを作ることができる．予選のこの問題では，このような工夫は要求していないが，実際にプログラムを書いて利用しようと思ったら，状況によっては高速化を求められる場合もあるだろう．興味のある人のために，以下では高速化のための方法の概略を述べる．

写真の星の座標を単に与えられたまま配列で記憶するのではなく，この部分の記憶方法 (データ構造) を工夫しておくことで，後で星座のすべての点が写真に含まれるかどうかを調べるのにかかる時間を短縮するのが有効である．このように，後の処理の効率化のために前もって工夫しておくことを前処理という．

写真の星の座標を辞書式順序でソートして覚えておくと，ある点が写真に含まれるかどうかを調べるのに二分探索を用いることができ， O(n) 時間ではなく O(log n) 時間で済む．このため，全体の計算量は O(mn²) 時間から O(mn log n) 時間に改善する．

また，写真の星の座標をハッシュテーブルを用いて記憶しておくと，ある点が写真に含まれるかどうかを調べるのは，運が悪くない限り定数時間で済む．このため，全体の計算量は O(mn) 時間に改善する．

なお，ある点が写真に含まれるかどうかを座標を添え字とする2次元配列で記憶しておけば，ある点が写真に含まれるかどうかの判定は定数時間で行えるが，座標の範囲が x 座標・ y 座標とも 0 以上 1000000 以下と広いので，この方法は現実的ではない．この方法でも部分点が取れるよう，入力 1 と入力 2 は座標の範囲を 0 以上 1000 以下に制限してある．