📝

AtCoder Beginner Contest 272 レポート

2022/10/08に公開約4,800字

摘要

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

ABC272

https://atcoder.jp/contests/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()

https://atcoder.jp/contests/abc272/submissions/35466266

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()

https://atcoder.jp/contests/abc272/submissions/35476535

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()

https://atcoder.jp/contests/abc272/submissions/35478313

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()

https://atcoder.jp/contests/abc272/submissions/35493004

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()

https://atcoder.jp/contests/abc272/submissions/35507445

感想

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

Discussion

ログインするとコメントできます