この記事の目的

最近少し競技プログラミングから離れており、エンジニアとしてこれからどのようになっていけば良いかとちょっと悩んでいる時期でもありましたが、心機一転取り合えず技術力向上/何か行動を起こさなければということでAtcoderの問題を解くことを再開しようと思います。

とりあえず、練習をたくさん積んでC・D問題を解けるようになりたいと思います。

A問題

この問題は[0-9]の10種類あるうち、1種類だけ出てこない数字があるのでそれを見つけてくださいという内容です。
案としては、

入力を昇順にソートして0から確認していく(ソートで時間かかるけど全探索は済む)
[0-9]のリストを作成して入力の先頭から確認していく(ソート処理は必要ないけど全探索しなければいけない)
入力の数字全部足して45-入力の合計をする

考えつくのはこれくらいでした。
3つ目の考え方をコードにすると以下の感じです。他の案より簡潔で良いかもしれません

num_list = [int(a) for a in input()] 
print(45-sum(num_list))

B問題

3つの入力値から必要な条件を満たす演算をする問題です。

とりあえず、AがB以上になるまでwhileループしてみましょう。以下のような感じです。

a,b,k = map(int, input().split())
answer = 0

while True:
  if a >= b:
    break
  else:
    a *= k
    answer += 1
print(answer)

正直、whileで無限ループにするのはBが果てしなく大きい時とか、最終的に答え出せなかった時に困りそうですが今回のに制約的にKは1ではないので無限に計算していればいずれは解答にたどり着くことができるので、whileで正答できました。

1. 1≤A≤B≤10^9
2. 2≤K≤10^9
3. 入力は全て整数

C問題

はい、来ましたね問題文読んでもイメージ湧かなくて詰む系のやつ。
こういうものって大体動的計画法とか計算量を減らすアルゴリズムを使わないといけません。

とりあえず動的計画法(Dynamic Programming)のアルゴリズムの解説などみながら解いてみましょう。
まずは、以下のように計算したものを入れる箱を作りましょう。

n,m,k = map(int, input().split())
dp = [0] * n * m

動的計画法は漸化式のように、dp[i+1] = dp[i] + ？という感じになるのは知っているのですが、どうやら今回は数列の総和が条件に入っているため一工夫が必要なようです。

詳しくは、公式解説の方の説明が非常にわかりやすかったです。

dp[数列から選択する要素の数][総和]という2重配列にするようです。解説の部分だと、以下のところです。

総和が4である「1 3」と「2 2」は数列の3番目以降を選ぶという観点では、条件が全く同じになる。

ということで、2重配列になることをふまえると以下のように変化します。

n,m,k = map(int, input().split())
dp = [[0] * (k+1) for _ in range(n+1)]
dp[0][0] = 1

そして計算の部分ですね。
長さがnということで、一番外のforはn回繰り返す。
そして2個目のforでkを繰り返し使います。
なぜkかというと、kはこれまでの総和の計算結果ということなのでこれに数列の次の数字を足すことで求めたい総和の要素番号はわかるといった感じですかね(解釈が怪しいですが、、)
最後のforで数列の総和を計算するといった構成に。
計算部分では、制約条件2つ目をifとして、動的計画法の計算と最終的な計算結果は余りを出さなければいけないので各計算ごとに余りを算出しておきましょう

for i in range(n):
    for j in range(k):
        for kk in range(1,m+1):
            if j + kk <= k:
                dp[i+1][j+kk] += dp[i][j]
                dp[i+1][j+kk] %= MOD

そして、全て計算し終わったところで、以下のように選択しなければならない要素(=n)と総和がkよりも小さい計算結果を足してmodで余りを算出するという工程を踏めば無事に答えまで辿り着けるはずです。

ans = 0
for l in range(1,k+1):
    ans += dp[n][l]
    ans %= MOD
    l += 1
 
print(ans)

最後に

やはりC問題が解けないですね、、(永遠の課題)
動的計画法など、アルゴリズムがどういったところで活かされるかを理解しながらやらなければ、学んでもうまく活用できずに終わってしまいそうなので実践的な使用例などを参考にしつつ、理解を深めていきたいです。

AtCoder Beginner Contest 248

この記事の目的

A問題

B問題

C問題

最後に