EAFP

~ Easier to Ask for Forgiveness than Permission ~

Atcoder-ABC215をpythonで解いてみた

目的

  • Atcoderで上を目指すべく頑張っている中でABC215を解いたので、解説してみる
    • pypy7.3を使って解いている

A問題

atcoder.jp

考察

  • 問題文通りに解けば良い

実装

S = input()

if S == "Hello,World!":
    print("AC")
else:
    print("WA")

結果

B問題

atcoder.jp

考察

  • logを使って解いたが、数値誤差により WA を出した
  • 本番時は、厳密に原因まで分からなかったが、for文で回す方法にshiftし、無事解けた(2**60程度まで計算すれば良いことはlog使ってた際にわかっていたので)
  • pow(2,60) とかにどの程度時間がかかるか不明だったが、ローカルで実行して高速だったのでいけると判断した

  • なるべく小数を使わないようにするという基本を学び直した

atcoder.jp

実装

N = int(input())

ans = 0

for i in range(0, 60):
    if pow(2, i) <= N:
        ans = i
    else:
        break

print(ans)

結果

C問題

atcoder.jp

考察

並べ替えで作成可能な文字列作成に関して

  • 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 個の文字列しかないはずなので、なんとかなると思って利用した
$ 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問題

中々筋のいい方針が立たずに、時間ばかり経って解けなかった

atcoder.jp

考察

試験中考えてたこと

  • N,M=105 なので、O(NlogN), O(N√N) 以内で解く必要がありそうだと考えた

    • 愚直にやるとO(NM)なので、間に合わない
  • 何となく素数を列挙して足りないものを足せば良さそうだと思った

    • ここで見たような気がするなーと思い、コピペして利用した

ja.wikipedia.org

  • ただ、素数列挙するだけではダメで、素数でないけど、数列Aとは互いに素になるものも、あるはずで、それをどうしたら見つかるか?が分からず終わった

f:id:kazu_0716:20210822022504p:plain
ABC215D メモ

解説を見た後

  • ちょっと考えたが、事前にM以下の数字の数列を用意し、不要なものを消すと言うのは、なんだか計算量多くなりそうでやめたが、そっちで行けばよかった
    • 素因数分解するとできそうだと思ったけど、出した素因数をどう使っていくのか(解説だと倍数を消していく)と言う部分の発想がなかった

atcoder.jp

qiita.com

  • setの利用
    • pythonのlistだと、特定の数値を含んでいるのか、その数値をlistから削除するのもO(n)なので利用できないと思った
      • 2分探索で、数値を含んでるかどうかはある程度高速で判定できるが、削除はどうしようもないと思った
    • dictかsetで考えたが、今回は数値のみ扱えればいいのでsetを使った(理由は下記の通り)
      • 要素探索がaverageでO(1)
      • 要素削除がaverageでO(1)

wiki.python.org

  • エラトステネスの篩の理解
    • 下記で、ざっくり理解した
    • 今回は、素因数分解で求めた、素因数の定数倍のものを、M以下の整数列から削除していけば良い

manabitimes.jp

実装

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")

結果

まとめ

  • 今回もD問題解けなかった(diff的には茶色だが)

    • 整数問題系の演習量が足りてないと思う部分もあるので、今回を気に増やしていく
    • 高速な素因数分解や、素数列挙の方法等を学んだので、より理解を深めていきたい
  • setをあまり使ってこなかったが、今回計算量なども学べて、構造の理解も深まりよかった

  • 引き続き、D問題の過去問を進め、D問題がコンテスト中に解けるように、頑張っていきたい