PAST4K
from 第四回 アルゴリズム実技検定
PAST4K
考えたこと
結合した時にどうなるか考察
結合した列の転倒数はそれぞれの転倒数と頻度表から求められる ACLPC L
結合する前に単独で計算する時のnが最大で10^5だ
どうするのか
フェニック木らしい
サンプルは通ったがWA
TLEもしてる
1ずらしてWAが消えるかテスト
だめ
あまりが10^9だった！
WA消えたが3TLE
インライン展開した、これでだめならダメ
ダメだった
これ以上に何ができるのか
そもそも3×10^5なのに、なぜ5秒もあるのがタイムアウトするのか
30万だとダメだが10万ずつだとOKなのか？
それでも3TLE
Cythonにしてみたけどダメ
C++で書くべきか？
公式解説
方針は良い
同じ列が繰り返し使われる時に毎回フェニック木で転倒数を求めていたのがよくない
転倒数と頻度表を前処理すべきだった
列の長さの和が小さく抑えられているのは、前処理でフェニック木を使うのはTLEしないが、クエリのたびに使うとクエリが長い列ばかり選ぶ場合があってNGという意図
AC
pythondef solve(K, seqs, Q, BS):
MOD = 10 ** 9
N = 20
invs = []
freqs = []
for i in range(K):
init(N)
freq = [0] * 21
inv = 0
for a in seqs[i]:
bit_add(a, 1)
inv += bit_sum(N) - bit_sum(a)
freq[a] += 1
invs.append(inv)
freqs.append(freq)
ret = 0
freq = [0] * 21
for b in BS:
ret += invs[b - 1]
f = freqs[b - 1]
for i in range(1, 21):
for j in range(i + 1, 21):
ret += f[i] * freq[j]
for i in range(1, 21):
freq[i] += f[i]
ret %= MOD
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→
- →AtCoder Library×aclpc×aclpc_a×ACLPC B×aclpc_c×aclpc_d×aclpc_e×aclpc_f×aclpc_g×aclpc_h×aclpc_i×aclpc_j×aclpc_k×ACLPC L→
- →atcoder×AtCoder Library Practice Contest×numba×cython×フェニック木×セグメント木×遅延伝搬セグメント木×接尾辞配列×lcp_array×pythonでの累乗・逆数・階乗・階乗逆数・組み合わせ×中国剰余定理×floor_sum×np.convolve×two_snuke×長整数が速い×dsu×unionfind×最大流×最小費用流×scc×2-sat→
"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]