スポンサーリンク

【Python】AtCoder Beginner Contest 011 A,C問題 解答

スポンサーリンク
スポンサーリンク
この記事は約4分で読めます。

A問題 来月は何月?

今が何月かという情報から来月を出力する問題です。

今が12月かそれ以外かで条件分岐をさせてみました。

今が12月である場合は1を出力。今が12月以外の場合は1を加えて出力しています。

今回は問題文に入力される値が1~12という制約があったので、それ以外の値が入力された場合のことについて考える必要はありませんでした。

 

C問題 123引き算

方針

数字Nが与えられるので、1,2,3のどれかの数字を引き算を繰り返し、100回以内に0にできるかを調べる問題です。

ただし、引き算の結果が指定された3つのNG数字になってはならず、最初に与えられた数字NがNG数字だった場合もアウトです。

条件を満たす場合はYES、満たさない場合はNOを出力します。

ざっくりと、以下を100回繰り返す実装にしました。

①N-3がNG数字でなければN=N-3

②N-2がNG数字でなければN=N-2

③N-1がNG数字でなければN=N-1

④NがNG数字ならNOを出力して終了

⑤Nが0ならYESを出力して終了

①~⑤を100回繰り返して0にならなければにNOを出力します。

Nから1,2,3のどれを引いていけば良いのかについてですが、100回という回数制限がある以上、0まではできる限り早く近づいた方が良いので、NG数字にならない限り大きい数で引き算するのが良いかと思います。

解答

入力例3のように3を100回引き続けなければならないのに、途中で57のNG数字になってしまうパターンは、nが60の時に2を引くことになります。(for文内の1つ目のif文の条件式を満たさず、2つ目の条件を満たす)

すると、そのあとは3ずつ引き算していったとしても、100回の繰り返しで0にすることができなくなるため、最後のprint文でNOが出力されます。

解答② 動的計画法

動的計画法を使った解法です。入力例2で考えてみます。

nの範囲は問題文より1~300と決まっているので、301個の要素を持つリストdpを作ります。

dpの各要素は、そのインデックス(何番目の要素であるか)が0~nまでの数字を表します。

dpの各要素には、dp[0](0番目の要素、つまり0)に至るまでの最小操作回数を保存します。最小の操作回数をしらべるする際にmin関数を使うので、dpの各要素の初期値を無限大(inf)としておきます。

dpの各要素はこのようになります。

dp=[inf,inf,inf,inf,inf,0,inf・・・・・,inf,inf]

NG数字は1,2,4なので、このようになります。

[OK,NG,NG,OK,NG,OK]

■1つ目のforループの1周目の操作

①i=5で、1を引く場合

dp[i]+1=dp[5]+1=1、dp[i-j]=dp[5-1]=infより、dp[4]には1を入れます。

②i=5で、2を引く場合

dp[i]+1=dp[5]+1=1,dp[i-j]=dp[5-2]=infより、dp[3]には1を入れます。

③i=5で、3を引く場合

dp[i]+1=dp[5]+1=1,dp[i-j]=dp[5-3]=infより、dp[2]には1を入れます。

■1つ目のforループの2周目の操作

①i=4で、1を引く場合

dp[i]+1=dp[4]+1=2,dp[i-j]=dp[4-1]=1より、dp[4]は変わらず1のままです。

②i=4で、2を引く場合

dp[i]+1=dp[4]+1=2,dp[i-j]=dp[4-2]=1より、dp[3]は変わらず1のままです。

③i=4で、3を引く場合

dp[i]+1=dp[4]+1=2,dp[i-j]=dp[4-3]=infより、dp[1]には2を入れます。

上記の操作をn回繰り返します。

するとdp[0]に最終的な引き算を行った最小回数が記録されるので、これが100と比較して大きいか小さいかを見れば良いです。

参考にさせて頂いた記事

[Python] ABC011 C (yottagin.com)

【Python】漸化式で実装する動的計画法(DP) – Qiita

 

コメント