概要

各行の空席 . の数を数え、空席数が最大となる行を求めます。同じ空席数の行が複数ある場合は、最も上の行を答えます。

考察

座りたい行を決めるには、各行に空席が何個あるかだけが分かれば十分です。空席の位置を調べる必要はありません。

すべての座席を確認する素朴な方法でも、調べる座席数は最大で \(10 \times 10 = 100\) 個なので、十分に間に合います。

注意が必要なのは、空席数が最大の行が複数ある場合です。例えば、上から順に空席数が \([2, 3, 3]\) なら、答えは \(2\) 行目です。最大値を見つけるたびに答えを上書きすると、下の行を選んでしまうことがあります。

そこで、各行の空席数を上から順にリストへ保存し、最大値が最初に現れる位置を求めます。これにより、最も上の行を選べます。

アルゴリズム

1. \(H, W\) を読み込みます。
2. 各行の文字列について、count('.') で空席数を数え、リスト empty に上から順に保存します。
3. max(empty) で、空席数の最大値を求めます。
4. empty.index(max(empty)) で、その最大値が最初に現れる位置を求めます。
5. リストの添字は \(0\) から始まるため、求めた位置に \(1\) を足して出力します。

empty は上から順に並んでいるため、最大値の最初の位置は、空席数が最大の行のうち最も上の行に対応します。

計算量

• 時間計算量: \(O(HW)\)
  各行の \(W\) 文字を調べる処理を \(H\) 回行います。最大値とその位置の探索はそれぞれ \(O(H)\) なので、全体では \(O(HW)\) です。
• 空間計算量: \(O(H + W)\)
  空席数のリストに \(O(H)\)、読み込み中の文字列に一時的に \(O(W)\) の領域を使います。

実装のポイント

• 空席を表す文字は . です。o の数ではなく、. の数を数えます。

• Python の list.index() は、指定した値が最初に現れる添字を返すため、同数の場合の条件も満たせます。

• 出力する行番号は \(1\) 始まりなので、添字に \(1\) を足すことを忘れないようにします。

• 全席が埋まっている場合も、空席数はすべて \(0\) となり、正しく \(1\) 行目が選ばれます。

  ソースコード

# 問題文から独立に実装: 各行の空席数のリストで最大値の最初の位置
h, w = map(int, input().split())
empty = [input().count('.') for _ in range(h)]
print(empty.index(max(empty)) + 1)

この解説は gpt-6-astra-medium によって生成されました。