Zenn
🎃

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

2024/05/28に公開
Python
AtCoder
tech

AtCoder Daily Training ALL 2024/05/28 17:30start に参加しました。
初の ALL です。
D に引っかかったのもあって 4完でした。

A - 3.14

もしくは こちら

考え方

文字列のまま扱えばよいです。

実装例(Python)

def solve(n: int) -> str:
    pi: str = (
        "3.1415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253421170679"
    )
    return pi[: n + 2]


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

感想

やるだけ。

B - Past ABCs

もしくは こちら

考え方

末尾3文字を数字に変換して、範囲と 316 でないかをチェックします。

実装例(Python)

def solve(s: str) -> bool:
    count: int = int(s[3:])
    if count == 316:
        return False
    return 1 <= count <= 349


if __name__ == "__main__":
    S: str = input()
    result = solve(S)
    print("Yes" if result else "No")

感想

やるだけ。

C - qwerty

もしくは こちら

考え方

数列から一つずつ文字列に変換します。
ほぼイディオムのような chr(ord("a") + i - 1) で変換します。
ord("a") + i - 1 で a から i 文字目の文字コードを取得し、chr で文字に変換します。

実装例(Python)

def solve(p: list[int]) -> str:
    return "".join(chr(ord("a") + i - 1) for i in p)


if __name__ == "__main__":
    P: list[int] = list(map(int, input().split()))
    result = solve(P)
    print(result)

感想

一見問題文の意味がわかりませんでしたが、よくよくサンプル見ると、簡単な変換だけでした。

D - Pizza

もしくは こちら

考え方

ほぼ公式解説通りです。
問題文通りのことを実装するのがまずめんどいので、ピザを回転せずに切れ込みを入れるとすると、何度の位置に切れ込みが入るのかを考えます。

切れ込みが入る位置は、i-1 本目の切れ込みから A_i 度左回りに回転させた位置です。
360度で一周して戻ってくることを考慮して、k 度の位置に切れ込みが入ってるかを表す配列 dev[k] を用意します。
k=0 で必ず切れ込みが入るので初期化しておきます。

その後、dev の真となっている位置の間の大きさを求めます。
探索を配列全てではなく、0 \le k \le 360 で行うことで、最後の切れ込みから 360 度位置までの角度の大きさをまとめて計算します。
あとは、その中で最大のものを取ればよいです。

実装例(Python)

def solve(_n: int, a: list[int]) -> int:
    dev: list[bool] = [False] * 360
    dev[0] = True
    s: int = 0
    for a_i in a:
        s += a_i
        s %= 360
        dev[s] = True
    # print(*(i for i in range(359) if dev[i]))
    ans: int = 0
    cnt: int = 0
    for i in range(0, 361):
        if dev[i % 360]:
            ans = max(ans, cnt)
            cnt = 0
        cnt += 1
    return ans


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

感想

配列のサイズを 359 で使ったため、範囲外アクセスエラーを出しました。
RE が範囲外アクセスだろうとは思っていましたが、配列サイズが足りないということに気づかず、時間を無駄にしました。

E - Path Graph?

もしくは こちら

考え方

一直線上に引き延ばすことができるかが、問題の答えです。
つまり、とあるノードにつながっているパスはほとんど2つで、両端のみ1つです。

まず、各ノードにつながっているノードを集合の辞書を用いて管理します。
この辞書は、ノード番号をキーにして、そのノードにつながっているノードの集合を値に持ちます。
これらの集合の大きさが1のものがあれば、それが両端のノードです。

両端のノードのいずれかをスタート地点とし、以下の操作を全てのノードについて行います。

  1. ノード 'now' につながっているノードを取得します。(ノード next_)
  2. ノード next_ につながっているノードの集合から、ノード now を削除します。
    こうすることで、元のノードに戻る可能性をなくすとともに、次のノード候補を端以外1つに限定することができます。
  3. ノード next_ を now として、1 に戻ります。

この操作によって、次のノードが一意に決まらない場合、問答無用でおかしいことがわかります。
最後のノードでは次のノードがあるはずがないので、集合のサイズが0なら真です。

実装例(Python)

from collections import defaultdict


def solve(n: int, m: int, uv: list[tuple[int, int]]) -> bool:
    edge = defaultdict(set)
    for u, v in uv:
        edge[u].add(v)
        edge[v].add(u)

    now: int = 0
    for i in range(1, n + 1):
        if len(edge[i]) == 1:
            now = i
            break

    for i in range(n):
        if i == n - 1:
            if len(edge[now]) == 0:
                return True
        if len(edge[now]) != 1:
            return False
        # print(f"i: {i}, now: {now}")
        next_ = edge[now].pop()
        edge[next_].remove(now)
        now = next_
        # print(edge)
    return False


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

感想

分岐の処理に少し手間取りましたが、概ね想定通り処理できました。

Discussion