概要

空席が最も多い行を求めます。同じ数の空席を持つ行が複数ある場合は、最も上の行を選びます。

考察

どの行にも座席は \(W\) 個あるため、各行について次の関係が成り立ちます。

\(空席数 = W - 人が座っている座席数\)

したがって、空席が最も多い行は、人が座っている座席が最も少ない行です。提示されたコードでは、各行の o の個数を数え、その個数が最小の行を探しています。

例えば、座席表が次の場合を考えます。

o.o.
....
.o..
....

各行の o の個数は順に \(2, 0, 1, 0\) 個です。最小なのは \(2\) 行目と \(4\) 行目なので、最も上にある \(2\) 行目が答えです。

すべての座席を調べても最大で \(10 \times 10 = 100\) 席なので、素朴に全探索しても十分高速です。

注意すべきなのは、同数の場合の扱いです。上から順に調べるとき、最小値と同じ場合にも答えを更新すると、より下の行を選んでしまい、誤答になります。これまでの最小値より小さい場合だけ更新することで、最も上の行を残せます。

アルゴリズム

1. これまでに見つかった着席数の最小値 bestSeated を、十分大きな値で初期化します。答えの行番号を idx に記録します。
2. 上から順に、行番号 \(i = 1, 2, \ldots, H\) について次を行います。
   • その行の文字列を読み込みます。
   • 文字列中の o の個数を数え、seated とします。
   • seated < bestSeated の場合だけ、bestSeated を seated に、idx を \(i\) に更新します。
3. idx を出力します。

この処理では、各行を調べ終えた時点で、idx は「そこまでの行のうち、着席数が最小で、最も上にある行」を表します。そのため、すべての行を調べ終えた後の idx が求める答えです。

計算量

• 時間計算量: \(O(HW)\)
  各行の \(W\) 文字を、\(H\) 行分調べます。
• 空間計算量: \(O(W)\)
  一度に保持するのは長さ \(W\) の文字列と、定数個の変数だけです。

実装のポイント

• bestSeated の初期値は、着席数の最大値 \(W\) より大きくします。コードでは 1 << 30 を使っており、最初の行で必ず更新されます。

• 更新条件は seated < bestSeated とします。<= にすると、同数の場合に下の行で上書きされてしまいます。

• 出力する行番号は \(1\) 始まりなので、コードでは行を調べるループも \(1\) から始めています。

• 空席がまったくない場合でも、すべての行の着席数が同じになるため、正しく \(1\) 行目が選ばれます。

  ソースコード

// 問題文から独立に実装: 着席数が最も少ない行（同数なら最初）を探す
#include <iostream>
#include <string>
int main() {
    int h, w; std::cin >> h >> w;
    int bestSeated = 1 << 30, idx = 0;
    for (int i = 1; i <= h; ++i) {
        std::string s; std::cin >> s;
        int seated = 0;
        for (int j = 0; j < w; ++j) if (s[j] == 'o') seated++;
        if (seated < bestSeated) { bestSeated = seated; idx = i; }
    }
    std::cout << idx << std::endl;
}

---

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