sima(mu)*雑記

print(f"{雑多なこと}")

ABC110参加記

AtCoder Beginner Contest 110 - AtCoder コンテスト時間: 2018-09-23(日) 21:00 ~ 2018-09-23(日) 22:40
f:id:awaawa4423:20180924000410p:plain
バイトが9時に終わったのでうーん帰りの電車ABC参加チャレンジwithスマホするか!wってやった結果です
4完はできましたがDの途中までスマホコーディングしてたのでなかなかひどいことになってます(言い訳

A - Maximize the Formula (100)

流石に自明にA,B,Cの一番大きいやつを10の位に持ってくるのが最適なので

abc = sorted(list(map(int, input().split())))
print(abc[2]*10+abc[0]+abc[1])

B - 1 Dimensional World's Tale

なんか問題の設定が把握しきれなかったけど
Yと任意のyの最小値が,Xと任意のxの最大値より真に大きければよいので(多分

def inpl(): return list(map(int, input().split()))
N,M,X,Y = inpl()
X = max(max(inpl()),X)
Y = min(min(inpl()),Y)
if X < Y:
    print("No War")
else:
    print("War")

C - String Transformation

何をすればいいかはわかるけど言語化するのが難しい問題
適当に実験してみたりすると
aabbc -> aaccb -> eeccb -> eebbc
みたいな感じになって

  • 最初からi文字目とj文字目が一致してるならどう変化させても一致する
  • 最初からi文字目とj文字目が一致していないならどう変化させても一致しない

っぽいことがわかるので,いわゆる換字式暗号が成立しているような組み合わせかということを見ればよい.
参考:換字式暗号 - Wikipedia
これはSを前から見ていって

  • S[i]が今まで見たことないものならdds[S[i]] = T[i]という対応を記録する
  • 見たことあるのならdds[S[i]] == T[i]ならスルー,dds[S[i]] != T[i]なら'No'を出力してexit()

しかしこれはS->Tへの対応しか見てないのでT->Sの対応も見る必要がある
(例えばS='aab', T = 'bbb'とかだとS->Tだけ見るだけだと通る)

実装はdict型をいい感じに使うとやりやすいです

S = input()
T = input()
L=len(S)
dds = defaultdict(int)
ddt = defaultdict(int)
for i in range(L):
  s = S[i]
  t = T[i]
  if dds[s] == 0:
    dds[s] = t
  else:
    if dds[s] != t:
      print("No")
      sys.exit()
      
  if ddt[t] == 0:
    ddt[t] = s
  else:
    if ddt[t] != s:
      print("No")
      sys.exit()
      
print("Yes")

因みになんかテストケース弱かったらしく個数を数えるだけの嘘解法でも通った(?)とかなんとか

D - Factorization

Pythonだとなんか高速化でハマりました(2桁msで通してる人もいるのに…)
考察はそんな重くないけど色々貼り付けたので若干知識色が強い問題かも?

とりあえず素因数を振り分けるみたいなイメージなので素因数分解したい気持ちになる
んで数列が異なるというのはどこか一カ所でも違えばいいので それぞれの素因数について割り振る場合の数をそれぞれ掛け合わせればいいです

もう少し丁寧に書くと,例えばサンプル2の時(N=3,M=12)
12 = 22 * 3なのでそれぞれの素因数についてN=3個に振り分けると

  • 2 : {22,1,1}, {2,2,1}, {2,1,2}, {1,22,1}, {1,2,2}, {1,1,22}
  • 3 : {3,1,1}, {1,3,1}, {1,1,3}

ここで全体の場合の数はそれぞれの素因数の分け方のどれか一つでも変わってれば違う数列になる
(素因数なので例えばx=2a * 3bとなるようなa,bは一意に求まるので一カ所変えれば同じ数列は存在しえない)
またこの割り振り方は重複組み合わせというやつでコンビネーションで数えられる
参考:重複組合せの公式と例題(玉,整数解の個数) | 高校数学の美しい物語
なのでans=3 * 6=18となる

またコンビネーションは逆元を使って高速に求めるようにします
(あまりにも頻出なのでめぐるちゃんを貼っておきます)

実装

考察は1分かからず終わったけど実は実装でとてもハマった
最初に実装したのは以下のような感じ

  1. 篩をしてmath.sqrt(109)くらいまでの素数のリストを作る
  2. 1の素数のリストを使ってMを素因数分解
  3. 逆元を使ってO(1)でコンビネーションが求まるように前計算しておく
  4. あとはそれぞれの素因数について重複組み合わせを計算して掛け合わせていくだけ

しかしなんか無限にTLEが吐かれる
AtCoderのコードテストで試してみると篩と素因数分解がネックになってるっぽい
うーんわかんね!->『Python 素因数分解 [検索]』 で出てきたのをコピペ参考にさせていただくとなんか爆速になって通ります
参考にさせて頂いた記事
qiita.com

from collections import defaultdict
mod = 10**9+7

#素因数分解
def factors_nojit(n):
    gaps = [1,2,2,4,2,4,2,4,6,2,6]
    length, cycle = 11, 3
    f, fs, nxt = 2, [], 0
    while f * f <= n:
        while n % f == 0:
            fs.append(f)
            n0 = n
            n //= f
        f += gaps[nxt]
        nxt += 1
        if nxt == length:
            nxt = cycle
    if n > 1: fs.append(n)
    return fs

#Combination事前計算
MAX = 10**5 + 100
fac = [1]*(MAX+1)
for i in range(1,MAX+1):
    fac[i] = (fac[i-1]*i)%mod
rev_m = [1]*(MAX+1)
rev_m[MAX] = pow(fac[MAX],mod-2,mod)
for i in range(MAX,0,-1):
    rev_m[i-1] = (rev_m[i]*i)%mod

def Comb(n,k):#nCk
    return (fac[n]*rev_m[k]*rev_m[n-k])%mod

N,M = map(int, input().split())

fs =  factors_nojit(M)
fs.sort()

dd = defaultdict(int)
ed = []
for f in fs:
    if dd[f] == 0:
        ed.append(f)
    dd[f] += 1

ans =1
for e in ed:
  k = dd[e]
  ans *= Comb(k+N-1,k)
  ans %= mod

print(ans)

なんか爆速になったの図 f:id:awaawa4423:20180924000539p:plain

感想

unratedですが一応4完できて良かったです(8ペナから目を逸らしながら)
ちなみに競プロ始めてから対ABConlyの成績はこれで4勝1敗(三完)
Dは典型じゃんって思ってすんなり(?)解けたので少しは力ついてきたかなって思ったり
これは今回のABC関係ないのですが学生のうちにCodeFestival参加したいので予選B頑張りたいです(A爆死した人並感
のでTypicalDPContestをBまでに解きたい