ABC299 C問題（Dango）を解く

AtCoder が提供しているABC（AtCoder Beginner Contest）299 のC問題をC++とPythonで解いてみました。ABC299は、2023年4月22日21:00に実施されました。

この回は、外部からDDoS攻撃を受けてサーバが不安定になり unrated となりました。

AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。

C問題 Dango（Difficulty : 280）

問題はリンク先をご覧ください。

ABC299 C問題 Dango

与えられた文字列に含まれる特定の文字が連続する回数を答える問題です。AtCoder Problems による Difficulty は 280 でした。

解答案

問題文から、以下について解答することが読み取れました。

• 文字 ‘o’ が一つもない場合は、-1 を出力する。
• 文字 ‘-‘ が一つもない場合は、-1 を出力する。
• 上記以外の場合、文字 ‘o’ が連続する最大の回数を求めて出力する。

C++ プログラム例（ABC299C）

文字列を走査して、以下の処理を行います。

• ‘o’ の場合: 一時変数 count を増やして、count が最大の場合、result を更新する（15-18行目）。
• ‘-‘ の場合: count を0にリセットして、- が現れたことを示すフラグ（is_minus_exist）をセットする（21、22行目）。

実際には、文字は2種類であるため、後者は else 節で処理しています。

以下が、C＋＋プログラムとなります。

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

int main()
{
	int n;
	cin >> n;
	string s;
	cin >> s;

	int result = -1;
	bool is_minus_exist = false;
	int count = 0;
	for (int i = 0; i < n; ++i) {
		if (s[i] == 'o') {
			++count;
			if (count > result) {
				result = count;
			}
		} else {
			count = 0;
			is_minus_exist = true;
		}
	}

	if ((is_minus_exist)&&(result > 0)) {
		cout << result << endl;
	} else {
		cout << -1 << endl;
	}

	return 0;
}

AC（Accepted＝正しいプログラム）と判定されました。

Python プログラム例（ABC299C）

C++のロジックをそのまま Python に書き直しました。

"""AtCoder Beginner Contest 299 C"""
n = int(input())
s = input()

result = -1
is_minus_exist = False
count = 0
for i, ch in enumerate(s):
    if ch == 'o':
        count += 1
        if count > result:
            result = count
    else:
        count = 0
        is_minus_exist = True

if is_minus_exist and result > 0:
    print(result)
else:
    print(-1)

こちらも「AC」と判定されました。

最後に

問題文を読み替えれば、’o’ が連続する回数をカウントする問題であることが分かります（いくつかの例外がありますが）。問題の読み替えにより解きやすくなる問題でした。

引き続き ABC の問題を紹介していきます。