危険な区域

問題の概要

縦 \(H\) 行、横 \(W\) 列の区域があり、各区域は X(危険)または .(安全)です。上から順に見ていったとき、最初に X を \(1\) つ以上含む行が何行目かを求めます。X が \(1\) つも存在しない場合は -1 を出力します。

アルゴリズム

行を上から順番に \(1\) 行目から \(H\) 行目まで走査し、各行について X が含まれるかどうかを調べます。最初に X を含む行が見つかった時点で、その行番号(\(1\) 始まり)を答えとして出力し、走査を打ち切ります。最後まで X が見つからなかった場合は -1 を出力します。

実装は非常に単純です。

• C++ では string::find('X') が string::npos でないかどうかで判定します。
• Python では 'X' in s で判定します。

答えを保持する変数 ans を -1 で初期化しておき、見つかった行で上書きします(C++)。あるいは、見つかった時点で break し、見つからなければ初期値 -1 のまま出力します(Python)。

正しさの証明

補題: アルゴリズムが行 \(i\) を出力するのは、行 \(i\) が X を含み、かつ \(1\) 行目から \(i-1\) 行目までのすべての行が X を含まない場合に限る。

証明: ループは \(i = 1, 2, \ldots\) の順に各行を調べる。行 \(i\) で X が見つかった時点で出力して打ち切るので、出力された \(i\) 自身は X を含む。また、それ以前の行 \(1, \ldots, i-1\) では打ち切られずにループが継続したということは、それらの行には X が含まれていなかったことを意味する。逆に、条件を満たす最小の行 \(i\) では、それ以前の行では打ち切られないため必ず行 \(i\) まで到達し、そこで出力される。

定理: アルゴリズムは正しい出力を行う。

証明: 補題より、X を含む行が存在する場合、出力されるのはそのような行のうち最小のものであり、これは問題文の「上から順に見て最初に危険な区域を含む行」の定義と一致する。X を含む行が存在しない場合、ループは一度も打ち切られずに終了し、初期値 -1 が出力される。これも仕様と一致する。

計算量

• 時間計算量: \(O(HW)\)。各行を高々 \(1\) 回走査し、各行の判定は \(O(W)\)。実際には最初に X を含む行で打ち切るため、これより高速になることもある。
• 空間計算量: C++ 版は各行を読むたびに前の行を捨てるため補助空間は \(O(W)\)。Python 版は入力を一括で読み込むため \(O(HW)\)。いずれにせよ \(H, W \leq 10\) なので問題ない。

タイブレークについて

X を含む行が複数ある場合、上から順に走査して最初に見つかった(すなわち行番号が最小の)行を出力します。これは問題文の仕様そのものであり、追加のタイブレーク規則はありません。