公式

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 から抜ける。

このアルゴリズムは (文字列の長さ) \(\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)

投稿日時:
最終更新: