Official

A - First ABC Editorial by en_translator


For beginners
  • If you are new to learning programming and do not know where to start, please try Problem A "Welcome to AtCoder" from practice contest. There you can find a sample code for each language.
  • Also, if you are not familiar with problems in programming contests, we recommend you to try some problems in "AtCoder Beginners Selection".
  • 競プロ典型 90 問」(Typical 90 Problems of Competitive Programming) is a collection of typical 90 competitive programming problems; unfortunately, currently the problem statements are all Japanese.
  • C++入門 AtCoder Programming Guide for beginners (APG4b)」 is a C++ tutorial for competitive programmers. Sadly, this is only in Japanese too.


This problem asks to scan a string type properly.
The problem statement can be rephrased into a procedural style as follows:

  • Use a True/False flag to manage whether A has appeared, B has appeared, and C has appeared. Initially, the three flags is in False state.
  • Use a for loop to iterate \(i=1, 2, \dots, N\). In an iteration:
    • Let \(x\) be the \(i\)-th character of \(S\). Set the flag corresponding to “whether x has appeared” to True.
    • When all the three flags are True for the first time, the answer is \(i\). Print \(i\), and escape from the for loop.

This algorithm is fast enough because it requires only (length of string) \(\leq 100\) steps, so we can simply implement this. Regarding the implementation, we can use the for-loop if we know that the \(i\)-th character of a string (where the initial character is considered \(0\)-th) can be obtained as S[i].

  • Sample code (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

We briefly introduce some alternative solutions.
One is to manage the characters appeared so far in a set-type set. All of A, B, and C have appeared if and only if three distinct characters have appeared so far. Thus, in the algorithm above, we can check if the size of the set of characters already appeared is \(3\) or not.

  • Sample code (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

There is another solution. Let us define \(a\), \(b\), and \(c\) as follows:

  • A appears at the \(a\)-th position for the first time;
  • B appears at the \(b\)-th position for the first time;
  • C appears at the \(c\)-th position for the first time;

Then, the answer is in fact \(\max\lbrace a,b,c\rbrace\), so we can obtain the answer by computing \(a\), \(b\), and \(c\), and taking the \(\max\). We can simply implement it with the find member function of a string type in C++, Python, and so on.

  • Sample code (Python 3)
N = int(input())
S = input()
print(max(S.find(c)for c in "ABC") + 1)

posted:
last update: