ブルートフォースアタック！
D - Brute Force Attack1
実行制限時間:2sec/メモリ制限:1024MB
配点:200点
<<問題文>>
あなたは自分でかけたデジタル錠の暗証番号を忘れてしまいました。
かろうじて、暗証番号の桁数 N と各位の和 S は思い出すことができました。
条件からあり得る暗証番号が何通りあるかを出力してください。
<制約>
1 ≦ N ≦ 6
0 ≦ S ≦ 9*N
<入力形式>
N S
<入力例1>
2 5
<出力例1>
6
条件からあり得る暗証番号は、05,14,23,32,41,50 の6通りであるので、6 と出力してください。
<入力例2>
4 12
<出力例2>
415
えっと、桁ごとに足したものを覚えているから、それを満たす暗証番号が何通りあるかを調べたいんだね。
なんというか、暗証番号は忘れたのに、暗証番号を桁ごとに足した数字は覚えてるのおかしいよね。問題に一通り目を通したので、ざっと考えてみる。
ナニコレ。何通りあるかって数学の問題？私、競技プログラミングのコンテストに出てたはずなんだけど。
競技プログラミングって、数学力も必要だったりする？あんまり数学得意じゃないから困る。
確かに今考えると、前ひまり先輩が解いていて私に教えていた問題はフィボナッチ数列が関係してた。階段の上り方のやつね。
えっと、何通りあるかって数学の単元だと「場合の数」だよね。場合の数ってどうすれば求められるんだっけ。
積の法則とか和の法則とか、かすかに脳に残っている単語はあるけど、それらの具体的な方法を思い出せない。
名前に引きずられてシャーペンで適当に＋とか×とか記号を書いてみた。うーん？なんかしっくりこない。
あ、そういえば何通りあるかって、最悪全部書き出すと求められるんだよね。テストを受けたときに樹形図とか書いてたのを思い出した。力技で、数学っぽくないなと思ったんだよね。
......ん？「全部」書き出すって競技プログラミングでもやったかも。多分、最初の問題を解いた後に哀先輩から聞いた気がする。
あのとき、哀先輩なんて言ってたんだっけ？あの後ひまり先輩がガトーショコラをお皿に乗せて部室に走って来たのは思い出せるんだけど。
「全探索」だ。全部調べるのが競技プログラミングの基本だから、覚えといてねって哀先輩が言ってた。この問題も全探索が使えそう。
暗証番号を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秒でも早く見つかってほしい。自分でもほとんど見れてないんじゃないかと思うくらいの速さでページを捲って確認していく。
あった。map(int,input().split())だ。そうだ、哀先輩が言ってた時の問題は、身長の最大値を探す問題だったね。まっぷいんといんぷっとすぷりっと。......先輩方がいないと静かだね。ちょっと寂しさを感じた。
えっと、この問題だと変数nとsをカンマで区切って、n,s = map(int,input().split())って書くと良さそう。
あとは、n桁の暗証番号をfor文で調べることが必要。これは面倒そう。数字の前に0がある、05みたいなものは数字にすると5になって、桁数が変わっちゃうから困るんだよね。
どうすればいいだろう。n桁以下からそこまで難しくなさそうではあるけど。
例えば、三桁以下の数字をfor文で全部調べるなら、初めて四桁になる数字1000の前まで数えれば良いよね。1000はつまり10の3乗だから、for文で10を3回掛ければ計算できる。
つまり、n桁以下の数字をfor文で調べるときは、10のn乗未満の数まで調べればいい。あとは、n桁だけを調べる方法を考えればいい。
よく考えたら、n桁より桁数が少ない数も、前に0がつくだけだから別に分けて考えなくてもいいんじゃない？ちょっと天才かもしれない。
つまり、n桁の数字じゃなくて、n桁以下の数字をfor文で全部調べれば良い。だから、さっき考えたfor文の計算方法がそのまま使える！
ちょっと一息。水を一口飲む。考えないといけないことはあと半分。
暗証番号の各桁の和がSかどうかを調べることが必要。これもすぐには思いつかない。
各桁の和を求める前に、各桁を求める方法を考えた方が良さそう。各桁の数字が求まれば、各桁の和はfor文で足していけば求まるからね。
数字の一桁目は、どうやって求められる？
これ、さっきの問題で考えた偶数か奇数か判定する方法に似てるかも。
あのときは、一桁目が0,2,4,6,8かどうか判定するのは難しいから、2の倍数かどうかを判定したんだった。2の倍数かどうかは、プログラミングだと2で割ったときの余りで区別できたんだよね。
その問題みたいに、とりあえず何かの数で割った余りを考えてみようかな。
あ、元の数を10で割った余りの数字は、一の位と等しくなりそう。例えば、123で考えてみよう。
123 / 10 = 12 あまり 3 になる。123 = 12 * 10 + 3 みたいに、10の位より上の数字は割ったときに消えるから。よし。これで一の位を求める方法は見つかった。
次に、数字の十の位を求めることを考えよう。今回は100で割った余りで求まる？
いや、それだと、123 / 100 = 1 あまり 23 みたいに一の位も一緒に出てきちゃう。ここから一の位を消す方法が欲しい。
たくさん書いてたら、チラシの裏紙の余白がなくなっちゃった。新しいものに替える。
うーん。10で割った商はどうだろう。さっきの123の例で考えると、123 / 10 = 12 あまり 3 で、確かに商を見ると123から一の位が消えた12が計算できてる。
このあとに、この数の一の位を計算すれば良さそう。この方法を繰り返していけば、各桁を一つづつ求められそう。試しに紙に書いてみる。
123
一の位を求める -> 3
10で割った商を求める -> 12
12
一の位を求める -> 2
10で割った商を求める -> 1
1
一の位を求める -> 1
10で割った商を求める -> 0
こんな感じで、10で割った商が0になるまで続けていけば良さそう。
でも、Pythonで割り算をすると、小数点が出てくるんだよね。最初の問題の 14 / 2 = 7.0 みたいに。
あ、でも割った余りを計算することができるから、割った商を求める記号もありそうじゃない？
さっき割り算の余りを計算する記号を調べたときにページを開いた。えっと、割り算の下だよね。
あった。スラッシュ二つで 123 // 10 と書くと良いらしい。
解けた！だいぶ難しかった。ぎりぎりの時間と思考で脳が悲鳴を上げているけど、もうちょっと頑張らないと。ここまでできて時間切れはないよ。急がなきゃ。
<<Python>>
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)
えっと、今の私のランクが灰色で、次のランクの茶色に上がるまではレートをあと348上げないといけないらしい。これ次のランクに上がるまで時間かかるやつかも。
レートの上に表示されてるパフォーマンスというのは、今回のあなたの成績は、レートがこれくらいの人相当ですよっていう数字らしい。
レート400以上で次のランクに入るらしいから、今回は次のランク相当の成績らしいね。やったね。
競技プログラミング最初にしては頑張った方じゃないかな。一つ上のランク相当の成績らしいもんね。自分で自分を褒めます。自分偉い！
あと、忘れないうちにアカウント名を本名から変えておこう......
