📝

AtCoder Beginner Contest 272 レポート

2022/10/09に公開

AtCoder

Python 3

tech

摘要

残り2分でE問題を通してABCDE5完でした．ギリギリ水色復帰です．

ABC272

コンテスト名: AtCoder Beginner Contest 272
順位: 1034th / 8565
パフォーマンス: 1431
レーティング: 1171 → 1200 (+29)
コンテスト参加回数: 59

A - Integer Sum

A - 問題

整数列 $A$ の和を求めよ．

A - 解法

特筆事項なし．

A - ACコード

def main():
    N = int(input())
    A = list(map(int, input().split()))

    ans = sum(A)
    print(ans)


if __name__ == '__main__': main()

B - Everyone is Friends

B - 問題

$M$ 行の配列に対して，1から $N$ までの整数から任意の2つを選んだ組み合わせについて，そのどちらとも同じ行に存在しているかを判定せよ．

B - 解法

それぞれの整数について，同席した整数をset()により管理する． $M$ 回の舞踏会について処理を行ったのち，全ての整数 $i$ についてlen(set(i)) == N-1を満たすか判定する．

B - ACコード

def main():
    N, M = map(int, input().split())

    st = [set() for _ in range(N+1)]
    for _ in range(M):
        arr = list(map(int, input().split()))

        for i in range(1, arr[0]):
            for j in range(i+1, arr[0]+1):
                st[arr[i]].add(arr[j])
                st[arr[j]].add(arr[i])

    ans = 'Yes' if all(len(s) == N-1 for s in st[1:]) else 'No'
    print(ans)


if __name__ == '__main__': main()

C - Max Even

C - 問題

整数列 $A$ の異なる2要素の和のうち最大の偶数を求めよ．（存在しない場合は-1を出力）

C - 解法

2要素の和が偶数となるのはその偶奇が一致するとき．全ての要素を奇数と偶数に仕分け，奇数，偶数の要素が2個以上ある場合に上位2つの和が答えの候補となる．

C - ACコード

def main():
    N = int(input())
    A = sorted(map(int, input().split()))
    O, E = [], []
    for ai in A:
        if ai % 2: O.append(ai)
        else: E.append(ai)

    ans = -1
    if len(O) > 1: ans = sum(O[-2:])
    if len(E) > 1: ans = max(ans, sum(E[-2:]))

    print(ans)


if __name__ == '__main__': main()

D - Root M Leaper

D - 問題

$N \times N$ のマス目の各マスについて， $(0, 0)$ よりスタートして次の桂馬跳び/ナイト跳びを適切に行った時の最短移動回数を求めよ．
桂馬跳び: $(i, j)$ から， $(i-k)^2+(j-l)^2 = M$ を満たす $(k, l)$ へ移動する．

D - 解法

可能な跳び方 $dr$ をあらかじめ次のように求める．
$dr = \{(\pm dx, \pm dy), (\pm dx, \mp dy) | dx^2 + dy^2 = M, 0 \leq dx, dy \leq N-1\}$
あとは各マスの $(0, 0)$ からの最短移動回数を動的計画法により求めれば良い．

D - ACコード

from collections import deque


def main():
    N, M = map(int, input().split())

    ans = solve(N, M)
    _ = [print(*a) for a in ans]


def solve(N, M):
    dp = [[-1]*N for _ in range(N)]
    dp[0][0] = 0

    dr = make_dr(N, M)

    deq = deque([(0, 0)])
    while deq:
        x, y = deq.popleft()
        dist = dp[x][y]

        for dx, dy in dr:
            nx, ny = x+dx, y+dy
            if 0 <= nx < N and 0 <= ny < N and dp[nx][ny] == -1:
                dp[nx][ny] = dist+1
                deq.append((nx, ny))

    return dp


def make_dr(N, M):
    dr = set()
    for i in range(N):
        if i**2 > M: break
        for j in range(i, N):
            if i**2 + j**2 > M: break
            if i**2 + j**2 == M:
                dr |= {(i, j), (j, i), (-i, j), (-j, i), (i, -j), (j, -i), (-i, -j), (-j, -i)}

    return dr


if __name__ == '__main__': main()

E - Add and Mex

E - 問題

長さ $N$ の整数列 $A$ について，次の操作を $M$ 回行う．
操作: 各 $i (1 \leq i \leq N)$ について，A[i] += i．
各回の操作後， $A$ に含まれない最小の非負整数mex(A)を求めよ．

E - 解法

各回の答えは必ず0以上 $N$ 以下．
A[i] += iという処理が調和級数のオーダーとなることから，各回操作後の $A$ の要素のうち0以上 $N$ であるものをs = set()で保持すれば良さそう．
また，mex(sorted(s))は二分探索により求められる．
ここまで実装できたのが残り10分．そこから焦りながらデバッグを行ってなんとか時間内にAC．

E - ACコード

def main():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))

    st = [set() for _ in range(M+1)]

    for i in range(N):
        ai = A[i]

        fr = max(0, -int(ai//(i+1)))
        ai += fr*(i+1)

        for x in range(fr, M+1):
            if ai > N: break
            st[x].add(ai)
            ai += i+1

    for s in st[1:]: print(meguru(sorted(s)))


def meguru(arr):
    ng, ok = -1, len(arr)

    while abs(ok-ng) > 1:
        md = (ok+ng)//2
        if arr[md] > md: ok = md
        else: ng = md

    return ok


if __name__ == '__main__': main()

感想

水色ボーダーになんとか乗ることができて良かった
とりあえず問題タイトルからキーワード（ $Mex$ ）を拾えたのが我ながら偉かったです