📝

AtCoder Beginner Contest 281 レポート

2022/12/10に公開

Python

AtCoder

tech

摘要

ABCD4完でした．D問題にめちゃくちゃ手間取り，まあまあの冷え込みでした．

ABC281

コンテスト名: AtCoder Beginner Contest 281
順位: 2140th / 9226
パフォーマンス: 1054
レーティング: 1267 → 1247 (-20)
コンテスト参加回数: 66

A - Count Down

A - 問題

$N$ 以下の非負整数を大きい方から順に出力せよ．

A - 解法

特筆事項なし．

A - ACコード

def main():
    N = int(input())

    for i in range(N, -1, -1): print(i)


if __name__ == '__main__': main()

B - Sandwich Number

B - 問題

文字列 $S$ が，「英大文字」「6桁の整数」「英大文字」をこの順に連結したものであるか判定せよ．

B - 解法

細かい条件分岐を考えるのが面倒だったので適当に．

B - ACコード

from string import ascii_uppercase as up


def main():
    S = input()

    if len(S) != 8 or S[0] not in up or S[-1] not in up: ans = 'No'
    else:
        for i in range(100000, 1000000):
            if S[0] + str(i) + S[-1] != S: continue

            ans = 'Yes'
            break
        else: ans = 'No'

    print(ans)


if __name__ == '__main__': main()

C - Circular Playlist

C - 問題

長さ $N$ の整数列 $A$ を無限に繰り返すとき，先頭からの和が $T$ となる位置を求めよ．

C - 解法

累積和 $cu$ を作り，x = bisect(cu, T%cu[-1]), y = T%cu[-1] - cu[x-1]と計算する．

C - ACコード

from bisect import bisect


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

    cu = [0]*(N+1)
    for i, ai in enumerate(A): cu[i+1] = cu[i] + ai

    x = bisect(cu, T%cu[-1])
    y = T%cu[-1] - cu[x-1]

    print(x, y)


if __name__ == '__main__': main()

D - Max Multiple

D - 問題

非負整数列 $A$ について，異なる $K$ 個の要素の和のうち $D$ の倍数となるものの最大値を求めよ．

D - 解法

ナップザックDPを用いることは分かった．

$0 \leq A_i \leq 10^9$ の制約をクリアするために $\bmod D$ を考える
DPの更新として，余りで分類した和の最大値をメモする
ナップザックの復元を行う（しかもこれ要らなかった）

この辺に気づかなかったり手間取ったりして88分+2WA．

D - WAコード

def main():
    global N, K, D, A
    N, K, D = map(int, input().split())
    A = sorted(map(int, input().split()), reverse=True)

    ans = knapsack()
    print(ans)


def knapsack():
    dp = [[[False]*D for _ in range(N+1)] for _ in range(N+1)]
    dp[0][0][0] = True

    for i, ai in enumerate(A):
        for j in range(N+1):
            for k in range(D):
                if dp[i][j][k]:
                    dp[i+1][j][k] = True
                    if j < N: dp[i+1][j+1][(k+ai)%D] = True

    if not dp[-1][K][0]: return -1

    sm = 0
    cnt, mod = K, 0
    for i in range(N, -1, -1):
        if not cnt: break
        if dp[i][cnt][mod]: continue

        sm += A[i]
        cnt -= 1
        mod = (mod - A[i])%D

    return sm


if __name__ == '__main__': main()

ヒィヒィ言いながら復元まで実装した挙句WAってしまい，終わったと思った．
$A$ を降順にソートしているし大丈夫だと思っていたが，これでは復元した和が最大とは限らない．

D - ACコード

def main():
    global N, K, D, A
    N, K, D = map(int, input().split())
    A = sorted(map(int, input().split()), reverse=True)

    ans = knapsack()
    print(ans)


def knapsack():
    dp = [[[-1]*D for _ in range(N+1)] for _ in range(N+1)]
    dp[0][0][0] = 0

    for i, ai in enumerate(A):  # i番目までの整数から
        for j in range(N+1):  # j個選んで
            for k in range(D):  # S == k mod D となるような和Sの最大値
                x = dp[i][j][k]
                if x == -1: continue

                if x > dp[i+1][j][k]: dp[i+1][j][k] = x
                if x + ai > dp[i+1][j+1][(k+ai)%D]: dp[i+1][j+1][(k+ai)%D] = x + ai

    return dp[-1][K][0]


if __name__ == '__main__': main()

感想

頭が固い日でした．E, Fあたりはまたあとで復習しておきます．