現在の目標

2018年内に茶色になる←イマココ. 現レート 368
- ABC の A, B 問題を全部解く
2018年度内に緑色を取得する
- ABC の C 問題を全部解く
(水色になったら, APG4b で C++ にも手を出す)

今日のおはなし

結論

C 問題以上は, アルゴリズムも学ばないと厳しい
itertools は便利

解いた問題

TLE 祭り

TLE_answer.py

# coding: utf-8
N = int(input())

ans = 0
if N <= 356:
    print(ans)
    exit()


if N >= 777777754:
    N = 777777753

for i in range(357,N+1,2):
    st = str(i)
    if ("0" in st) or ("1" in st) or ("2" in st) or ("4" in st) or ("6" in st) or ("8" in st) or ("9" in st):
        continue
    if ("3" in st) and ("5" in st) and ("7" in st):
        ans+=1
print(ans)

最近 TLE になることが多いので, 制約条件を見るだけで「あ, この手法はダメっぽいな...」というのが分かってきました. 今回は, 1<=N<=10^9 なので, 全探索だと計算が終わりませんでした. 発想としては, N 以下かつ 3, 5, 7 だけで構成される数を作って数え上げたかったのですが, 良い方法が浮かびませんでした.

アルゴリズムとの出会い

模範解答が python でした.

suggested_answer.py

# 模範解答の写経
# coding: utf-8
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"))

ある七五三数に対して, 7 か 5 か 3 を再帰的に付け加え, 数え上げる方法とのことです.

Twitter を見るに, 数え上げる問題(すなわち探索するような問題)を解く上で, DFS(深さ優先探索)や BFP(幅優先探索)というアルゴリズムを知っていることが大前提のようだったので, 勉強を始めました.

以下, 参考になりそうなリンクを貼っておきます.

これらを活用しつつ, 「アルゴリズム図鑑」という書籍で代表的なアルゴリズムの勉強を始めました. 今後は頭の片隅にアルゴリズムを意識しながら, 問題に取り組もうと思います.

これを活用できるようになるには, アルゴリズムを意識しながら問題を解くしかなさそうですね. 精進あるのみです.

itertools との出会い

ほかの方の AC 回答を見てみると, itertools というモジュールがとても便利そうでした.

itertools.py

# coding: utf-8
import itertools
N = int(input())
ans = 0

for i in range(3, len(str(N))+1):
    for ptn in itertools.product((3,5,7), repeat=i):
        if (3 not in ptn) or (5 not in ptn) or (7 not in ptn):
            continue
        a = int("".join(list(map(str, ptn))))
        if a <= N:
            ans += 1
print(ans)

itertools の product メソッドを使えば, 指定の文字だけで構成される指定長さの文字列作れるんですね. こりゃ便利だ! ほかにも組合せ, 順列, 階乗をサクサクっと計算できるようです. 参考リンクを貼っておきます. こちらも今後活用できるように, 頭の片隅に置いておきたい.

むすび

知らないことは伸びしろのはず. 精進あるのみ.

Pythonで競プロに挑む日誌 vol.24 ~アルゴリズムはじめました~