3/17 AtCoder（素因数分解） - 塩見周子の徒然日記

こんばんは。昨日のAGCのショックでしばらく立ち直れなかったとーです。

解くに至った問題

AGC:031A
ARC:097C
Tenka1 Programmer Contest:C
CADDi 2018:C
codeFlyer:B

AGC031A

解き方はすぐ思いついたのですが、まず10**9+7で割ったあまりを問われていることに気づかず3回WA、さらに、もし26文字すべてが文字列の中に使われていたとすると、それらを選ぶ/選ばないの組合せが2**26通りあるので、これではO(10**8)くらいになって間に合わない

という感じで本番中にACできませんでした（実質解き方を思いついてない）　

2**26通りの組み合わせはいいんですけど、これって結局「何を何個使うか」の組合せでしかない
例えば、「120の約数は何個ありますか？」という問いかけに対して、馬鹿正直に120==(2**3)*(3**1)*(5**1)だから、2だけで構成されるのが何個、2と3で構成されるのが何個......みたいに数え上げる必要はない
2が使えるのは0,1,2,3個だから4通り、3が使えるのは0,1の2通り、5が使えるのは0,1の2通りだから約数は4*2*2=16個、と数えるのが普通だし、明らかに速い
というわけで、今回もこちらを使うべきである　ただ、「一つも選ばない」という選択は出来ないので、その場合（1通り)を除くようにすれば、すぐに答えは求まる

bit全探索しか思いつかなかった　脳が凝り固まっている
制限時間内に解ける仕様になっているのだから、それを見つけるように努力する

天下一C

うまいことすれば3500**2のループで解けますって言われたから、普通に書いたらTLEした
通ったコードはこれ

N = int(input())
for n in range(1,3501):
  for w in range(n,3501):
    if (4*n*w-w*N-n*N) > 0:
      h = n*w*N/(4*n*w-w*N-n*N)
      if h == int(h) and h > 0:
        print(int(h),n,w)
        exit()

4行目で != 0としていたらダメだった　分母が負の値の時も律儀に計算することになるためである
だから>0とする必要がある

CADDi2018C

nを素因数分解するコード

def prime_factor(n):
    ass = []
    for i in range(2,int(n**0.5)+1):
        while n % i==0:
            ass.append(i)
            n = n//i
    if n != 1:
        ass.append(n)
    return ass

計算量はO(n**0.5)