論理的思考力を上げたい！という思いで、以前AOJの競技プログラミングの問題を解いたりしていましたが、最近はAtCoderに登録して過去問を解いています。
そこでまた心動かされたので記事として残します。
問題
以下リンクから。
atcoder.jp
問題文の要約
お札（一万、五千、千）N枚で金額Y円になるケースはあるか？
- ある場合はそれぞれの枚数を出力（複数パターンあっても出力は1つのみで可）
- ない場合はないことを表す値（-1 -1 -1）を出力
（例１）
N=9,Y=45000 ⇒ 9枚で45,000円 の場合
一万*4枚、五千*0枚、千*5枚で条件満たすため、"4 0 5"を出力で正解。
一万*0枚、五千*9枚、千*0枚でも条件満たすため、"0 9 0"でも正解。
（例２）
N=20,Y=196000 ⇒ 20枚で196,000円 の場合
どんなケースでも満たすものはないので、"-1 -1 -1"を出力で正解。
私の提出したコード
def calc(N, Y): ten_max = Y // 10 for ten in range(ten_max + 1): y_1 = Y - 10 * ten if y_1 == 0: if ten == N: print(ten, 0, 0) return else: continue five_max = y_1 // 5 for five in range(five_max + 1): y_2 = y_1 - 5 * five if y_2 == 0: if (ten + five) == N: print(ten, five, 0) return else: continue one = N - (ten + five) if y_2 == one: print(ten, five, one) return print(-1, -1, -1) N, Y = map(int, input().split()) Y //= 1000 calc(N, Y)
コードの意図
一万円札の枚数をループ
五千円札の枚数をループ
残り千円札の枚数を計算
枚数と金額が一致するものがあれば出力して終わり
・・・余りにも愚直です。
ほぼ総当たり。
しかしこれより良い解法が思いつきませんでした。
提出結果
一応Accepted（正解）でした。
が、他の問題と比べると実行速度があまりにも遅い。
絶対他の解法ある、そうに決まってる。
他の人の提出コードを見て感動した
与えられた条件から式変形して変数を減らしてました。
感動した。
･･･金額の等式
･･･枚数の等式
↓ これを式変形していって
および
を、
だけで表せるようにし、後は
（一万円札の枚数）のループだけで解いていました。
こういう発想をちゃんとできないといけない世界なんだなと痛感。
終わりに
競技プログラミングの問題を解いてみた - アウトプットブログ
↑の記事の問題を解いたときにも思いましたが、発想の転換というか、違ったアプローチがないか考えるの本当に大事。
ただこういうのって急に思いつくかと言われたら難しいし、やっぱりできるだけたくさんの問題を解いて引き出しを増やしていくというのが正しい道筋だと思いました。
ということで隙間時間見つけて、論理的思考力を高めていきます。
終わり。
