Zenn
🐙

[AtCoder Daily Training HARD 2024/05/07 17:30start] 参加記録

2024/05/07に公開
Python
AtCoder
tech

AtCoder Daily Training HARD 2024/05/07 17:30start に参加しました。
3冠です。
H 問題に関しては残り15分を切っていたため諦めて問題を眺めていました。

E - Centers

もしくは こちら

考え方

単純に各 i について、2番目に出てきた i の位置を保存します。
保存方法はフラグのリストを別に持つ方法もありますが、今回は一度も出てきていない場合は -2、一度だけ出てきたときには -1、2回目に出てきたらそのインデックスを保存するリストを用いました。
これで、f(i) のマッピングができたので、あとは i と f(i) をまとめて、f(i) をキーに並び替え、i だけを取り出せばいいです。

実装例(Python)

from collections import defaultdict


def solve(_n: int, a: list[int]) -> list[int]:
    rtn = defaultdict(lambda: -2)
    for i, a_i in enumerate(a):
        if rtn[a_i] == -1:
            rtn[a_i] = i + 1
        if rtn[a_i] == -2:
            rtn[a_i] = -1
    return [index for index, _ in sorted(rtn.items(), key=lambda x: x[1])]


if __name__ == "__main__":
    N = int(input())
    A = list(map(int, input().split()))
    result = solve(N, A)
    print(*result)

感想

最初2番目だけを取り出すデータ構造をどうするか悩みましたが、最初に思いついたやつでやりました。

F - Graph Isomorphism

もしくは こちら

考え方

今回、1 \le N \le 8 なので、問題文の P を全探索しても十分間に合います。
Python には 'itertools.permutations' という並び替え列挙の関数があるので、これを使って P を列挙します。
その後、P_i と P_j について、同様に繋がれているかどうかを確認します。
制約より、A_i \le B_i が保証されているので、P を元にしたひもは1項目の方が小さいとすると集合を用いて高速に判定できます。

実装例(Python)

from itertools import permutations


def solve(
    n: int, _m: int, ab: list[tuple[int, int]], cd: list[tuple[int, int]]
) -> bool:
    # 1<=n<=8 より前探索
    cd_set = set(cd)
    for p in permutations(range(1, n + 1)):
        # print(p)
        for a, b in ab:
            p_c = p[a - 1]
            p_d = p[b - 1]
            if p_c > p_d:
                p_c, p_d = p_d, p_c
            if (p_c, p_d) not in cd_set:
                break
        else:
            return True

    return False


if __name__ == "__main__":
    N: int
    M: int
    N, M = map(int, input().split())
    AB: list[tuple[int, int]] = [
        tuple(map(int, input().split())) for _ in range(M)
    ]
    CD: list[tuple[int, int]] = [
        tuple(map(int, input().split())) for _ in range(M)
    ]
    ans = solve(N, M, AB, CD)
    print("Yes" if ans else "No")

感想

グラフの同型判定は問題として複雑そうだなと思っていました。
そこで制約を見てみると、1 \le N \le 8 ということで、全探索が間に合うことがわかりました。
全探索できる問題は全探索するのが実装もわかりやすくて嬉しいです。
ただこのような問題は本番であまり見ないような気がします。
少なくとも ABC の C や D ではあまり見ません。

G - Polynomial division

もしくは こちら

考え方

これは単純な多項式の割り算です。

上位の項から順に見ていく時に、C を更新しながら、B は C の 0 でない最上位の項を &A& の最上位の項で割ったものを入れていくだけです。

実装例(Python)

def solve(
    n: int,
    m: int,
    a: list[int],
    c: list[int],
) -> list[int]:
    b: list[int] = [0] * (m + 1)

    # print(a, b, c)
    for i in range(m, -1, -1):
        b[i] = c[n + i] // a[-1]
        for j in range(n, -1, -1):
            c[j + i] -= a[j] * b[i]
        # print(a, b, c)

    return b


def mul(
    n: int,
    m: int,
    a: list[int],
    b: list[int],
) -> list[int]:
    c: list[int] = [0] * (n + m + 1)
    for i in range(n + 1):
        for j in range(m + 1):
            c[i + j] += a[i] * b[j]
    return c


if __name__ == "__main__":
    N: int
    M: int
    N, M = map(int, input().split())
    A: list[int] = list(map(int, input().split()))
    C: list[int] = list(map(int, input().split()))
    result = solve(N, M, A, C)
    print(*result)

感想

多倍長整数の実装経験があるので、楽勝だと思いました。
思いましたが、一発目 15WA を出しました。
その後、ランダムテストを書いてデバッグしたら B を更新する時に C の0でない最上位の項をそのまま使っていることがわかりました。
本来であれば C を更新していくと最上位の項から順に 0 が増えていくはずですが、それが起こっていなかったのです。
この原因解明に時間がかかりました。
時間がかかった理由はサンプルケースが全て通っていたことです。
偶然にもサンプルケースの A の最上位の項が 1 だったため、問題ありませんでした。
この先入観によって何かコーナーケースやしなければならない処理を見落としているのではないかと考えました。
正直 15WA/7AC は明らかに基本ロジックに間違いがあるのに、そこに注目するのが遅かった。
5分で気がつけていれば、残り25分で H 問題に取り組むことができたと思います。

Discussion