📝

AtCoder Beginner Contest 281 レポート

2022/12/10に公開約3,900字

摘要

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

ABC281

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

https://atcoder.jp/users/hannaheptapod/history/share/abc281

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

https://atcoder.jp/contests/abc281/submissions/37135005

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

https://atcoder.jp/contests/abc281/submissions/37144896

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

https://atcoder.jp/contests/abc281/submissions/37149480

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

https://atcoder.jp/contests/abc281/submissions/37171268

ヒィヒィ言いながら復元まで実装した挙句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()

https://atcoder.jp/contests/abc281/submissions/37185250

感想

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

Discussion

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