PythonでAtCoder Beginner Contest 154参加記

50の手習いで、pythonでのプログラミングを始めました。モチベーション維持のためにAtCorderでのBeginners Contestに参加してます。

今回は、AtCoder Beginner Contest 154参加記です。

Contents

1 結果
2 恥ずかしながら回答紹介
3 解説、回答例を見て
4 今後に向けて

結果

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

はるきちの回答は、以下の通りです。

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)

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)

超絶そのままコーディングの多重ループです。ただ、他の方法も直ぐに思い浮かばず、まあ、とりあえず書いてみようかという感じで書き始めました。

まず、K==1の場合はなんとかなって。K==2を書き足してみたらなんとかなって。

このまま行けるのかと・・・・、ですがK==3は実行時間オーバーになりました。ただ、もう引き返して書き直す時間もないので、なんとかならないかと思ったところ。K==3についてはループを２つに分けることと、後半の内側ループは逆向きにすることで処理がはしょれることを思いつきました。

実行時間 931msでなんとかAcceptになりました。

これが通った時点で、残り8分くらいでした。

F問題を大急ぎで書いて提出したのですが、エラーとなってしまいました。実は、最初は適当に決めたバッファのサイズが小さくてエラーになったのですが、直ぐにはそれに気が付かないまま、コンテスト終了となりました。

ただ、エラー修正後も実行時間がNGでしたので、仕方ないですね。

解説、回答例を見て

AtCorderのBeginners Contestでは、解説と回答例があります。

E問題は、DP（動的計画法）という手法で解くとのこと。競技プログラミングでは、定番の手法のようです。

解説ビデオを見ていると、解説されている方は、サクッと計算量を見積もったり、あっという間にコーディングしていって完成させてしまいました。

競技プログラミングで難易度の高い問題を解くには、コーディングテクニックに加えて数学の素養や知識が必要みたいです。はるきちも高校生か大学入りたてのころだったら、もう少し頑張れたと思いますが、今回も組み合わせのコンビネーションってどうやって計算するんだっけ？というレベルでしたので、道は険しいと思いました。

ですが、コンテストのおかげで、Pythonの基本的なところは多少分かってきた気がしました。

今後に向けて

コンテストも今は楽しいのですが、数学の素養の必要性が感じたので早晩行き詰りそうです。ただ目標は、「Python＆Excel＆Webデータの連携で何かサービスを作りたい」なので、もう少しそちらに向けたライブラリや実際のWebデータ取得の練習でもしてみようかと思っています。

楽しめるうちは、コンテストにも参加してみます。

はるきち