📝

AtCoder Beginner Contest 271 レポート

2022/10/02に公開

AtCoder

Python 3

tech

摘要

ABC3完と大敗を喫しました．先月初めて入水したのも束の間，早速緑に出戻りです
敗因としては，

C：漠然とした方針を複数思いつき悩んでしまった
D：方針からDPの漸化式までスムーズに思いつくも範囲外参照に気付けず

というところです．

ABC271

コンテスト名: 京セラプログラミングコンテスト2022(AtCoder Beginner Contest 271)
順位: 2958th / 8491
パフォーマンス: 840
レーティング: 1202 → 1171 (-31)
コンテスト参加回数: 58

A - 484558

A - 問題

0以上255以下の整数 $N$ を2桁の16進表記に変換せよ．

A - 解法

「hex()とかformat()とか使えばいいんだろう」と思いつつ，調べるほどでもないと思い愚直に計算してAC．

A - ACコード

def main():
    N = int(input())
    s = '0123456789ABCDEF'

    ans = s[N//16]+s[N%16]
    print(ans)


if __name__ == '__main__': main()

A - 改良版

N = int(input())

ans = '{:02X}'.format(N)
print(ans)

B - Maintain Multiple Sequences

B - 問題

与えられた $N$ 行の二次元配列について， $s_k$ 行 $t_k$ 列目 $(1 \leq k \leq Q)$ の項を出力するクエリを $Q$ 回処理せよ．

B - 解法

素直に実装してAC．

B - ACコード

def main():
    N, Q = map(int, input().split())
    arr = [[0]] + [list(map(int, input().split())) for _ in range(N)]

    for _ in range(Q):
        s, t = map(int, input().split())
        print(arr[s][t])


if __name__ == '__main__': main()

C - Manga

C - 問題

与えられた長さ $N$ の数列に対し次の操作 $f$ を0回以上任意の回数行って，1から連続して数列に含まれる自然数の個数 $M$ を最大化する． $M$ を求めよ．
$f$ : 数列の要素を2つ選び消去して，任意の自然数を新たに数列に加える．

C - 解法

とりあえず重複する要素についてはそれぞれ1つを残して売り飛ばす弾にしておく．
その上で，1から $M$ までの連続した自然数を全て数列に含むことができるか，始めに用意した弾と $M$ より大きい要素の個数を合わせて足りるかを調べることにした．
ここで，最初から思い付いていた答え決め打ち二分探索を素直に実装すればよかったのに，
「1から愚直にシミュレーションを回しても計算量的に間に合うのでは，またその方が実装が楽なのでは」
と無駄に悩み時間を大きく無駄にしてしまう．
最終的に二分探索で実装するも，探索範囲の上限が $N-1$ としてしまう初歩的なミスにより1WAを経てAC．

C - ACコード

from collections import Counter
from bisect import bisect_right


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

    ans = solve()
    print(ans)


def solve():
    cnt = Counter(A)
    rem = sum(v-1 for v in cnt.values())

    arr = sorted(set(A))
    leng = len(arr)

    ok, ng = 0, N+1
    while abs(ng-ok) > 1:
        md = (ok+ng)//2

        idx = bisect_right(arr, md)
        if 2*(md - idx) <= leng - idx + rem: ok = md
        else: ng = md

    return ok


if __name__ == '__main__': main()

C - WAコード

    ok, ng = 0, N
    while abs(ng-ok) > 1:  ## 探索がN-1で止まってしまう
        md = (ok+ng)//2

D - Flip and Adjust

D - 問題

2個の整数 $(a, b)$ のペア $N$ 組について，各ペアから一つずつ整数を選んでその和を $S$ にすることができるか判定し，可能ならその選び方を求めよ．

D - 解法

ぱっと見ナップサック問題．
和が最小値 $mn$ となる状態からスタートして，適切に選び方を変更することで和を $S-mn$ だけを大きくすることができるかどうかを動的計画法により調べるという方針を立てる．
配るDPで漸化式を立て，可能かどうかの判定だけでなく解の復元についても処理を決め，
制約 $N \leq 10^2, S \leq 10^4, a, b \leq 10^2$ より計算量も問題ないことを確認．
コンテスト終了10分前で実装ができたと確信するも一部ケースでRE．配列の参照エラーであろうことは見当がついたものの時間内にバグ取りできず終了．

D - ACコード（追試）

def main():
    N, S = map(int, input().split())
    arr = [list(map(int, input().split())) for _ in range(N)]

    ans = solve(N, S, arr)
    print(*ans, sep='\n')


def solve(N, S, arr):
    cards = [[h > t, abs(h-t)] for h, t in arr]
    mn = sum(arr[i][cards[i][0]] for i in range(N))

    if mn > S: return ['No']

    if mn == S: return make(cards[i][0] for i in range(N))

    sm = S-mn
    dp = [[False]*(sm+101) for _ in range(N+1)]
    dp[0][0] = True

    for i in range(N):
        for j in range(sm+1):
            if dp[i][j]:
                dp[i+1][j] = True
                dp[i+1][j+cards[i][1]] = True

    if not dp[N][sm]: return ['No']

    for i in range(N-1, -1, -1):
        if not dp[i][sm]:
            cards[i][0] = not cards[i][0]
            sm -= cards[i][1]

    return make(cards[i][0] for i in range(N))


def make(turns): return ['Yes', ''.join('T' if turn else 'H' for turn in turns)]


if __name__ == '__main__': main()

D - WAコード

def solve(N, S, arr):
    cards = [[h > t, abs(h-t)] for h, t in arr]
    mn = sum(arr[i][cards[i][0]] for i in range(N))
    mx = sum(arr[i][1-cards[i][0]] for i in range(N))

    if mn > S: return False  # ここでmxがSより小さい場合についても除外する必要あり

    turns = [turn for turn, _ in cards]
    if mn == S: return make(turns)

    dp = [[False]*(mx-mn+1) for _ in range(N+1)]
    dp[0][0] = True

    for i in range(N):
        for j in range(mx-mn+1):
            if dp[i][j]:
                dp[i+1][j] = True
                if j+cards[i][0] <= mx-mn: dp[i+1][j+cards[i][1]] = True

    if not dp[N][S-mn]: return False  # mx < S の場合エラー

感想

デバッグ下手すぎでした．
新しいアルゴリズムやデータ構造を詰め込む以前に，知っているものを正しく使えるように練度をあげていきたいと思います．