📝
AtCoder Beginner Contest 281 レポート
摘要
ABCD4完でした.D問題にめちゃくちゃ手間取り,まあまあの冷え込みでした.
ABC281
- コンテスト名: AtCoder Beginner Contest 281
- 順位: 2140th / 9226
- パフォーマンス: 1054
- レーティング: 1267 → 1247 (-20)
- コンテスト参加回数: 66
A - Count Down
A - 問題
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 - 問題
文字列
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 - 問題
長さ
C - 解法
累積和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 - 問題
非負整数列
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ってしまい,終わったと思った.
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あたりはまたあとで復習しておきます.
Discussion