[パナソニックグループ プログラミングコンテスト2024（AtCoder Beginner Contest 354）] 参加記録

パナソニックグループ プログラミングコンテスト2024（AtCoder Beginner Contest 354）に参加しました。
4冠です。
9時時点で PC の前に座れなかったので、タイムロスが大きいです。
計画的に行動します……

A - Exponential Plant

考え方

シンプルに植物の高さを保存して、 $H$ を超えたらその時の日数を出力します。
ちなみに、 $2^i$ の和は、 $2^{i+1} - 1$ なので、 $log_2(H)$ を元に考えてもいいと思います。

実装例(Python)

def solve(h: int) -> int:
    ans = 0
    for i in range(128):
        ans += 2**i
        if ans > h:
            return i + 1


if __name__ == "__main__":
    H = int(input())
    print(solve(H))

感想

非常にシンプルな問題でした。
始まった瞬間 PC の前におらず、スマホでやったら普通に RE しました。

B - AtCoder Janken 2

考え方

問題文通りの処理です。
まず、ユーザー名をキーに辞書順に並べます。
$T$ を計算して、 $T mod N$ の位置にいるユーザーのユーザー名を出力すればいいです。

実装例(Python)

def solve(n: int, sc: list[tuple[str, int]]) -> str:
    sorted_sc = sorted(sc)

    t = sum(c for s, c in sc)
    return sorted_sc[t % n][0]


if __name__ == "__main__":
    N = int(input())
    SC = [tuple(input().split()) for _ in range(N)]
    SC = [(s, int(c)) for s, c in SC]
    print(solve(N, SC))

感想

問題文通りの処理でした。
できるだけシンプルに書くことを心がけました。

C - AtCoder Magics

考え方

問題文より残るカードの集合が一意に定まるので、取り除くのではなく 組み込んでいく 処理と考えます。
取り除く系の問題は、最終成果物が一意なら、逆に組み込むとか組み立てるとか考えると計算量が削減できて嬉しいことが多いです。
グラフの辺を取り除く問題にこのパターンを見たことがあります。

最終的な出力は元のカードのインデックスなので、カードのインデックスとセットにした上で、 $A_i$ の大きい順に並べます。
これはカードを追加していく順番なのですが、足していくカードは強さの面では既存のカード全てより弱いことが保証されます。
そのため、既存のカードのいずれかよりコストが高いかどうかを確認して、高くないなら追加します。
このとき、 $N \le 2 \times 10^5$ なので、追加のたびに残り全てと比べると計算量が一回あたり $O(N)$ になり、全体で $O(N^2)$ になってしまい TLE します。

ここで、既存のカードのいずれかよりコストが高いか確認する時、既存のカードの最小値よりも大きいかどうかを確認すればいいことに気がつけば、計算量を一回あたり $O(1)$ に抑えることができます。
ということで、最小値を保存し、それよりも大きくないなら追加するという処理を行えば全体の計算量 $O(N)$ で解けます。

実装例(Python)

def solve(n: int, ac: list[tuple[int, int]]) -> tuple[int, list[int]]:
    sorted_ac = sorted(zip(ac, range(1, n + 1)), reverse=True)
    # print(sorted_ac)

    rtn: list[int] = [sorted_ac[0][1]]
    cost_min = sorted_ac[0][0][1]
    for i in range(1, n):
        # print(i, sorted_ac[i])
        cost = sorted_ac[i][0][1]
        if cost_min < cost:
            continue
        rtn.append(sorted_ac[i][1])
        cost_min = cost

    return len(rtn), sorted(rtn)


if __name__ == "__main__":
    N = int(input())
    AC = [tuple(map(int, input().split())) for _ in range(N)]
    ans, res = solve(N, AC)
    print(ans)
    print(*res)

感想

まず、グラフの問題の衝撃がすごかったので、方針はすぐに立ちました。
そこから計算量からどうにか処理したいと考えました。
すると、最小値だけをみればいいと気がつけたので、それを実装しました。
10分ちょっとで解けました。
9時ぴったりに PC の前に座れていれば、ここまで15分で解けて E 問題に取り掛かれたかもしれません。

バイトから帰ってくるのが7時の予定だったんですけどね。

D - AtCoder Wallpaper

考え方

問題の図からヒントを得ます。
まずは、入力が全て整数なので、座標系ではなくマス目のように考えます。
すると、 $x$ 軸方向に4マスずつセットにすると、全てのセットでの面積が $2$ であることがわかります。

まだ考慮できないところを考えると、右側の 0~3 列分です。
$y$ 軸方向に2マスずつセットにすると、全てのセットが特定の面積になることがわかり、その面積は見る列の印でクスの剰余で決まるため、それぞれ分岐させます。

もし高さが偶数ならここまでで全て計算済みになるので、そのまま出力します。
高さが奇数の場合、最後の 1 列分を考えます。
これは残りの列に応じて変わってくるので、1マスずつ計算すればわかりやすいです。
残りの 1~3 マスの座標は剰余をとって全て正にしておくと計算がしやすいです。
Python は仕様上正の数で剰余を取れば正の数になるので、そのまま計算しても大丈夫です。

$i$ 列 $j$ 行目のマス目の面積(0-index)は $i \not \equiv j \mod 2$ なら $0.5$ 、そうでなく $i$ が $0$ または $1$ なら $1$ 、そうでないなら $0$ です。
これを残りのマス目に対して計算していけば、全てのマス目の面積が求まります。

最後に $2$ 倍する処理がありますが、最初から $2$ 倍しておけば、最後の処理が不要になりますし、全て整数型で計算できます。
$0.5$ でもバイナリ特有の誤差は出ないので、そのまま計算しても大丈夫ですが、暗黙の型変換のコストがあるので、整数型で計算することをおすすめします。

実装例(Python)

def solve(a: int, b: int, c: int, d: int) -> int:
    rtn = 0
    width = c - a
    w_set, w_mod = divmod(width, 4)
    height = d - b
    rtn += w_set * height * 4
    # print(f"4set: {rtn}")

    h_set, h_mod = divmod(height, 2)
    c1_mod = (c - w_mod) % 4
    for _ in range(w_mod):
        # print(f"{c1_mod=}")
        if c1_mod == 0:
            rtn += h_set * 3
        elif c1_mod == 1:
            rtn += h_set * 3
        else:
            rtn += h_set
        c1_mod += 1
        c1_mod %= 4
    # print(f"h_set: {rtn}")

    if h_mod == 1:
        c1_mod = (c - w_mod) % 4
        d_mod = (d - 1) % 2
        # print(f"{c1_mod=}, {d_mod=}")
        for _ in range(w_mod):
            # print(f"{c1_mod=}")
            if c1_mod % 2 ^ d_mod % 2:
                # print("add tri")
                rtn += 1
            elif c1_mod < 2:
                # print("add squ")
                rtn += 2
            c1_mod += 1
            c1_mod %= 4

    return rtn


if __name__ == "__main__":
    A, B, C, D = map(int, input().split())
    print(solve(A, B, C, D))

感想

最後の残りの 1~3 マスの処理に手こずり、WA を出しました。
試しに、 $A$ と $B$ をそれぞれ $0$ に固定し、 $C$ と $D$ をずらしたテストケースを作り、それを通るように修正したところ AC しました。
テストケースはどんな時でも重要ですね。