公式
C - Poem Online Judge 解説 by Nyaan
この問題はいくつかの解法が考えられると思いますが、例えば for-loop を用いて前から調べていく方法を使って解けないか考えてみましょう。すると、一例として次のような手順が考えられます。
- 暫定的に優秀な提出
best
、およびその得点best_score
を変数として用意する。 - \(1\) 番目の提出から昇順に調べていく。\(i\) 番目の提出を調べるときは、まずその提出がオリジナルかを判定する。
- もしオリジナルであれば、得点
T_i
がbest_score
より大きいかを判定する。- 大きければ
best
をi
に、best_score
をT_i
に更新する。 - そうでなければ何もしない。
- 大きければ
- もしオリジナルでなければ何もしない。
- もしオリジナルであれば、得点
これを 2 重の for-loop を用いて Python でナイーブに実装すると以下のようになります。
しかしこのままでは提出 \(i\) がオリジナルか判定する部分に \(\mathrm{O}(N)\) かかっており、全体で \(\mathrm{O}(N^2)\) 時間かかり TLE してしまいます。
# TLE する解法
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)
そこで、今まで出てきた文字列を Python の set
や C++ の std::set
のような集合型や連想配列(辞書)を用いて管理しましょう。
集合型は次の操作を \(\mathrm{O}(1)\) あるいは \(\mathrm{O}(\log (集合の要素数) )\) で行うことができるデータ構造です。
- ある文字列が集合に含まれているか判定する
- 集合を文字列に追加する
このようなデータ構造を用いることで、ボトルネックの部分であった「文字列が前に登場したか判定する」部分を高速に行うことができるので AC することができます。
# AC する解法
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)
投稿日時:
最終更新: