Atcoder-ABC215をpythonで解いてみた
目的
- Atcoderで上を目指すべく頑張っている中でABC215を解いたので、解説してみる
- pypy7.3を使って解いている
A問題
考察
- 問題文通りに解けば良い
実装
S = input() if S == "Hello,World!": print("AC") else: print("WA")
結果
B問題
考察
- logを使って解いたが、数値誤差により
WA
を出した - 本番時は、厳密に原因まで分からなかったが、for文で回す方法にshiftし、無事解けた(2**60程度まで計算すれば良いことはlog使ってた際にわかっていたので)
pow(2,60) とかにどの程度時間がかかるか不明だったが、ローカルで実行して高速だったのでいけると判断した
なるべく小数を使わないようにするという基本を学び直した
- 使う場合は、計算時の誤差に注意すること
- 不安な時は
Decimal
を使って計算すること
実装
N = int(input()) ans = 0 for i in range(0, 60): if pow(2, i) <= N: ans = i else: break print(ans)
結果
C問題
考察
並べ替えで作成可能な文字列作成に関して
- Sの長さが、最大8なので、順列(permutation)や組み合わせ(combination)が使えると思った
- そのため、itertools.permutations を利用した
- 同じ文字列がSに含まれる場合、重複するのでsetで重複した文字列を取り除いた
- 8!=40320 なので、そこそこ思い処理してもTLEにはならないと思って雑に解いた部分もある
sortに関して
- pythonのsortが文字列をアルファベット順にsortしてくれるので、それを利用した
- 通常のsortは O(nlogn) であるが、事前に各文字列のscoreを求めるので通常の数値比較より重い処理になるはず
- 文字列をasciiコードに変換し、上位の桁になるほど重くなる(ex. n桁の場合、10n-1 で評価する)とかでスコアを決めてるのではないかと思っている
- これも、高々 40320 個の文字列しかないはずなので、なんとかなると思って利用した
- 通常のsortは O(nlogn) であるが、事前に各文字列のscoreを求めるので通常の数値比較より重い処理になるはず
$ python Python 3.6.9 (1608da62bfc7, Dec 23 2019, 10:50:17) [PyPy 7.3.0 with GCC 4.2.1 Compatible Apple LLVM 10.0.0 (clang-1000.11.45.5)] on darwin Type "help", "copyright", "credits" or "license" for more information. >>>> test = ["zz","aaa", "aab", "cacs","baas" ] >>>> test.sort() >>>> print(test) ['aaa', 'aab', 'baas', 'cacs', 'zz']
実装
from itertools import permutations S, K = input().split() K = int(K) ans = set() for p in permutations(S): s = "".join(p) ans.add(s) ans = list(ans) ans.sort() print(ans[K-1])
結果
D問題
中々筋のいい方針が立たずに、時間ばかり経って解けなかった
考察
試験中考えてたこと
N,M=105 なので、O(NlogN), O(N√N) 以内で解く必要がありそうだと考えた
- 愚直にやるとO(NM)なので、間に合わない
何となく素数を列挙して足りないものを足せば良さそうだと思った
- ここで見たような気がするなーと思い、コピペして利用した
解説を見た後
- ちょっと考えたが、事前にM以下の数字の数列を用意し、不要なものを消すと言うのは、なんだか計算量多くなりそうでやめたが、そっちで行けばよかった
- 素因数分解するとできそうだと思ったけど、出した素因数をどう使っていくのか(解説だと倍数を消していく)と言う部分の発想がなかった
- pythonでの素因数分解
- 素数判定の応用だと理解し、自分で書いた
- 今回は、素因数のみがわかればいいので、そこだけ計算するようにした
- sqrtを使っても書けるが、前述の誤差もあって整数を使って処理するように書いた
- 割った数のみで、割られた数を含めるのを漏らしていて、WAを何度かした
- 結構ここに気づくのに時間かかった、debug力の低さに反省...orz
- 素数判定の応用だと理解し、自分で書いた
- setの利用
- pythonのlistだと、特定の数値を含んでいるのか、その数値をlistから削除するのもO(n)なので利用できないと思った
- 2分探索で、数値を含んでるかどうかはある程度高速で判定できるが、削除はどうしようもないと思った
- dictかsetで考えたが、今回は数値のみ扱えればいいのでsetを使った(理由は下記の通り)
- 要素探索がaverageでO(1)
- 要素削除がaverageでO(1)
- pythonのlistだと、特定の数値を含んでいるのか、その数値をlistから削除するのもO(n)なので利用できないと思った
- エラトステネスの篩の理解
- 下記で、ざっくり理解した
- 今回は、素因数分解で求めた、素因数の定数倍のものを、M以下の整数列から削除していけば良い
実装
N, M = map(int, input().split()) A = tuple(map(int, input().split())) s = set(range(1, M+1)) p = set() for i in range(N): a, j = A[i], 2 while pow(j, 2) <= a: if a % j == 0: p.add(j) p.add(a//j) j += 1 if a != 1: p.add(a) for prime in p: i = 1 while prime * i <= M: if prime * i in s: s.discard(prime * i) i += 1 print(len(s)) print(*s, sep="\n")