AtCoder

ABC301 A問題(Overall Winner)を解く

AtCoder_ABC301_A

AtCoder が提供しているABC(AtCoder Beginner Contest)301 のA問題をC++とPythonで解いてみました。ABC301は、2023年5月13日21:00に実施されました。

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

A問題 Overall Winner(Difficulty : 19)

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

ABC301 A問題 Overall Winner

文字列から勝ち負けを判定する問題です。AtCoder Problems による Difficulty は 19 でした。

解答案

問題は以下です。

  • ‘T’ と ‘A’ から成る文字列を読み込む。
  • ‘T’ の方が多ければ ‘T’ を、’A’ の方が多ければ ‘A’ を総合勝者として出力する。
  • ‘T’ と ‘A’ の数が同じであれば、先にその数に到達した方を総合勝者として出力する。

C++ プログラム例(ABC301A)

先に総合勝者になる勝ち数を計算しておきます。文字列の長さが奇数の場合と偶数の場合で異なりますが、変数 win に格納しておきます(11-16行目)。

文字列を走査して、T の勝ち数(t_win)と A の勝ち数(a_win)を更新します。更新後の勝ち数が win 以上になっていれば、総合勝者を出力して終了します。

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

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

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

	int win;
	if (n % 2 == 1) {
		win = n / 2 + 1;
	} else {
		win = n / 2;
	}

	int t_win = 0;
	int a_win = 0;
	for (int i = 0; i < n; ++i) {
		if (s[i] == 'T') {
			++t_win;
		} else {
			++a_win;
		}
		if (t_win >= win) {
			cout << "T" << endl;
			return 0;
		}
		if (a_win >= win) {
			cout << "A" << endl;
			return 0;
		}
	}

	return 0;
}

AC(Accepted=正しいプログラム)と判定されました。

Python プログラム例(ABC301A)

Python 版は C++ 版をそのまま移植しました。

"""AtCoder Beginner Contest 301 A"""
n = int(input())
s = input()

if n % 2 == 1:
    win = n // 2 + 1
else:
    win = n // 2

t_win = 0
a_win = 0
for i, ch in enumerate(s):
    if ch == 'T':
        t_win += 1
    else:
        a_win += 1
    if t_win >= win:
        print("T")
        break
    if a_win >= win:
        print("A")
        break

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

最後に

ABCの開催が300回を超えました。気分を新たにして参加を楽しみたいと考えています。

ABC301 について、引き続き問題を紹介していきます。

COMMENT

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

CAPTCHA