📝

AtCoder Beginner Contest 274 レポート

2022/10/23に公開約4,800字

摘要

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

ABC274

https://atcoder.jp/contests/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()

https://atcoder.jp/contests/abc274/submissions/35865039

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

https://atcoder.jp/contests/abc274/submissions/35868166

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

https://atcoder.jp/contests/abc274/submissions/35874392

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, …, 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()

https://atcoder.jp/contests/abc274/submissions/35889882

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

https://atcoder.jp/contests/abc274/submissions/35911551

感想

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

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

Discussion

ログインするとコメントできます