AtCoder キーエンス プログラミング コンテスト 2021 個人的メモ

所感

ab2完
bでバグに気づかずに2wa

A - Two Sequences 2

$i=j - 1$から$i=j$に移動した時，増える候補は$i=0$から$i=j$までの$A_i$と$B_j$の積の$j$個ある
この中で最も大きいのは，明らかに最も大きい$A_i$と$B_i$の積
だから，$i$が$j$以下の時の最大の$A_i$を保持しとけば良い
こうすれば各$i$毎に$O(1)$で済むから，全体で$O(N)$で済む

N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

ans = [0]
a_max = 0
for a, b in zip(A, B):
    a_max = max(a_max, a)
    ans.append(max(ans[-1], a_max * b))

print(*ans[1:], sep="\n")

B - Mex Boxes

サンプル3の場合は図の様に詰めれば良さそう
なので，0から順に$K$個の箱にボールを詰めていけば良さそう

今，$K$個の箱全てに整数$i-1$以下のボールが1以上ずつ詰まっているとする
つまり，全ての箱の蓋の数$x=i$となっているということ
整数$i$のボールは$a_i$個ある
$a_i$と$K$の大小関係により，以下の2つの場合がある

• $a_i\geqq K$
  全ての箱に整数$i$のボールを入れることができ，全ての箱で$x=i+1$になる
  余ったボールは考慮不要なので，適当に詰めたとする

• $a_i\leqq K$
  $a_i$個の箱にのみ整数$i$のボールを入れることができ，それらの$a_i$個の箱が$x=i+1$になる
  一方で整数$i$のボールが入らなかった$K-a_i$個の箱は$x=i$のままである
  そしてこれらのボールが入らなかった箱の$x$はこれ以上大きくならない
  従って，これらの箱は以降考慮する必要が無いので$K=a_i$となる

よって，以上の操作を$i=0$から$0\leqq i\leqq a_i$の範囲で行なえばおｋ

ループ内最後のボールの個数を変える箇所をバグらせてた

from collections import Counter

N, K = map(int, input().split())
A = list(map(int, input().split()))

cnt = Counter(A)
ans = 0
num_ball = K
for i in range(N + 1):
    if num_ball <= cnt[i]:
        continue
    if cnt[i] == 0:
        ans += num_ball * i
        break
    ans += (num_ball - cnt[i]) * i
    num_ball = cnt[i]

print(ans)

C - Robot on Grid

解説ac
https://atcoder.jp/contests/keyence2021/editorial/564

配るDPで考える
ロボットがあるマスから移動することを考える
マスに書いてある文字によって以下の4つに場合分けできる

• Xと書いてある場合
  右か下に移動する
• Dと書いてある場合
  下に移動する
• Rと書いてある場合
  右に移動する
• 書いてない場合
  ↑3つのいずれかを書き込む
  つまり，3通りの内2通りの場合(XかR)で右に移動し，3通りの内2通りの場合(XかD)で下に移動する

これを再帰的に解けば，解を得られそう

H, W, K = map(int, input().split())
grid = [[""] * W for _ in range(H)]
for _ in range(K):
    h, w, c = input().split()
    grid[int(h) - 1][int(w) - 1] = c
MOD = 998244353

dp = [[0] * (W + 1) for _ in range(H + 1)]
dp[0][0] = 1
three_inverse = pow(3, MOD - 2, MOD)
for i in range(H):
    for j in range(W):
        dp[i][j] %= MOD
        num = dp[i][j]
        command = grid[i][j]
        if command == "X":
            dp[i + 1][j] += num
            dp[i][j + 1] += num
        elif command == "D":
            dp[i + 1][j] += num
        elif command == "R":
            dp[i][j + 1] += num
        elif command == "":
            num *= three_inverse * 2
            num %= MOD
            dp[i + 1][j] += num
            dp[i][j + 1] += num

print(dp[H - 1][W - 1] * pow(3, H * W - K, MOD) % MOD)