AtCoder

ABC283 D問題(Scope)を解く

AtCoder_ABC283_D

AtCoder が提供しているABC(AtCoder Beginner Contest)283 のD問題をC++とPythonで解いてみました。ABC283は、2022年12月24日21:00に実施されました。

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

D問題 Scope(Difficulty : 453)

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

ABC283 D問題 Scope

与えれた文字列をある条件で読み進めていく問題です。AtCoder Problems による Difficulty は、453 でした。ABC D問題として、標準的な問題です。

解答案

まず、文字 ‘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 を解いていきます。

COMMENT

メールアドレスが公開されることはありません。 が付いている欄は必須項目です

CAPTCHA