AtCoder が提供しているABC（AtCoder Beginner Contest）311 のB問題をC++とPythonで解いてみました。ABC311は、2023年7月22日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
B問題 Vacation Together（Difficulty : 67）
問題はリンク先をご覧ください。
全員の予定を調べてから、連続する暇な日数を調べます。AtCoder Problems による Difficulty は 67 でした。
解答案
以下の2段階に分けて考えます。
- 全員が暇な日（’o’）と、それ以外の日（’x’）を計算しておきます。
- 計算した結果から、’o’ が連続する一番長い列を見つけて、その長さを出力します。
C++ プログラム例（ABC311B）
先に全員の予定を文字列 result_str に格納しておきます（13ー26行目）。
- 全員の予定が ‘o’ の日は、result_str のその日を ‘o’ とする。
- ひとりでも予定が ‘x’ の人がいる日は、result_str のその日を ‘x’ とする。
変数 result_str から一番長い ‘o’ の列を探します。これは定番コードとなります（28ー37行目）。定番コードでは以下を行っています。
- 文字が ‘o’ の場合、変数 now をインクリメントして、最大値（result）を更新する。
- 文字が ‘x’ の場合、変数 now を0にリセットする。
以下が、C＋＋プログラムとなります。
#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];
}
string result_str = "";
for (int i = 0; i < d; ++i) {
bool this_time = true;
for (int j = 0; j < n; ++j) {
if (s[j][i] != 'o') {
this_time = false;
}
}
if (this_time) {
result_str += 'o';
} else {
result_str += 'x';
}
}
int result = 0;
int now = 0;
for (int i = 0; i < d; ++i) {
if (result_str[i] == 'o') {
++now;
result = max(result, now);
} else {
now = 0;
}
}
cout << result << endl;
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC311B）
C++ のコードを移植しました。全体の予定を変数 result_str に格納して、この文字列に含まれる ‘o’ の連続する一番長い列の長さを調べることも同じです。
"""AtCoder Beginner Contest 311 B"""
n, d = map(int, input().split())
s = [input() for i in range(n)]
result_str = ""
for i in range(d):
this_time = True
for j in range(n):
if s[j][i] != 'o':
this_time = False
result_str += 'o' if this_time else 'x'
result = 0
now = 0
for i in range(d):
if result_str[i] == 'o':
now += 1
result = max(result, now)
else:
now = 0
print(result)こちらも「AC」と判定されました。
最後に
適切な前準備（全員の日程計算）をしておくことによって解きやすくなったと考えています。「条件をみたす一番長い列を見つけよ」も定番として捉えておくと、つまらない間違いが減ると思います。
引き続き ABC の問題を紹介していきます。
