🟢
AtCoder ABC390解説(Python)
Python緑コーダーによる、ABC390(2025/01/25実施)の解説です!
今後は、時々解説を書いていこうと思います。
A問題
実際に、入れ替える値ごとにシミュレーションしてみましょう。
A = [int(x) for x in input().split()]
for i in range(4):
# `a_temp = A` とすると、Aの値が変わってしまうので注意
a_temp = A.copy()
# A[i]とA[i+1]を入れ替える(そのために一時的に保存)
temp = a_temp[i]
a_temp[i] = a_temp[i + 1]
a_temp[i + 1] = temp
# 値の並びをチェック(1つでも前の値の方が大きくなっていたらアウト)
for j in range(4):
if a_temp[j] > a_temp[j + 1]:
break
else:
print("Yes")
break
else:
print("No")
また、
- 正解となる並べ方(5通りしかありません)を列挙する方法
- 入力のリストと正解のリストでのそれぞれの差を合計し、合計が2か確かめる方法
もあるようです。
B問題
公比を実際に計算して比べようとすると、小数の影響で正しく比べられません。
A[0] : A[1] == A[i] : A[i+1]
となっているので、比の関係より
A[0] * A[i + 1] == A[1] * A[i]
を判定すれば良いことがわかります。
N = int(input())
A = [int(x) for x in input().split()]
for i in range(1, N - 1):
if A[i] * A[1] != A[i + 1] * A[0]:
print("No")
break
else:
print("Yes")
公式もあるみたいですね。
また、PythonだとDecimalモジュールを利用して正確な小数の計算をすることもできます。
ただし、処理速度が遅くなるので、C問題以降では使えないと考えたほうが良いでしょう。
from decimal import Decimal
N = int(input())
A = [int(x) for x in input().split()]
rate = Decimal(A[1]) / Decimal(A[0])
for i in range(2, N):
if Decimal(A[i]) / Decimal(A[i - 1]) != rate:
print("No")
exit()
print("Yes")
C問題
まず、黒がどの範囲にあるかを調べます。
その範囲をすべて黒で塗って長方形を作ることを考えると、範囲の中に白があったらアウトです。
これを実装すれば、O(HW)で計算でき、制限時間に間に合います。
H, W = [int(x) for x in input().split()]
grid = []
for _ in range(H):
grid.append(list(input()))
# 黒の左上と右下を調べる
min_x = W
max_x = -1
min_y = H
max_y = -1
for i in range(H):
for j in range(W):
if grid[i][j] == "#":
min_x = min(min_x, j)
max_x = max(max_x, j)
min_y = min(min_y, i)
max_y = max(max_y, i)
# その範囲の中に白が入ってしまっていたらアウト
ok = True
for i in range(min_y, max_y + 1):
for j in range(min_x, max_x + 1):
if grid[i][j] == ".":
ok = False
break
# こういうときに三項演算子はちょっと便利
print("Yes" if ok else "No")
D問題(なし)
D問題は未解答なので解説を飛ばします。
E問題(不正解)
N, X <= 5000なので、DPをすればいいことがわかります。
大切なのは、各ビタミンごとに最大値を求めることのようです。
各食べ物にはビタミンが1種類しか含まれていないので、各ビタミンごとにカロリーを割り当てれば、その中での各ビタミンの最大値をすぐに求めることができます。
カロリーを0から始めて、ビタミンの一番少ないものに割り当てを1ずつ足していきます。X<=5000なので十分間に合います。
TLE・WA解答
普通に解法を間違えています。
N, X = [int(x) for x in input().split()]
food = []
for _ in range(N):
food.append([int(x) for x in input().split()])
dp = [[(0, 0, 0) for _ in range(X + 1)] for _ in range(N)]
for i in range(N):
v, a, c = food[i]
v -= 1
for j in range(X + 1):
before = dp[i - 1][j]
if j - c >= 0:
eat = dp[i - 1][j - c]
eat[v] += a
else:
eat = (0, 0, 0)
if min(before) < min(eat):
dp[i][j] = eat
elif min(before) > min(eat):
dp[i][j] = before
elif sum(before) < sum(eat):
dp[i][j] = eat
else:
dp[i][j] = before
print(min(dp[-1][-1]))
コンテスト結果
taketiiさんのAtCoder Beginner Contest 390での成績:3639位
パフォーマンス:902相当
レーティング:987→978 (-9) :(
#AtCoder #ABC390
次回こそは水パフォ狙いです!
宣伝
良ければ見てみてください!
Discussion