ケーキ同好会でも、プログラミングは必須スキルです！ 作：蒼(DPD)
D - Brute Force Attack 1
実行制限時間:$2$sec/メモリ制限:$1024$MB
配点:$200$点
問題文
あなたは自分でかけたデジタル錠の暗証番号を忘れてしまいました。
かろうじて、暗証番号の桁数 $N$ と各位の和 $S$ は思い出すことができました。
条件からあり得る暗証番号が何通りあるかを出力してください。
制約
入力はすべて整数
$1 \leq N \leq 6$
$0 \leq S \leq 9\cdot N$
入力形式
$N\ S$
入力例1
$\texttt{2 5}$
出力例1
$\texttt{6}$
条件からあり得る暗証番号は、$\texttt{05,14,23,32,41,50}$ の$6$通りであるので、$6$ と出力してください。
入力例2
$\texttt{4 12}$
出力例2
$\texttt{415}$
えっと、暗証番号を桁ごとに足した数字を覚えているから、それを満たす暗証番号が何通りあるかを調べたいんだね。
何というか、暗証番号は忘れたのに、暗証番号を桁ごとに足した数字は覚えてるのおかしいよね。
問題に一通り目を通したので、ざっと考えてみる。
......ナニコレ。何通りあるかって数学の問題みたい。
競技プログラミングって、数学力も必要だったりするの？私あんまり数学得意じゃないから困るな。
確かに今考えると、前ひまり先輩が解いていて私に教えていた問題はフィボナッチ数列が関係してた。階段の上り方のやつだね。
悲しんでいてもしょうがないので考えます。
えっと、何通りあるかって数学の単元だと「場合の数」だよね。
場合の数ってどうすれば求められるんだっけ。
積の法則とか和の法則みたいな、かすかに脳に残っている単語はあるけど、それらの具体的な方法を思い出せない。
シャーペンで適当に$＋$とか$\times$とかを書いてみる。うーん？なんかしっくりこない。
あ、そういえば何通りあるかって、最悪全部書き出すと求められるんだよね。
テストを受けたときに樹形図とか書いてたのを思い出した。
力技で、数学っぽくないなと思ったんだよね。
......ん？「全部」書き出すって競技プログラミングでもやったかも。
多分、最初の問題を解いた後に哀先輩から聞いた気がする。
あのとき、哀先輩なんて言ってたんだっけ？あの後ひまり先輩がガトーショコラをお皿に乗せて部室に走って来たのは思い出せるんだけど。
「全探索」だ。全部調べるのが競技プログラミングの基本だから、覚えといてねって哀先輩が言ってた。
この問題も全探索が使えそう。
暗証番号をfor文で全部調べることにしよう。
それぞれの暗証番号に対して、桁数が$N$と等しいかどうかと、各桁の和が$S$に等しいかどうかを調べて、両方合ってるものだけ数えれば答えが求まりそう。
よし、答えが求まりそうな方針は立った。
あ、この問題、数字の入力形式が空白区切りだ。これちょっと面倒くさいんじゃなかったっけ。
そうそう、哀先輩が口頭で言ってて全然分からなかったやつだ。メモに書いてるはずだから見よう。
まとめメモ
・ print("") で文字を出力する
・ x = で文字や数を記憶しておける
・ x = input() で文字を入力する
・ x = int(input()) で数を入力する
・ if 条件式: で条件を満たしたときだけ処理をすることができる(: ←コロンを忘れずに！)
・ else: をifの後ろに付けると、ifが実行されなかったときだけ処理をすることができる
・ for i in range(N): で処理を$N$回繰り返すことができる(iは0から！)
・ A = [] で配列(変数がたくさんあるもの)を作る
・配列の$i$番目の値には、A[i]でアクセスする(0番目から！)
あれ、メモに書くの忘れてた！どうしよう。
あのときのプログラムを見れたらコピペできるんだけど、毎回プログラムを全部消して書き直してるから復元しようがない。
ちょっとこれは反省ポイントかも。
今度から忘れそうな文法はメモに書くの忘れないようにしないと。
困った。教科書から見つけられるかな。この教科書から探すの大変なんだよね、分厚いから。
探す範囲は最初の方だけだから何時間も見つからないことはないけど、今は1秒でも早く見つかってほしい。
自分でもほとんど見れてないんじゃないかと思うくらいの速さでページを捲って確認していく。
あった。$\texttt{map(int,input().split())}$だ。
そうだ、哀先輩が言ってた時の問題は、身長の最大値を探す問題だったね。
まっぷいんといんぷっとすぷりっと。
......先輩方がいないと静かだね。ちょっと寂しさを感じた。
えっと、この問題だと変数$\texttt{n}$と$\texttt{s}$をカンマで区切って、
n,s = map(int,input().split())
って書くと良さそう。
よし、本題に戻って桁数が$N$と等しいかどうかと、各桁の和が$S$に等しいかどうかを調べる方法を考えよう。
そもそも、$N$桁の数字だけfor文で調べることにすればいいかな。
うーーん。どうしよう。
数字の前に0がある、05みたいなものはfor文で調べるときは$\texttt{i = 5}$になって、2桁から1桁に減っちゃう。
\[05 \xrightarrow{\text{for文}} 5\]
どうすればいいだろう。
頭の中だけで考えていたって仕方がないし、具体例を作ってみよう。
例えば、3桁以下の数字をfor文で全部調べるときはどうする？
初めて4桁になる数字1000の前まで数えれば良いよね。
1000はつまり
\[1000 = 10\cdot10\cdot10 = 10^3\]
だから、for文で10を3回掛けたら計算できる。
これを踏まえて考えると、$N$桁以下の数字をfor文で全部調べるなら、$10^N$未満の数まで数えればいいね。
よし。あとは、$N$桁だけを調べる方法を考えればいい。
よく考えたら、$N$桁より桁数が少ない数も、前に0がつくだけだから別に分けて考えなくてもいいんじゃない？
ちょっと天才かもしれない。
つまり、$N$桁の数字じゃなくて、$N$桁以下の数字をfor文で全部調べれば良い。
だから、さっき考えたfor文の計算方法がそのまま使える！
ちょっと一息。水を一口飲む。考えないといけないことはあと半分。
暗証番号の各桁の和が$S$かどうかを調べることが必要。これもすぐには思いつかない。
各桁の和を求める前に、各桁を求める方法を考えた方が良さそう。
各桁の数字が求まれば、各桁の和はfor文で足していけば求まるからね。
ある数の一桁目は、どうやって求められる？
\[341 \xrightarrow{\text{何らかの方法}} 1\]
これ、さっき解いた問題で考えた偶数か奇数かを判定する方法に似てるかも。
あのときは、一桁目が$0,2,4,6,8$かどうか判定するのは難しいから、2の倍数かどうかを判定したんだった。
2の倍数かどうかは、プログラミングだと2で割ったときの余りで区別できたんだよね。
その問題みたいに、とりあえず何かの数で割った余りを考えてみようかな。
あ、元の数を10で割った余りの数字は、一の位と等しくなりそう。例えば、123で考えてみよう。
\[123 \div 10 = 12 \ \text{あまり}\ 3 \]
になる。
$123 = 12 \times 10 + 3$ みたいに、10の位より上の数字は割ったときに消えるから。
よし。これで一の位を求める方法は見つかった。
次に、数字の十の位を求めることを考えよう。今回は100で割った余りで求まる？
いや、それだと、
\[123 \div 100 = 1~\text{あまり}~23\]
みたいに一の位も一緒に出てきちゃう。
ここから一の位を消す方法が欲しい。
たくさん書いてたら、チラシの裏紙の余白がなくなっちゃった。新しいものに替える。
うーん。10で割った商はどうだろう。
さっきの123の例で考えると、
\[123 \div 10 = 12~\text{あまり}~3\]
で、確かに商12を見ると123から一の位が消えた12が計算できてる。
つまり、10で割るという計算は、一の位を消す計算になってる。
\[123 \xrightarrow{\div 10} 12\]
このあとに、この数の一の位を計算すれば良さそう。
この方法を繰り返していけば、各桁を一つづつ求められそう。試しに紙に書いてみる。
こんな感じで、10で割った商が0になるまで続けていけば良さそう。
でも、Pythonで割り算をすると、小数点が出ちゃうのが困るんだよね。
最初の問題の 14 / 2 = 7.0 みたいに。
あ、でも割った余りを計算することができるから、割った商を求める記号もありそうじゃない？
さっき割り算の余りを計算する記号を調べたときにページを開いた。えっと、割り算の下だよね。
あった。スラッシュ二つで $\texttt{123 // 10}$ と書くと良いらしい。
解けた！だいぶ難しかった。
ぎりぎりの時間と思考で脳が悲鳴を上げているけど、もうちょっと頑張らないと。
ここまでできて時間切れはないよ。急がなきゃ。
n,s = map(int,input().split())
max = 1
for i in range(n):
max *= 10
answer = 0
for i in range(max):
sum = 0
x = i
for j in range(n):
sum += x % 10
x //= 10
if sum == s:
answer += 1
print(answer)
できた！入力例を試している時間はない。すぐにコピペして提出する。
提出ボタンを押すと同時にコンテストが終わった表示が出た。
もう新しく提出はできない。
あとは、今提出したプログラムが合ってることを祈るのみ。
結果
WJ...
お願い、間違えていませんように...
AC
よし！正解だ！思わずガッツポーズをしてしまう。
しばらく余韻に浸っていたけど、せっかくだから順位表も見てみよう。最終順位は何位になったんだろう。
︙
790 laure 550点
791 灰崎ゆい 550点
792 modal\_p 350点
︙
791位だ。やった、結構高いんじゃない？最初に順位を見たときは3700位くらいだったから、3000位くらい上がってる。
あ、よく見たら点数が550点の人の中で一番低い順位だ。
ということはつまり、私が一番最後に四問目の問題を解いたんだ。本当にぎりぎりだったね。
そういえば、今回のコンテストの成績に応じてレートって言う数字が変動するんだったよね。どれくらいになったんだろう。
灰崎ゆいさんのPBC028での成績：791位
パフォーマンス：420相当
レート：0→52 (+52)
えっと、今の私のランクが
次のランクの
これ次のランクに上がるまで時間かかるやつかも。
レートの上に表示されてるパフォーマンスというのは、今回のあなたの成績は、レートがこれくらいの人相当ですよっていう数字らしい。
レート400以上で次のランクに入るらしいから、今回は次のランク相当の成績らしいね。
やったね。
競技プログラミング最初にしては頑張った方じゃないかな。
自分で自分を褒めます。自分偉い！
あと、忘れないうちにアカウント名を本名から変えておこう......