ABC 3解答でパフォーマンス 673 でした。
今回はD問題が残念でした。
D問題はTLEを時間内に解決できなかったのですが、これは「PyPyは再帰呼び出しが遅い」という特性のため。アルゴリズム的には正解だったので、もしもPyPyに変えてCPythonで提出していたら正解だった。
ABC363 C問題でもPythonの実行速度の遅さで不正解だったことがあり、そろそろ他の言語を使うなどの対応策を考えないといけないかもしれない。
A - Cut
配列の一部をcutしてマージする問題。Pythonの A[X:] とか A[:X] の記法に慣れておらず、何回か試行錯誤したため時間をロスしてしまっている。
N, K = map(int, input().split())
A = list(map(int, input().split()))
answer = A[N-K:] + A[:N-K]
print(*answer)
B - Decrease 2 max elements
条件を読んで計算量は間に合うだろうと考え、問題文のとおりにそのままシミュレーションをした。
N = int(input())
A = list(map(int, input().split()))
for i in range(10 ** 10): # ループ回数は適当に大きな値
A.sort(reverse=True)
if A[0] > 0:
A[0] -= 1
if A[1] > 0:
A[1] -= 1
count = 0
for a in A:
if a > 0:
count += 1
if count <= 1:
print(i+1)
exit()
C - Triple Attack
B問題とは違い、この問題は問題文のとおりにシミュレーションするとTLEになってしまう。「３回攻撃すると５ダメージ」という性質をうまく使うと計算量を削減できる。
N = int(input())
H = list(map(int, input().split()))
# t=現在の攻撃力, h=モンスターのHP
def attack(t, h):
new_t = t
# 位置を3n+1回目の攻撃にあわせる
amari = t % 3
if amari == 2:
new_t += 1
h = h - 3
if h <= 0:
return new_t
elif amari == 1:
new_t += 1
h = h - 1
if h <= 0:
return new_t
new_t += 1
h = h - 3
if h <= 0:
return new_t
# ３の倍数で攻撃
attacks_3 = h // 5
new_t += attacks_3 * 3
h = h - attacks_3 * 5
# あまりを削る
while 0 < h:
new_t += 1
if new_t % 3 == 0:
h = h - 3
else:
h = h - 1
return new_t
t = 0
for i in range(N):
t = attack(t, H[i])
print(t)
上の提出コードはちょっと冗長だった。「# 位置を3n+1回目の攻撃にあわせる」の部分は無くてもいい（現在の攻撃力が 3N, 3n+1, 3N+2 どの位置であっても、３回攻撃すれば５ダメージなのだから）
改修後のコードは以下。
N = int(input())
H = list(map(int, input().split()))
# t=現在の攻撃力, h=モンスターのHP
def attack(t, h):
new_t = t
# 3回攻撃で５ダメージを与える
attacks_3 = h // 5
new_t += attacks_3 * 3
h = h - attacks_3 * 5
# あまりを削る
while 0 < h:
new_t += 1
if new_t % 3 == 0:
h = h - 3
else:
h = h - 1
return new_t
t = 0
for i in range(N):
t = attack(t, H[i])
print(t)
D - Minimum Steiner Tree
今回は解けなかった問題。以下の正解コードは時間内に出来ていたのだけど、PyPyではTLEになってしまう(CPythonならAC)。
「PyPyは再帰の実行が遅い」というのが頭に入っていなかったのが敗因。
CPythonに切り替えるなり、ChatGPTでC++に移植するなり、コンテスト中に思いつけばなあ...。
ソースコードは、深さ優先探索で削除しても良い頂点を求める方針。削除しても良い頂点は、以下の方針で求める。
- 末端でかつVに含まれる頂点でない場合、削除する
- 自分以下の頂点を調べたあとに、子の頂点がすべて削除して良いなら、自分も削除する
以下、CPythonならACのサンプルソースです。
import sys
sys.setrecursionlimit(10 ** 8)
N, K = map(int, input().split())
path = defaultdict(list)
for i in range(N-1):
A, B = map(int, input().split())
path[A].append(B)
path[B].append(A)
V = list(map(int, input().split()))
set_v = set(V)
# 削除しても良い頂点
delete = set()
# Vに含まれる頂点が連結になるように、削除する頂点を決める
# 探索(current=調査する頂点番号、parent=呼び出し元の頂点番号)
def dfs(current, parent):
global delete
# 末端でかつVに含まれる頂点でない場合、削除する
if len(path[current]) == 1 and current not in set_v:
delete.add(current)
# 再帰でcurrent以下を再探索する
for next in path[current]:
if next == parent:
continue
dfs(next, current)
if current not in set_v:
# 調べたあとに、current頂点以下がすべてdeleteならば、currentもdelete
delete_current = True
for next in path[current]:
if next == parent:
continue
if next not in delete:
delete_current = False
break
if delete_current:
delete.add(current)
dfs(V[0], -1)
# 全体から削除点を引く
print(N-len(delete))