現在の目標
- 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 メソッドを使えば, 指定の文字だけで構成される指定長さの文字列作れるんですね. こりゃ便利だ! ほかにも組合せ, 順列, 階乗をサクサクっと計算できるようです. 参考リンクを貼っておきます. こちらも今後活用できるように, 頭の片隅に置いておきたい.
- itertools の公式ドキュメント
- Pythonで競プロをやる時にそこそこ使う書き方（itertools編）
- すごいぞitertoolsくん
- itertoolsによる順列、組み合わせ、直積のお勉強
むすび
知らないことは伸びしろのはず. 精進あるのみ.