解説

問題の要約

\(H\) 行 \(W\) 列のマス目が与えられ、各マスは T（宝物あり）か .（何もなし）です。各行について、その行に T が \(1\) つ以上含まれるなら o、含まれないなら x として、上の行から順に並べた長さ \(H\) の文字列を出力します。

アルゴリズム

各行 \(S_i\) を順に読み込み、その行に文字 T が含まれるかどうかを判定します。

• 含まれる場合、答えの文字列に o を追加する。
• 含まれない場合、x を追加する。

全ての行を処理した後、できあがった長さ \(H\) の文字列を出力します。

C++ では S.find('T') != string::npos で判定し、Python では 'T' in S で判定します。

正しさの証明

主張: アルゴリズムが出力する文字列の \(i\) 文字目は、\(S_i\) に T が \(1\) つ以上含まれるとき、またそのときに限り o である。

証明: アルゴリズムは各行 \(i\) を独立に処理する。\(i\) 番目の反復では \(S_i\) のみを調べ、T が見つかれば o を、見つからなければ x を答えの \(i\) 文字目として追加する。文字列の走査は \(S_i\) の全文字を調べるので、T が存在すれば必ず検出され、存在しなければ検出されない。したがって \(i\) 文字目は仕様どおりに o または x となる。文字は上の行から順に追加されるため、出力文字列は要求された順序と長さ \(H\) を持つ。■

計算量

• 時間計算量: \(O(HW)\)（入力の読み込みを含む）。
• 空間計算量: C++ は \(O(H + W)\)、Python は \(O(HW)\)。入力・出力として保持する配列や文字列も含む。