初めてのAtCoder （ABC114）

昨日（12/2），初めてAtCoderでプロコンに参加した．
プログラミングはちょこちょこやっていたが，まじめに勉強し始めてから1週間経たないうちの挑戦だったので緊張．
結果はABの2完1WAで，パフォは732，レートは46（言語はPython3）．
B問題までを8分で解けたのが大きい気がする．
ただ，残りの1時間30分くらいを全て使ってもC問題が解けなかったためめちゃくちゃ悔しい．
まず試してみたのはABSの白昼夢的な解き方．

main.py

N = input()
counter = 0
 
for i in range(1, int(N)+1):
  a = str(i)
  if '7' in a and a != '':
    a = a.replace('7', '')
    if '3' in a and a != '':
      a = a.replace('3', '')
      if a != '':
        a = a.replace('5', '')
        if a == '':
          counter += 1
print(counter)

これは半分ちょいACだったが，幾つかのケースがTLEで弾かれる．
この後は数学的に解こうとしてREを連発しながらコンテスト終了．

ちなみに模範回答はこれ．

main.py

N = int(input())
 
def dfs(s):
  if int(s) > N: 
    return 0
  ret = 1 if all(s.count(c) > 0 for c in '753') else 0
  for c in '753':
    ret += dfs(s+c)
  return ret
 
print(dfs('0'))

いわゆる深さ優先探索と呼ばれるアルゴリズム（らしい）．
最初は文字列'0'から初めて，そこに'7'か'5'か'3'を付け足していく．
もし繰り返していく過程で文字列に'7', '5', '3'が全て含まれていればretに1が加算されていく．
最初に回答を見た時にパッと理解できなかったので，まだまだプログラミング（＋アルゴリズム）の知識が足りないなと反省．

次回は3完するぞい．