｢珠玉のプログラミング｣のコラム2を再読した

チュートリアル記事を書いていたら懐かしくなったので、思わず続きを読むなどした。
コラム2は以下の3つの問題を扱っている。

- ある範囲の数値で抜けているものを探す。(同じものは一回だけ出現)
- 文字列の先頭のn文字を末尾にくっつける。
- ある単語とアナグラムの関係になっている単語を辞書から探す。

どれもよく見る問題だけれど改めて見てみると大切な事がたくさん詰まっている良い問題ばかり。

最初の問題は二分探索で解く。最初にデータを中央値より小さいものと大きいものに振り分けて2つの集合を作る。すると2つの集合でサイズが小さい方には確実に抜けがあるので、小さい集合に対して同じ処理をする、というのを繰り返す。この他にも、二分探索はプログラミングのデバッグなどで日常的に使える便利な方法だということが書いてある。というか実際よく使う。
2つめの問題はまずn文字目までを反転、n+1文字目から後ろを反転、最後に全体を反転させる。とすれば解ける。他にもいくつか手法が紹介されているが複雑なものが多い。優れた手法は単純なものが多いという話。あとは各手法に共通しているのは、いずれも単純な操作の組み合わせで実現されているということ。
最後の問題は各単語を構成する文字でソート(apple => aelpp)してから、辞書全体をソートするとアナグラムの関係にある単語が並ぶ、という話。ソートをソート目的ではなく、正規化(aelppのように文字順に並べた単語のこと)された単語を一箇所に集めるのに用いているのがポイント。この手法はProjectEulerとかでもよく使った記憶がある。