Organize Your Train part II 解説

アルゴリズムの概略

与えられた文字列を2つに分割し,それぞれを「そのままor反転」と「そのまま連結or逆に連結」という操作によって生成できる文字列が何種類あるかを数え上げる問題。 文字列処理の問題といえます。 C++であれば,string クラス(文字列を扱えるクラス)と set クラス(集合を扱えるクラス)を使えば簡単です。

アルゴリズムとしては,まず全ての位置で文字列をheadとtailに2分割するループを回します。 次いで,反転操作「headそのまま&tailそのまま」,「head反転&tailそのまま」, 「headそのまま&tail反転」,「head反転&tail反転」の4種類×連結操作「head + tail」,「tail + head」の2種類, 計8種類の操作を行ったものを set に注ぎ込んでいきます。 最後に set に入っている数を出力すれば終わりです。

アルゴリズムの計算量

文字列の反転操作や連結操作はたかだか O(L) で終わります。 外側の分割のループも O(L) なので,文字列の分割・反転・連結操作全体としては O(L2) になります。 文字列の長さ L <= 72 なので生成される文字列の種類数は最大でも 8種類×722 = 41,472 程度になります。

さて,問題は(setに挿入したときの)重複判定の計算量なのですが,これの具体的な計算量は実装依存です。 とはいっても,普通は二分木のようなアルゴリズムで実装されていると思うので, キー値の比較に必要な時間 O(L) を含めても平均的にはたかだか O(L log2 n) 程度の計算量で挿入ができるはずです。 従って全体では,平均的に10,000個程度がsetに挿入されているという実際よりも相当悪い状況を想定したとしても, (8×722)×(72×log2 10,000) = 38,817,792 の定数倍程度で一つのデータに解答できます。

…確かに現実時間内で確実に結果を出せますが,けっこう大きいですね。 実際には L=72 のときでもこの10分の1~100分の1程度の計算量にしかならないと思いますが。 実際にはどうか知りませんが,問題的には「重複判定アルゴリズムを O(L×n)」にしても(つまりCで簡易的なものを実装しても)解けるように作ってある気はします。

アルゴリズムの実装

ライブラリの利用方法を覚えておきましょう。 本番ではライブラリの利用方法が簡単に書いてある印刷物を持ち込んでもいいでしょう。

C++であれば,GCCのg++が使えることを想定しておいて大丈夫です。 STLを含めてg++が標準で持つライブラリが全て使えます。

$Id: index.shtml 1335 2007-03-01 09:06:39Z SYSTEM $