Flying Cat Penguin

ゆるゆる仕事、ソフトウェアテスティング関連のことについて綴ります。

AtCoder 修行日記#86

Python AtCoder

86日目
ABCのC問題に取り組み中。
茶色レベルのD問題も余裕があれば取り組み中。

勉強用のコンテンツはここから。
https://kenkoooo.com/atcoder/#/table/

進捗と一言感想

[C問題] 1問(残り125問)

ABC011: 123引き算

今回は典型的な動的計画法の問題…当然まだすぐにできないので他の方のコードを見て、写経しつつAC。

n = int(input())
ngNumber = []
for _ in range(3):
  ngNumber.append(int(input()))

infinity = float("inf")
dp = [infinity for _ in range(301)]

dp[n] = 0
for i in range(n,0,-1):
  if i in ngNumber:
    continue
  for j in range(1,4):
    #print(dp[:n+1],dp[i]+1,dp[i-j],j,i)
    dp[i-j] = min(dp[i]+1, dp[i-j])

if dp[0] <= 100:
  print("YES")
else :
  print("NO")

入力例2でprintを実行してみると下記のような動きになる。
[それぞれの数にできる最小の計算回数] 計算開始の数から計算した時の回数 その数の暫定の最小計算回数 引く数 計算開始の数

[inf, inf, inf, inf, inf, 0] 1 inf 1 5
[inf, inf, inf, inf, 1, 0] 1 inf 2 5
[inf, inf, inf, 1, 1, 0] 1 inf 3 5
[inf, inf, 1, 1, 1, 0] 2 1 1 3
[inf, inf, 1, 1, 1, 0] 2 inf 2 3
[inf, 2, 1, 1, 1, 0] 2 inf 3 3

下記の文献を参考にしていましたが、基本的にはdpテーブルの中身を見て1ステップずつ確認するというほうがいいですね。
動的計画法超入門！ Educational DP Contest の A ～ E 問題の解説と類題集 - Qiita

atcoderの動的計画法のまとめなんかあれば集中的に解いてみると良さそう。

参考

https://kenkoooo.com/atcoder/#/user/dandan611?userPageTab=AtCoder+Pie+Charts
Aizu Online Judge
www.youtube.com

目標
  • まず、今年中に茶色コーダー
学習方針

以上。