AGC047A
AC
浮動小数点数を使うのは避けて10^9倍して整数にした
問題条件は「整数を掛けて10^18の倍数になるか」になる
それぞれの数を2で何回割れるか(P2)、5で何回割れるか(P5)、を計算しておく
P2[i] + P2[j] > 17 and P5[i] + P5[j] > 17 なら「掛けて10^18の倍数になる」pythondef solve1(N, AS):
ret = 0
P2 = []
P5 = []
for i in range(N):
p2 = 0
p5 = 0
x = AS[i]
while x % 2 == 0:
p2 += 1
x //= 2
while x % 5 == 0:
p5 += 1
x //= 5
P2.append(p2)
P5.append(p5)
for i in range(N):
for j in range(i + 1, N):
if P2[i] + P2[j] > 17 and P5[i] + P5[j] > 17:
ret += 1
return retこれで小さいデータに対してはACするが、大きいとTLEになる
数が最大20万個あるので、一個ずつ比べる方法では百億オーダーだからTLEになる
Nの二重ループがあるのがいけない
前処理をすることでこれを一重ループで済ませる
つまり
P2[i], P5[i] が与えられた時に「 P2[i] + P2[j] > 17 and P5[i] + P5[j] > 17 を満たすjの数」がループを回さずにわかれば良い→頻度表を作る
解説によればそれだけでもACになりそう
頻度分布表の幅は高々19
18乗以上は区別する必要がないから
計算回数は20万×400程度なので十分狭い
だけど僕は気づかないでさらに工夫した
Numpyだと二次元配列の累積和も簡単
pythonfor i in range(19, 0, -1):
P[i - 1] += P[i]
for i in range(19, 0, -1):
P[:, i - 1] += P[:, i]これで一重ループで求められるようになる
pythonfor i in range(N):
ret += P[18 - P2[i], 18 - P5[i]]だが、これだと正しい答えにならないので修正が必要
まず、P2もP5も9以上の数については「自分自身」をペアにカウントしてしまっているのでそれを引く
残りに関してはijペアとjiペアを両方カウントしているので2で割る
これで正解になる
pythondef solve(N, AS):
import numpy as np
ret = 0
P2 = []
P5 = []
P = np.zeros((20, 20), dtype=np.int)
for i in range(N):
p2 = 0
p5 = 0
x = AS[i]
while x % 2 == 0:
p2 += 1
x //= 2
while x % 5 == 0:
p5 += 1
x //= 5
if p2 > 18:
p2 = 18
P2.append(p2)
P5.append(p5)
P[p2, p5] += 1
for i in range(19, 0, -1):
P[i - 1] += P[i]
for i in range(19, 0, -1):
P[:, i - 1] += P[:, i]
for i in range(N):
ret += P[18 - P2[i], 18 - P5[i]]
ret -= P[9, 9]
ret //= 2
return retRelated Pages
- →数え上げ×degwer×状態をまとめる×dpは全探索の高速化×arc059f×codefestival_2016_final_f×aoj2439×探索順の変更×大きい順に並べる×aoj2333×順列は挿入dp×bit_dp×区間は終点でソート×条件の言い換え×操作は多いが産物は少ない×agc013d×線形和への分解×演算順序の変更×ビット演算を桁ごとに分解×部分群×操作が可逆で全域→部分群×ラグランジュの定理×再帰的定義→dp×arc037d×桁dp×aoj0570×累積和×フェニック木×高速フーリエ変換×ntt×高速ゼータ変換×and_と_add_の畳み込み×二分累乗×agc013e×行列木定理×全域木の個数×lgv公式×非交叉経路の個数×小さい確率を無視する×二項係数の公式×経路数×45度回転×xとyにわける×カタラン数×包除原理×agc005d×約数系包除×arc064f→
"Engineer's way of creating knowledge" the English version of my book is now available on [Engineer's way of creating knowledge]
(C)NISHIO Hirokazu / Converted from [Scrapbox] at [Edit]