AtCoder が提供しているABC（AtCoder Beginner Contest）283 のD問題をC++とPythonで解いてみました。ABC283は、2022年12月24日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
D問題 Scope（Difficulty : 453）
問題はリンク先をご覧ください。
与えれた文字列をある条件で読み進めていく問題です。AtCoder Problems による Difficulty は、453 でした。
解答案
まず、文字 ‘a’ にだけ注目します。’a’ の個数を格納する変数を2種類用意します。
- ‘a’ の箱に入っているボールの数をカウントする count
- ‘(‘ と ‘)’ に囲われたレベル（depth）と組みで ‘a’ の箱に入っているボールの数をカウントする配列 count_d[depth]
文字列を走査して、左カッコ ‘(‘、右カッコ ‘)’、注目している文字 ‘a’ の場合に、以下を行います。
左カッコ ‘(‘ を検出した場合
- 囲われたレベル（depht）を増やす。
- count_d[depth] を初期化する。
右カッコ ‘)’ を検出した場合
- count から count_d[depht] を引く。
- count_d[depth] を初期化する。
- 囲われたレベル（depth）を減らす。
文字 ‘a’ を検出した場合
- count が 0 より大きければ、問題の制約（箱にすでにボールが入っている）により高橋君が失神します。この場合、”No” を出力します。
- それ以外であれば、count と count_d[depth] を増やす。
文字列を最後まで走査して、”No” を出力する条件を満たしてなければ “Yes” を出力します。
C++ プログラム例（ABC283D）
‘a’ から ‘z’ までの英小文字に対して、上記の解答案に従い文字列を走査します。
#include <bits/stdc++.h>
using namespace std;
int main()
{
string s;
cin >> s;
bool result = true;
for (char c = 'a'; c <= 'z'; ++c) {
int count = 0;
int depth = 0;
vector<int> count_d(s.length());
count_d[0] = 0;
for (int i = 0; i < s.length(); ++i) {
if (s[i] == '(') {
++depth;
count_d[depth] = 0;
} else if (s[i] == ')') {
count -= count_d[depth];
count_d[depth] = 0;
--depth;
} if (s[i] == c) {
if(count > 0) {
result = false;
} else {
++count;
++count_d[depth];
}
}
}
}
if (result) {
cout << "Yes" << endl;
} else {
cout << "No" << endl;
}
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC283D）
C++ プログラムに従い書き換えました。
"""AtCoder Beginner Contest 283 D"""
s = input()
result = True
count_d = [0] * len(s)
for c in range(26):
count = 0
depth = 0
count_d[0] = 0
letter = chr(ord('a') + c)
for i in range(len(s)):
if s[i] == '(':
depth += 1
count_d[depth] = 0
elif s[i] == ')':
count -= count_d[depth]
count_d[depth] = 0
depth -= 1
elif s[i] == letter:
if count > 0:
result = False
else:
count += 1
count_d[depth] += 1
print("Yes" if result else "No")Python らしくするために2点変更します。
- 英小文字は、あらかじめ定義されている string.ascii_lowercase を使う。
- 文字列を for 文でループさせる場合、enumerate を使う。
後者の変更点は、pylint が出力する警告に従いました。主な変更点の背景色を変更しておきます。
"""AtCoder Beginner Contest 283 D"""
import string
s = input()
result = True
count_d = [0] * len(s)
for i, letter in enumerate(string.ascii_lowercase):
count = 0
depth = 0
count_d[0] = 0
for j, ch in enumerate(s):
if ch == '(':
depth += 1
count_d[depth] = 0
elif ch == ')':
count -= count_d[depth]
count_d[depth] = 0
depth -= 1
elif ch == letter:
if count > 0:
result = False
else:
count += 1
count_d[depth] += 1
print("Yes" if result else "No")どちらも「AC」と判定されました。ただし、どちらの Python プログラムも C++（実行時間約50ms）に対して、時間がかかりました（実行時間 1600～1700ms 程度）。
最後に
この問題は、時間内に解くことができました。しかし、配列の大きさの制約条件を間違えたり、再初期化が漏れたため、WA 判定を2回受けました。また方針を考えるためにかなりの時間を使いました（73:29 に AC 判定）。このような実装中心の問題は、要領よく解けるようになりたいです。
この問題の採点データの入力ファイルに不備があったようです。深夜にも関わらず、即時の対応がされました。競技プログラミングを楽しむ立場からは、文字通り ありがたい と感じました。
引き続き ABC の問題を紹介していきます。
