AtCoder ABC 311 B - Vacation Together (灰色, 200 点)

二次元配列を活用する練習問題。また、「条件が連続する区間」を求める練習問題でもある。

• 問題へのリンク

問題概要

のグリッドが与えられる。各マスの値は 'o' か 'x' のいずれかである。

「どの行も文字 'o' であるような列」が最長で何個連続するかを求めよ。

考えたこと

一般に、 個のものが横に一列に並んでいるとき、条件を満たすものが最長で何個連続しているかを求める処理は、次のような for 文で実現できる。

int res = 0;  // 最長記録
int length = 0;  // 現在何個連続しているかを表す変数
for (int i = 0; i < D; ++i) {
    if (i 番目の物が条件を満たす) {
        ++length;
        res = max(res, length);  // 最長記録を更新するなら更新する
    } else {
        length = 0;
    }
}

今回の問題においても、「i 番目の物が条件を満たす」かどうかを判定する部分をきちんと実装すれば正解できる！

コード

#include <bits/stdc++.h>
using namespace std;

int main() {
    int N, D;
    cin >> N >> D;
    vector<string> S(N);
    for (int i = 0; i < N; ++i) cin >> S[i];
    
    int res = 0;  // 最長記録
    int length = 0;  // 現在何個連続しているかを表す変数
    for (int i = 0; i < D; ++i) {
        // i 日目が条件を満たすかを調べる
        bool ok = true;
        for (int j = 0; j < N; ++j) {
            if (S[j][i] != 'o') ok = false;
        }
        
        if (ok) {
            // i 日目が条件を満たすとき
            ++length;
            res = max(res, length);
        } else {
            length = 0;
        }
    }
    cout << res << endl;
}