ABC397をPythonで（A～E）

オムロンプログラミングコンテスト2025（AtCoder Beginner Contest 397）の解答等の速報的まとめ

A問題

3ポイントから条件を満たす場合それぞれ-1する

A

x = float(input())
print(3 - (x >= 37.5) - (x >= 38))

B問題

条件を満たさない箇所があるときは１つ加える、をシミュレーションで調べる
最後に加える必要があるかを忘れず調べる

B

s = input()
ans = 0
for i, s_i in enumerate(s):
    if ((i + ans) % 2 == 0 and s_i == "o") or ((i + ans) % 2 == 1 and s_i == "i"):
        ans += 1

print(ans + (len(s) + ans) % 2)

C問題

先頭からと後ろから座標ごとに種類数を調べる

C

n = int(input())
a = list(map(int, input().split()))

left = [0]
s = set()
for a_i in a:
    s.add(a_i)
    left.append(len(s))

right = [0] * (n + 1)
s = set()
for i in range(n - 1, -1, -1):
    s.add(a[i])
    right[i] = len(s)

print(max(l_i + r_i for l_i, r_i in zip(left, right)))

D問題

1. $n$の約数を調べる
2. $x^3-y^3=(x-y)(x^2+x \times y+y^2)$の因数分解を満たす$x, y$があるか二分探索で調べる

かなり冗長な気がする

D

def prime(limit):
    p = [True] * (limit + 1)
    p[0] = p[1] = False
    i = 2
    while i * i <= limit:
        if p[i]:
            for j in range(i * i, limit + 1, i):
                p[j] = False
        i += 1

    return [i for i in range(2, limit + 1) if p[i]]

def make_list(dic):
    res = [1]
    for key, val in dic.items():
        new_lst = []
        for r_i in res:
            for _ in range(val + 1):
                new_lst.append(r_i)
                r_i *= key
        res = new_lst
    return sorted(res)

def check(x, y, N):
    if N // x < x:
        return False
    return (x - y) * (x ** 2 + x * y + y ** 2) <= N

def search(target, N):
    ok, ng = 1, 10 ** 9 + 10
    while abs(ok - ng) > 1:
        mid = abs(ok + ng) // 2
        if check(mid + target, mid, N):
            ok = mid
        else:
            ng = mid

    x, y = ok + target, ok
    if (x - y) * (x ** 2 + x * y + y ** 2) == N:
        return x, y
    return -1, 0

n = int(input())
d = dict()
# 素数を取得
primes = prime(10 ** 6)
# nを素因数分解
n_i = n
for p in primes:
    if n_i % p == 0:
        d[p] = 0
        while n_i % p == 0:
            d[p] += 1
            n_i //= p

if n_i > 1:
    d[n_i] = 1
# 素因数分解の結果から約数を求める
f = make_list(d)

# 約数をもとに条件を満たすx,yがあるか調べる
for f_i in f:
    x, y = search(f_i, n)
    if x > 0:
        exit(print(x, y))

print(-1)

E問題

木をdfsで探索して

• 長さ$k$のパスになったら０を返す
• 長さ$k$に満たないパスだったらその長さを返す
• いずれでもない場合条件を満たさないのでNoを出力して終了

実行したらpythonだと間に合わなかったためC++に書き換えてAC

E（C++）

/*
Original Python Code:

import sys;sys.setrecursionlimit(10 ** 7)

n, k = map(int, input().split())
edge = [[] for _ in range(n * k)]
for _ in range(n * k - 1):
    u, v = map(lambda x:int(x) - 1, input().split())
    edge[u].append(v)
    edge[v].append(u)

def dfs(now, old=-1):
    score = 1
    count = 1
    for to in edge[now]:
        if to == old:
            continue
        r_i = dfs(to, now)
        if r_i > 0:
            score += r_i
            count += 1

    if score < k and count <= 2:
        return score
    elif score == k and count <= 3:
        return 0
    else:
        exit(print("No"))

dfs(0)
print("Yes")
*/

#include <iostream>
#include <vector>
using namespace std;

vector<vector<int>> edge;
int n, k;

int dfs(int now, int old = -1) {
    int score = 1;
    int count = 1;
    for (int to : edge[now]) {
        if (to == old) continue;
        int r_i = dfs(to, now);
        if (r_i > 0) {
            score += r_i;
            count += 1;
        }
    }

    if (score < k && count <= 2) {
        return score;
    } else if (score == k && count <= 3) {
        return 0;
    } else {
        cout << "No" << endl;
        exit(0);
    }
}

int main() {
    cin >> n >> k;
    edge.resize(n * k);
    for (int i = 0; i < n * k - 1; i++) {
        int u, v;
        cin >> u >> v;
        u--; v--;  // Convert to 0-indexed
        edge[u].push_back(v);
        edge[v].push_back(u);
    }
    dfs(0);
    cout << "Yes" << endl;
    return 0;
}