50の手習いで、pythonでのプログラミングを始めました。モチベーション維持のためにAtCorderでのBeginners Contestに参加してます。
今回は、AtCoder Beginner Contest 154参加記です。
結果
A~Fの6問中、5問がAcceptされました。思ったより良かったです。
今回の参加で3回目なのですが、BeginnersContestの感じだと、最初の4問はなんとかなる。難易度の上がるE問題とF問題が時間内になんとかなるのかどうかの勝負という感じです。
今回は、E問題がラッキーにもAcceptされました。
恥ずかしながら回答紹介
今回は、E問題がAcceptされたのがラッキーだったと思いますので、その紹介です。
問題は、以下の通りです。コンテストでのE問題のページはこちら
■問題文
1以上N以下の整数であって、10進法で表したときに、0でない数字がちょうどK個あるようなものの個数を求めてください。
■制約
1≤N<10^100
1≤K≤3
はるきちの回答は、以下の通りです。
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 26 27 28 29 30 31 32 33 34 35 |
N = int(input()) K = int(input()) res = 0 if K == 1: for i in range(1,10): for j in range(len(str(N))): if i*10**j <= N: res += 1 if K == 2: for i1 in range(1,10): for i2 in range(1,10): for j1 in range(len(str(N))-1): for j2 in range(len(str(N))-1-j1): if i1*10**(j1+j2+1)+i2*10**j2 <= N: res += 1 if K == 3: for j1 in range(len(str(N))-2-1): for j2 in range(len(str(N))-2-1-j1): for j3 in range(len(str(N))-2-1-j1-j2): res += 1 res = res * (9**3) for j1 in range(len(str(N))-2): for j2 in range(len(str(N))-2-j1): j3 = len(str(N))-2-j1-j2-1 for i1 in range(1,10): for i2 in range(1,10): for i3 in range(9,0,-1): if i1*10**(j1+j2+j3+2)+i2*10**(j2+j3+1)+i3*10**+j3 <= N: res += i3 break print(res) |
超絶そのままコーディングの多重ループです。ただ、他の方法も直ぐに思い浮かばず、まあ、とりあえず書いてみようかという感じで書き始めました。
解説、回答例を見て
AtCorderのBeginners Contestでは、解説と回答例があります。
E問題は、DP(動的計画法)という手法で解くとのこと。競技プログラミングでは、定番の手法のようです。
解説ビデオを見ていると、解説されている方は、サクッと計算量を見積もったり、あっという間にコーディングしていって完成させてしまいました。
競技プログラミングで難易度の高い問題を解くには、コーディングテクニックに加えて数学の素養や知識が必要みたいです。はるきちも高校生か大学入りたてのころだったら、もう少し頑張れたと思いますが、今回も組み合わせのコンビネーションってどうやって計算するんだっけ?というレベルでしたので、道は険しいと思いました。
ですが、コンテストのおかげで、Pythonの基本的なところは多少分かってきた気がしました。
今後に向けて
コンテストも今は楽しいのですが、数学の素養の必要性が感じたので早晩行き詰りそうです。ただ目標は、「Python&Excel&Webデータの連携で何かサービスを作りたい」なので、もう少しそちらに向けたライブラリや実際のWebデータ取得の練習でもしてみようかと思っています。
楽しめるうちは、コンテストにも参加してみます。
はるきち