📝

AtCoder Beginner Contest 274 レポート

2022/10/23に公開

AtCoder

Python 3

tech

摘要

ABCD4完．80:32 (2WA)が響いてレートを15下げてしまいました．

ABC274

コンテスト名: キーエンスプログラミングコンテスト2022（AtCoder Beginner Contest 274）
順位: 2096th / 8252
パフォーマンス: 1035
レーティング: 1195 → 1180 (-15)
コンテスト参加回数: 61

A - Batting Average

A - 問題

$\frac{B}{A}$ を小数第3位で四捨五入した値を求めよ．

A - 解法

特筆事項なし．

A - ACコード

def main():
   A, B = map(int, input().split())

   S = '{:.3f}'.format(B/A)
   print(S)


if __name__ == '__main__': main()

B - Line Sensor

B - 問題

$H\times W$ のグリッドについて，各列の $'#'$ マスの個数を求めよ．

B - 解法

愚直に数え上げ．

B - ACコード

def main():
    H, W = map(int, input().split())
    C = [input() for _ in range(H)]

    ans = [0]*W
    for ci in C:
        for j in range(W): ans[j] += int(ci[j] == '#')

    print(*ans)


if __name__ == '__main__': main()

C - Ameba

C - 問題

$1$ を根にもつ $2N+1$ 頂点の二分木について，各ノードが $1$ の何世代下にあるかを求めよ．

C - 解法

$1 \leq i \leq N$ の各 $i$ に対して，
ans[2*i] = ans[2*i + 1] = ans[A[i]] + 1
とするだけ．

C - ACコード

def main():
    N = int(input())
    A = [0] + list(map(int, input().split()))

    ans = [0]*2 + [-1]*2*N
    for i in range(1, N+1): ans[2*i] = ans[2*i + 1] = ans[A[i]] + 1

    print(*ans[1:], sep='\n')


if __name__ == '__main__': main()

D - Robot Arms 2

D - 問題

$xy$ 平面の格子上を移動して原点 $(0, 0)$ から $(X, Y)$ まで移動できるか求めよ．
正確には，

(0, 0) \to (A_1, 0) \to (A_1, \pm A_2) \to (A_1 \pm A_3, \pm A_2) \to … \to (X, Y)

のように縦横に $A = (A_1, A_2, A_3, \dots, A_N)$ の距離だけ移動を繰り返すことで $(X, Y)$ に辿り着けるか求めよ．

D - 解法

縦横ジグザグに移動することから， $x$ 方向の移動と $y$ 方向の移動はそれぞれ独立に扱うことができる．
また，それぞれの1次元移動について，(目標移動距離) $=$ (進む距離) $-$ (戻る距離)を満たすよう移動できるかどうかはナップザックDPにより求められる．

と，ここまでの方針はスムーズに立ったものの，

$x$ 方向の移動は初め $+A_1$ だけ移動することが固定
$x$ 方向の移動が1回の場合の処理

の2点に気を付けている間にどんどんコードが汚くなっていく……
同時に，ナップザックの容量を謎にケチろうとしたせいで無駄なバグを生んでしまった．
最終的にここ最近のコードの中でもぶっちぎりで汚いコードが完成してしまった．

D - ACコード

def main():
    global N, x, y
    N, x, y = map(int, input().split())
    A = list(map(int, input().split()))

    ver, hor = A[1::2], A[::2]

    ans = calc('ver', ver) and calc('hor', hor)
    print('Yes' if ans else 'No')


def calc(mode, arr):
    if mode == 'ver':
        sm = sum(arr)
        if sm%2 != y%2: return False
        tar = (sm + y)//2
        if tar < 0: return False

        dp = [[False]*(10*sm+11) for _ in range(N//2+1)]
        dp[0][0] = True
        for i in range(N//2):
            for j in range(tar+1):
                if dp[i][j]: dp[i+1][j] = dp[i+1][j+arr[i]] = True

        return dp[-1][tar]

    elif len(arr) > 1:
        sm = sum(arr[1:])
        if sm%2 != (x - arr[0])%2: return False
        tar = (sm + abs(x - arr[0]))//2
        if tar < 0: return False

        dp = [[False]*(10*sm+11) for _ in range(-(-N//2))]
        dp[0][0] = True
        for i in range(-(-N//2)-1):
            for j in range(tar+1):
                if dp[i][j]: dp[i+1][j] = dp[i+1][j+arr[i+1]] = True

        return dp[-1][tar]

    else: return arr[0] == x


if __name__ == '__main__': main()

D - 改良版

def main():
    global N, X, Y, A
    N, X, Y = map(int, input().split())
    A = list(map(int, input().split()))

    ans = calc()
    print('Yes' if ans else 'No')


def calc():
    hor, ver = A[::2] + [0], A[1::2]  # x方向の移動horについては，len(hor[1:]) > 0 となるよう0を追加
    sm_h, sm_v = sum(hor[1:]), sum(ver)

    """
    進む距離と戻る距離の偶奇が一致した場合は，和差算により得られた整数解についてナップザック問題を解く
    x方向の移動horについては A[0] -> X への移動を考える
    """
    if sm_h%2 != (X - A[0])%2 or sm_v%2 != Y%2: return False
    else: return knapsack(hor[1:], (X - A[0] + sm_h)//2) and knapsack(ver, (Y + sm_v)//2)


def knapsack(arr, w):
    dp = [True] + [False]*(10**4 + 10)  # ナップザックの容量をケチらない！

    for ai in arr:
        for j in range(w+1):
            if dp[j]: dp[j+ai] = True
            if dp[w]: return True
    return dp[w]


if __name__ == '__main__': main()

感想

D問題に手間取ってしまい，そこで体力が尽きました……
E問題は宝箱を街と同じように扱うことでなんとかなるらしいので，これから復習して確認します．
F問題はアイデアこそ普通に思いつきそうなものでしたが，Pythonの場合は定数倍高速化を考えないと実行時間が厳しいそうです．

今回の学びとしては，
「DPのサイズを絶対にケチらない」
以上です．