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 scorebest_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
bei
andbest_score
beT_i
. - Otherwise, do nothing.
- If it is greater, let
- If the submission isn’t original, do nothing.
- If the submission is original, check if the score \(T_i\) is greater than
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)
投稿日時:
最終更新: