😊

AtCoder ABC196 個人的メモ

2021/03/20に公開

Python

競技プログラミング

AtCoder

tech

所感

abcd4完
最高パフォでHighest更新
abc196
やったぜ

A - Difference Max

$x-y$ を最大化するには， $x$ は最大値で $y$ は最低値を用いればおｋ

a, b = map(int, input().split())
c, d = map(int, input().split())

print(b - c)

B - Round Down

数値 $X$ を文字列として入力
左端から1文字づつ確認していく
小数点に当たったらそこで終了すればおｋ

X = input()

ans = ""
for x in X:
    if x == ".":
        break
    ans += x

print(ans)

C - Doubled

前半と後半は等しいので，どちらか片方だけ考えればおｋ
制約が $N<10^{12}$ なので， $(前半の数)<\sqrt{N}<10^6$
というわけで，前半の数を全探索すれば良さそう

コンテスト中のコード

N = int(input())

ans = 0
for i in range(1, len(str(N)) // 2 + 1):
    for j in range(10 ** (i - 1), 10 ** i):
        if int(str(j) * 2) > N:
            continue
        ans += 1

print(ans)

コンテスト後のコード

N = int(input())

ans = 0
while int(str(ans) * 2) <= N:
    ans += 1

print(ans - 1)

D - Hanjo

解法は割とすぐ分かったけど，バグらせすぎた

再帰関数を用いて以下の様に全探索した
マスを左上から見ていき，空いているなら

半畳を置く
畳を縦に置く
畳を横に置く

の3通りをそれぞれ試してみる，という操作を繰り返す
畳が全て埋まっていて，畳の数と半畳の数が条件と一致する場合は，あり得る場合として勘定する

計算量はざっくり各マスで3通りの場合が考えられるとすると， $O(3^{HW})\sim O(10^7)$ だが，実際はもっと小さくなるはずなので，まぁ大丈夫そう

再帰関数についてはこの辺が参考になるかも

デバッグしやすい様に $now$ 配列の要素を整数にしているが，真理値にした方が実装は楽そう

再帰関数内で二次元配列を操作しているので，deepcopyを使わないとバグる

from copy import deepcopy


def rec(a: int, b: int, now: list):
    """
    空いている場所を探し，そこに半畳か畳を配置していく
    全部埋まっている&畳の数が正しければ1を返す
    a: int
        現在の部屋に詰めてある長方形の畳の数
    b: int
        現在の部屋に詰めてある正方形の半畳の数
    now: list
        現在の部屋の様子(どこにどの畳が詰めてあるか)
    """

    # まだ畳が置かれていない(空いている)場所を探す
    y, x = -1, -1
    for i in range(H):
        for j in range(W):
            if now[i][j] == 0:
                y, x = i, j
                break
        if y != -1:
            break

    res = 0
    # 空きが無い&畳の数が正しいなら1を返す
    if y == -1 and a == A and b == B:
        res += 1
    # 1.半畳を置く場合
    if b < B:
        lst = deepcopy(now)
        lst[y][x] = b + 1
        res += rec(a, b + 1, lst)
    # 2.畳を縦に置く場合
    if y + 1 < H and now[y + 1][x] == 0 and a < A:
        lst = deepcopy(now)
        lst[y][x] = -(a + 1)
        lst[y + 1][x] = -(a + 1)
        res += rec(a + 1, b, lst)
    # 3.畳を横に置く場合
    if x + 1 < W and now[y][x + 1] == 0 and a < A:
        lst = deepcopy(now)
        lst[y][x] = -(a + 1)
        lst[y][x + 1] = -(a + 1)
        res += rec(a + 1, b, lst)

    return res


H, W, A, B = map(int, input().split())

ans = rec(0, 0, [[0] * W for _ in range(H)])
print(ans)

所感

A - Difference Max

B - Round Down

C - Doubled

D - Hanjo

Discussion