A - First ABC 解説
by
Nyaan
初心者の方へ
- プログラミングの学習を始めたばかりで何から手をつけるべきかわからない方は、まずは practice contest の問題A「Welcome to AtCoder」をお試しください。言語ごとに解答例が掲載されています。
- また、プログラミングコンテストの問題に慣れていない方は、 AtCoder Beginners Selection の問題をいくつか試すことをおすすめします。
- C++入門 AtCoder Programming Guide for beginners (APG4b) は、競技プログラミングのための C++ 入門用コンテンツです。
この問題は文字列型を適切に走査することができるかを聞いている問題です。
問題文を手続き的に言い換えると次のようになります。
- 「
A
が出現したか」「B
が出現したか」「C
が出現したか」を True/False のフラグで管理する。はじめ 3 つのフラグはFalse
の状態である。 - \(i=1, 2, \dots, N\) の順に for-loop を回す。for-loop 内では次の操作を行う。
- \(S\) の \(i\) 番目の文字を \(x\) とする。「
x
が出現したか」に対応するフラグをTrue
にする。 - 3 つのフラグ全てが初めて True になったとき、答えは \(i\) である。よって \(i\) を出力して for-loop から抜ける。
- \(S\) の \(i\) 番目の文字を \(x\) とする。「
このアルゴリズムは (文字列の長さ) \(\leq 100\) 回のステップ数しか掛からないアルゴリズムなので十分高速ですから、これをそのまま実装すればよいです。実装に関しては、C++ や Python では文字列の \(i\) 文字目 (ただしこの \(i\) は \(0\) 始まり) を S[i]
で取得できることを知っていれば、for-loop を利用して実装することができます。
- 実装例 (Python 3)
N = int(input())
S = input()
exist_a, exist_b, exist_c = False, False, False
for i in range(N):
if S[i] == 'A': exist_a = True
if S[i] == 'B': exist_b = True
if S[i] == 'C': exist_c = True
if exist_a and exist_b and exist_c:
print(i + 1)
break
いくつか別の解法もあるので簡単に紹介します。
1 つは現れた文字を集合型 set
で管理する方法です。A
, B
, C
すべてが現れているということは、既に現れた文字が 3 種類であることと同値です。よって、上述のアルゴリズムのうち、\(i\) が答えかどうかを判定する部分で「現れた文字集合のサイズが \(3\) であるか?」を判定すればよいです。
- 実装例 (Python 3)
N = int(input())
S = input()
A = set()
for i in range(N):
A.add(S[i])
if len(A) == 3:
print(i + 1)
break
別の方針もあります。\(a, b, c\) を次のように置きます。
A
が初めて登場する位置を \(a\),B
が初めて登場する位置を \(b\),C
が初めて登場する位置を \(c\)
このとき、実は答えは \(\max\lbrace a,b,c\rbrace\) になります。よって \(a, b, c\) を計算して \(\max\) を取れば答えを計算できます。\(a,b,c\) は C++ や Python の文字列型のメンバ関数 find
を利用すれば容易に実装できます。
- 実装例 (Python 3)
N = int(input())
S = input()
print(max(S.find(c)for c in "ABC") + 1)
投稿日時:
最終更新: