👻

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

2021/01/17に公開

所感

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

A - Two Sequences 2

i=j - 1からi=jに移動した時,増える候補はi=0からi=jまでのA_iB_jの積のj個ある
この中で最も大きいのは,明らかに最も大きいA_iB_iの積
だから,ij以下の時の最大の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_iKの大小関係により,以下の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の範囲で行なえばおk

keyence_b_figure

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

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)

Discussion