C - Poem Online Judge 解説 by en_translator


There are several ways to solve this problem. For example, can we solve it by inspecting one-by-one with for-loop? The following procedure is possible, for instance.

  • Prepare a variable for the preliminary best submission best and its score best_score.
  • Inspect the submissions in the increasing order of their indices from the \(!\)-st submission. When inspecting the \(i\)-th submission, first check if the submission is original.
    • If the submission is original, check if the score \(T_i\) is greater than best_score.
      • If it is greater, let best be i and best_score be T_i.
      • Otherwise, do nothing.
    • If the submission isn’t original, do nothing.

The following is a naive implementation in Python with double for-loops.
However, it costs \(\mathrm{O}(N)\) time to determine if Submission \(i\) is original, for a total cost of \(\mathrm{O}(N^2)\), which leads to TLE (Time Limit exceeded).

# TLE submission

N = int(input())
S, T = [], []
for i in range(N):
  s, t = input().split()
  S.append(s)
  T.append(int(t))

best = -1
best_score = -1

for i in range(N):
  original = True
  for j in range(i):
    if S[i] == S[j]:
      original = False
  if original == False:
    continue
  if best_score < T[i]:
    best = i
    best_score = T[i]

print(best + 1)

Instead, let’s manage the strings appeared so far with a set type or a associative array (dictionary) like a set in Python or a std::set in C++.
The set is a data structure which enables the following operation in an \(\mathrm{O}(1)\) or \(\mathrm{O}(\log (\text{the number of elements}) )\) time.

  • Determine if a string is contained in the set
  • Insert a string to the set

With such a data structure, the bottleneck of “determining if string has appeared before” can be done fast enough, so that you can get AC (Accepted).

# AC submission

N = int(input())
S, T = [], []
for i in range(N):
  s, t = input().split()
  S.append(s)
  T.append(int(t))

best = -1
best_score = -1

appeared = set()
for i in range(N):
  if S[i] in appeared:
    continue
  appeared.add(S[i])
  if best_score < T[i]:
    best = i
    best_score = T[i]

print(best + 1)

投稿日時:
最終更新: