🟢

AtCoder ABC390解説(Python)

2025/01/27に公開

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]))

コンテスト結果

https://atcoder.jp/users/taketii/history/share/abc390

taketiiさんのAtCoder Beginner Contest 390での成績:3639位
パフォーマンス:902相当
レーティング:987→978 (-9) :(
#AtCoder #ABC390

次回こそは水パフォ狙いです!

宣伝

https://github.com/takechi-scratch/atcoder/
コンテスト終了後、いつもここに解答をアップロードしています。
良ければ見てみてください!

Discussion