AtCoder Beginner Contest 248 - プログラミングの備忘録

こんにちは。
今回は、前回の最後に参加した「AtCoder Beginner Contest 248」の復習をしてみます。

taq.hatenadiary.jp

参加してみたいという方は以下からどうぞ。

atcoder.jp

復習
- 振り返る
- 見てみる
また参加する
まとめ

復習

振り返る

まずは、自分のコードを振り返ります。

プログラムを書いたのは問題A、B、Dなので、それぞれ見てみます。
（問題文は省略します。）

問題A

「A - Lacked Number」

0~9までの数字からなる9文字の文字列の中で、欠けている数字を見つけるというものでした。

s = input()
 
t = []
for i in s:
    t.append(int(i))
 
n = [0,1,2,3,4,5,6,7,8,9]
 
for i in n:
    if i not in t:
        print(i)
        break

入力した文字列を1文字ずつに分けて配列tに入れ、0~9までの数字を格納した配列nに対してfor i in nとif i not in tで配列nの中に配列tの要素で無いものがあったらそれを出力して答えとしています。

が、よく考えたら配列nは必要ないですね。焦っていたのだということにします。
修正版は「見てみる」の項でつくります。

問題B

「B - Slimes」

叫ぶたびに増えるスライムの数を目標値以上にするには何回叫べば良いかを計算するというものでした。

A, B, K = map(int, input().split())
 
c = 0
while A < B:
    c += 1
    A *= K
 
print(c)

今のスライムの数Aが目標値B以上になるまでwhile文で繰り返し、その間中叫んだ回数cに1ずつ足し、今のスライムの数をK倍するという処理を行って、A <= Bが満たされたらcを出力して答えとしています。

問題D

「D - Range Count Query」

ある数列のある範囲内で、指定された数字の数を数えるというものでした。

N = int(input())
A = list(map(int, input().split()))
Q = int(input())
 
for i in range(Q):
    L, R, X = map(int, input().split())
    
    B = A[L-1:R]
    print(B.count(X))

クエリを読み込むたびに指定された範囲の数列を取り出し、指定された数字Xの数を数えて出力して答えとしています。

しかし、サンプルではうまくいきますが、クエリの数が最大で$2 \times 10^{5}$個あるようなのでクエリが増えると実行時間制限を超過してしまいます。
「ABC 247」にもあった、実際に並べるのではなく数で管理するようにする方法のように工夫が必要そうだは思ったのですが、良い方法が思いつきませんでした。

見てみる

さて、ここまでで本番で書いたプログラムを振り返りました。
ここからは答えを見ながらにはなりますが、改めてコードを書いてみます。

以下、他の方のコードを参考にしつつ自分がわかりやすいように変えて載せています。

問題A

配列nを無くしてfor i in range(10)で代わりとしました。
また、配列tをつくる処理を内包表記を使って書いてみました。

t = [int(i) for i in input()]

for i in range(10):
    if i not in t:
        print(i)
        break

また、賢いなと思ったのですが、与えられた文字列の数字を全て足して0~9までの和45との差をとれば、その答えが欠けた数字になります。

s = input()

a = 0
for i in s:
    a += int(i)

print(45-a)

Editorial - UNIQUE VISION Programming Contest 2022（AtCoder Beginner Contest 248）

問題B

100点ということにします。

問題C

「動的計画法（Dynamic Programming）」というものを使うと良いらしいです。
動的計画法は、これはこれでいくつか記事ができるくらい奥が深そうなものですが、簡単に言うと計算結果を保存しながら問題を解いていく方法です。

AtCoderに練習問題がありました。

atcoder.jp

良く分かる解説などが載っています。

qiita.com

というわけで、実際に書いてみます。

n, m, k = map(int, input().split())

dp = [[0 for i in range(k+1)] for j in range(n+1)]
dp[0][0] = 1
for i in range(n):
    for j in range(k):
        for l in range(1, m+1):
            if j+l <= k:
                dp[i+1][j+l] += dp[i][j]
a = 0
for i in range(k+1):
    a += dp[n][i]

print(a % 998244353)

Submission #31152674 - UNIQUE VISION Programming Contest 2022（AtCoder Beginner Contest 248）

計算結果の保存用に配列dpをつくります。（全て初期値は0）
dp[数列の要素数][数字の和]という形になっており、dp[0][0]は数列$A=(0)$のときで和が0になるのは何通りかを表すので、1となります。
そして、dp[0][0]から順々に計算していきます。

数列の要素を1つ増やし（i+1）、要素数が1つ少ないときの和jに$1～M$までの数lを足したとき（j+l）に、和が最大値$K$を超えない（j+l <= k）ならば、要素数が1つ少ないときの組み合わせ数dp[i][j]がdp[i+1][j+l]の組み合わせの一部になるため、dp[i+1][j+l] += dp[i][j]で加える、という処理を繰り返します。
最後に、問題文の条件は和が$K$以下になる組み合わせの数を998244353で割った余りで答えるというようになっているので、要素数$N$の行の値を全て足し（a += dp[n][i]）、998244353で割った余りを出力して答えとしています。