[ABC306 Python]トヨタ自動車プログラミングコンテスト2023#3(AtCoder Beginner Contest 306)
A問題
# 入力N
N = int(input())
# 入力S
S = input()
# 答え
ans = ""
# 1文字ずつ2倍していく
for i in S:
ans += i
ans += i
print(ans)
問題文から1文字ずつ2倍になっていることが分かりますね。
Sから1文字ずつ取り出して新たな文字列に2回ずつ加えれば答えが導き出せます。
B問題
# 入力A
A = list(map(int, input().split()))
# 答え
ans = 0
# 0から63までの64回足す
for i in range(64):
# 問題文のとおり、Ai+2**iを加える
ans += A[i]*2**i
print(ans)問題文に式があるので、式のとおりに解いていきます。
64回足すのはA[i]*2**iです。
C問題
# インポート
from collections import defaultdict
# 入力N
N = int(input())
# 入力A
A = list(map(int, input().split()))
# defaultdictを定義
# 1~Nが存在する場所を要素ごとに保存する
d = defaultdict(list)
for i in range(N*3):
d[A[i]].append(i+1)
# 答え
ans = []
# それぞれの要素の種類(1~N)について、
for i in d:
# 順番を並べ替えて、
d[i].sort()
# [f(i), i]の形で保存する
ans.append([d[i][1], i])
# f(i)でsort
ans.sort()
for i in ans:
# iを空白区切りで出力する
print(i[1], end=" ")1~Nの要素ごとに場所を保存する必要があるので、
defaultdictを使います。
求めたf(i)とiとの関係を保ちながら、
f(i)を並べ替えることで、答えを導き出します。
D問題
# 入力N
N = int(input())
# DP
# 1~N品目の料理が提供された後の、
# 高橋君の状態別のおいしさの総和を表す
# dp[i][0]：i品目の提供後高橋君がお腹を壊していない場合の最大の美味しさ
# dp[i][1]：i品目の提供後高橋君がお腹を壊している場合の最大の美味しさ
# dp[0]はまだ料理が提供されていないので、
# おいしさはお腹がどちらの状態でも0
dp = [[0, 0] for _ in range(N+1)]
# N品の料理が提供される
for i in range(1, N+1):
# 入力X,Y
X, Y = map(int, input().split())
# 解毒剤入りの料理の場合
if X == 0:
# お腹を壊さないためには、
# 「食べない」か、
# 「お腹を壊していない状態で食べる」か、
# 「お腹を壊している状態で食べる」、
# の最大値が答え
dp[i][0] = max(dp[i-1][0], dp[i-1][0]+Y, dp[i-1][1]+Y)
# お腹を壊すためには
# 「お腹を壊している状態で食べない」のみ
dp[i][1] = dp[i-1][1]
else:
# お腹を壊さないためには、
# 「お腹を壊していない状態で食べない」のみ
dp[i][0] = dp[i-1][0]
# お腹を壊すためには
# 「お腹を壊していない状態で食べる」か、
# 「お腹を壊している状態で食べない」、
# の最大値が答え
dp[i][1] = max(dp[i-1][0]+Y, dp[i-1][1])
# 最終的にはお腹の状態はどうでもいいので、
# 最後に料理の美味しさが大きいほうを出力する
print(max(dp[-1]))DPを使います。
状態分けは1~N品の料理が配られたのちの高橋君のお腹の状態です。
お腹を壊しているか、壊していないかを各回で条件分けし、
その都度美味しさの総和の最大値を更新していきます。