naoya_t@hatenablog

いわゆるチラシノウラであります

AtCoder Beginner Contest 110

9/23(日) 21:00-22:40
D-C-B-Aの順で
DはTLEが取れず3完

D - Factorization (400)

素因数分解
いや約数×約数の遷移でDPかな
答えは合うけど…N=100000だとどう考えても無理

行列の累乗でどうだろう(d=約数の個数って100とか200とかだと思うしO(d^3 logN)ならギリ間に合うのでは)
→TLE
https://beta.atcoder.jp/contests/abc110/submissions/3254895
先にC,B,Aを回ってから、行列乗算のループ順をi,j,kからi,k,jに変えるとかして頑張ったけど及ばず。

解説読んで

素因数分解して、素数ごとに割り振るパターンを (n-1+k)Ck で出して積をとるだけ
→AC
https://beta.atcoder.jp/contests/abc110/submissions/3259523

1e9までの範囲だと、約数が1000個以上になる数もある。O(d^3 logN)無理。

C - String Transformation (300)

ある文字を2種類以上の文字に変え分けることはできない
2つ(以上)の異なる文字を1つに合わせるには?…どんなに頑張っても最後にもう一方もフリップしちゃうから無理
1対多、多対1の組み合わせがあればNo、なければYesで
→AC
https://beta.atcoder.jp/contests/abc110/submissions/3256204

B - 1 Dimensional World's Tale (200)

xの最大とyの最小を調べておいて
Zを総当たりで
→AC
https://beta.atcoder.jp/contests/abc110/submissions/3256638

A - Maximize the Formula (100)

ソートして[x,y,z]の大きい方からzy+x
→AC
https://beta.atcoder.jp/contests/abc110/submissions/3256804