ABC 390感想まとめ

AtCoder Beginner Contest 390 - AtCoder

今回はABC3問解答でした。D問題の難易度が高く、4問解答はハードルが高かったです。。。

B問題の等比数列かどうかを判定するところで1ペナになりました。入力例・出力例のところで小数の例があり、小数点の誤差の危険を感じてはいたのですけども、それでもまんまと引っかかってしまいましたね...。

コンテストでは、D問題は排他的論理和が入っていて難しそうなのでパスし、E問題に着手しました（実際に、D問題は青色レベルの問題で難しかった模様）。E問題も難易度が高く、なんとなく実装方針は立ったものの正解には及ばずでした。

A - 12435

素直に A の要素 i と i+1 を入れ替えて、判定しています。

A = list(map(int, input().split()))

for i in range(4):
    A2 = A.copy()

    # i と i+1 を入れ替える
    sw = A2[i]
    A2[i] = A2[i + 1]
    A2[i + 1] = sw

    # ソート済Aと一致判定
    if A2 == sorted(A):
        print("Yes")
        exit()
print("No")

B - Geometric Sequence

1ペナしてしまい悔しい問題。

理屈としては、「A[0]/A[1] の比率と A[i]/A[i+1] の比率が一致しているか」を、全探索で確認すれば良いのです。ただし、整数を割り算をすると答えが小数になってしまって、誤差が出てきたりします。

ですので、式変形して掛け算にします。

A[0]/A[1] == A[i]/A[i+1] → A[0]*A[i+1] == A[i]*A[1]

こうすると誤差が出ないわけですね...。

N = int(input())
A = list(map(int, input().split()))

if len(A) == 2:
    print("Yes")
    exit()

for i in range(len(A) - 1):
    # 比率が一致しているか判定
    if A[0] * A[i+1] == A[i] * A[1]:
        continue
    else:
        print("No")
        exit()
print("Yes")

C - Paint to make a rectangle

まず、最も小さい黒の長方形は、どのようなサイズかを考えます。
黒マス(#)が確定しているマスは動かせないので、黒マス(#)のうち一番上のマス、一番下のマス、一番左のマス、一番右のマスを含むような長方形が、最も小さい黒の長方形になります。

先ほど求めた最も小さい黒の長方形の範囲の中に、一個でも白マス(".")があるとNGになります。ですので、そのような判定を行えば ok　でした。

H, W = map(int, input().split())
field = [list(input()) for _ in range(H)]

# 黒マスのうち、最も上下左右の位置はどこかを記録する
top = H - 1
left = W - 1
right = 0
bottom = 0

# 黒マスのうち、最も上下左右の位置はどこかを記録する
for i in range(H):
    for j in range(W):
        if field[i][j] == "#":
            top = min(top, i)
            left = min(left, j)
            right = max(right, j)
            bottom = max(bottom, i)

# 先ほど求めた範囲の中に、一個でも白マス(".")があるとNG
for i in range(top, bottom + 1):
    for j in range(left, right + 1):
        if field[i][j] == ".":
            print("No")
            exit()

print("Yes")

E - Vitamin Balance (解説で復習)

コンテスト中は解けなかったので、解説を見て復習しました。

解き方は以下です。

手順1. 各ビタミン値とカロリー値の対応配列を作成する

ビタミン1〜3について、「カロリーが index のときビタミン値が value」の対応表を作成します。入力例1の場合、こんな感じ。

dp1=[0, 0, 0, 0, 0, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8]
dp2=[0, 0, 0, 0, 0, 3, 3, 3, 3, 3, 7, 7, 7, 7, 7, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10]
dp3=[0, 0, 0, 0, 0, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5]

単調増加なので、二分探索で「ビタミン値 v1 のときのカロリーは？」がすぐに求められます。

手順2. 2分探索で、「ビタミン値=v2 のとき、カロリーはX以下に収まりますか？」の上限を探す

この手の問題でよくある、二分探索する手法。手順1の結果を使って、ビタミン値-カロリーの対応がわかるので、これもすぐに求められます。

import bisect

N, X = map(int, input().split())

AC1 = []
AC2 = []
AC3 = []
for i in range(N):
    V, A, C = map(int, input().split())
    if V == 1:
        AC1.append((A, C))
    elif V == 2:
        AC2.append((A, C))
    else:
        AC3.append((A, C))

# DPで indexがカロリー、valueがビタミン量の配列を作成する
def crateDP(AC):
    dp = [[0] * (X+1) for _ in range(len(AC)+1)]
    for i in range(len(AC)):
        a, c = AC[i]
        for j in range(1, X+1):
            if j - c >= 0:
                dp[i+1][j] = max(dp[i][j], dp[i][j-c] + a)
            else:
                dp[i+1][j] = dp[i][j]
    return dp[-1]

# 各ビタミンの カロリー - ビタミン量配列
dp1 = crateDP(AC1)
dp2 = crateDP(AC2)
dp3 = crateDP(AC3)

# ビタミン値が指定されたとき、カロリーXに収まるかを判定
def isEnable(value):
    v1index = bisect.bisect_left(dp1, value)
    v2index = bisect.bisect_left(dp2, value)
    v3index = bisect.bisect_left(dp3, value)
    enable = v1index + v2index + v3index <= X
    return enable

# 二分探索で最大スコアを求める
left = 0
right = min(max(dp1), max(dp2), max(dp3)) + 1

while right - left > 1:
    mid = (left + right) // 2
    if isEnable(mid):
        left = mid
    else:
        right = mid

print(left)