A問題 来月は何月?
|
1 2 3 4 5 6 |
n = int(input()) #変数nに整数型で入力値を代入 if n == 12: #nが12の場合 print(1) #1を出力 else: #nが12以外の場合 print(n+1) #n+1を出力 |
今が何月かという情報から来月を出力する問題です。
今が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数字にならない限り大きい数で引き算するのが良いかと思います。
解答
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
n=int(input()) ng=[] for i in range(3): ng.append(int(input())) #最初に与えられた数字nがNG数字ならその時点でNOを出力 if n in ng: print('NO') exit() #NG数字とならない引き算を100回繰り返します。 for i in range(100): if n-3>=0 and n-3 not in ng: n-=3 elif n-2>=0 and n-2 not in ng: n-=2 elif n-1>=0 and n-1 not in ng: n-=1 if n in ng: print('NO') elif n==0: print('YES') exit() print('NO') |
入力例3のように3を100回引き続けなければならないのに、途中で57のNG数字になってしまうパターンは、nが60の時に2を引くことになります。(for文内の1つ目のif文の条件式を満たさず、2つ目の条件を満たす)
すると、そのあとは3ずつ引き算していったとしても、100回の繰り返しで0にすることができなくなるため、最後のprint文でNOが出力されます。
解答② 動的計画法
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
n = int(input()) ng = [int(input()) for i in range(3)] #infに無限大の数をセット inf = float("inf") #n+1個の要素を持つDPテーブルを用意し、全要素をinfにする dp = [inf]*301 #n+1個目(最後)の要素を0にする dp[n] = 0 #nから-1し、n回ループする for i in range(n,-1,-1): if i in ng: continue #iがNG数字なら↓のforをスキップし、次の周回に移る #1~3までの3回のループを行い、dp[i]の右隣の要素の値に＋１した場合(dp[i]+1)と、1~3を引いた場合(dp[i-j])の小さい方をdp[i-j]に操作回数として記録 for j in range(1,4): dp[i-j] = min(dp[i]+1,dp[i-j]) #dp[0]の値(引き算を行った回数)が100以下か調べる if dp[0] <= 100: print('YES') else: 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
コメント