エイシング プログラミング コンテスト 2020
二乗の項があるのでx,y,zは100未満、全探索しても10^6だから十分余裕がある
それをN回やらないといけないことが問題
一旦細かいこと考えずに素朴にN回やるコードを書いてテスト通ることを確認
10^10
pythonif v == n:
ret += 1
elif v > n:
break計算結果がnに一致する時、retを増やして、小さい時には何もしてない
一番外のnについてのループは最も大きく1周して、その過程でもっと小さいnの場合の答えも数えたらnについてのループ不要だな、といって書き換える
n = N の所に元々は for n in range(N) があったpythondef solve(N):
from math import sqrt, floor
ret = [0] * (N + 1)
n = N
for x in range(1, floor(sqrt(n))):
v0 = x * x
for y in range(1, floor(sqrt(n))):
v1 = v0 + y * y + y * x
if v1 >= n:
break
for z in range(1, floor(sqrt(n))):
v = v1 + z * z + y * z + z * x
if v > n:
break
ret[v] += 1
return ret[1:]
おっ、コンテスト中提出のPyPyで最高速度のコードだ、何か実績解除とかないのかな？
20万桁の二進数が渡される
つまりそれを数値として扱うことは無謀
問題の関数を素朴に実装して1ステップかけた値を観察してみたら、結構小さな値ばかり
素朴に実装=数値を二進法文字列にして1の個数をカウントする
pythondef f(n):
p = bin(n).count("1")
return n % p:>>> [f(x) for x in range(1, 19)]
[0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 2, 0, 1, 2, 3, 0, 1, 0]popcountで剰余を取るのであっという間に小さくなるのだ
20万桁の二進数が渡されても、一回変換すれば最大20万になる。
16桁ぐらいなので、もう1ステップ計算したら上記のテーブルに到着する
つまり20万桁の二進数の1ステップ後の値を軽く求めればOK
この「軽く求める」に関して、問題条件を素朴に受けると20万桁の二進数の各桁ビット反転した20万個の値に対して剰余の計算が必要になって明らかにダメ
そこで20万個の値に対する剰余計算を、あらかじめ「2の累乗の剰余」を求めておくことで定数オーダーにする
まずはこの高速化をしないで素朴に書いてテストを通した
提出したらREになった
1つしかビットが立ってない入力の時に、そのビットが反転したら最初から0
それに気づかずに剰余を計算しようとするとpopcountもゼロなのでゼロ除算になる
素朴解法での剰余と高速解法での剰余が一致することをテストしてから置き換えた(半ばのコメントアウトしてるところ)
数値を二進法文字列にして1の個数をカウントするの遅そうに思うかもしれないけど全体では205msecで速い方から1ページに収まってました
実行時間の大きな割合を占めていないコードを高速化しても意味がないので手抜きしてます
pythondef solve(N, X):
o1 = ord("1")
def f(n):
p = bin(n).count("1")
return n % p
table = [0] * 20
for i in range(1, 20):
x = f(i)
if x == 0:
table[i] = 1
else:
table[i] = table[x] + 1
numOne = X.count(o1)
ret = [0] * N
v = 0
mod = numOne + 1
p2mod_p1 = [0] * N
p = 1
for j in range(N):
v *= 2
v %= mod
if (X[j] == o1):
v += 1
p2mod_p1[j] = p
p *= 2
p %= mod
xmod_p1 = v % mod # X mod (bc(X) + 1)
xmod_m1 = 0 # X mod (bc(X) - 1)
if numOne > 1:
p = 1
p2mod_m1 = [0] * N
v = 0
mod = numOne - 1
for j in range(N):
v *= 2
v %= mod
if (X[j] == o1):
v += 1
xmod_m1 = v % mod
p2mod_m1[j] = p
p *= 2
p %= mod
for i in range(N):
if X[i] == o1:
mod = numOne - 1
if mod == 0:
# already 0
ret[i] = 0
continue
v2 = (xmod_m1 - p2mod_m1[-1-i]) % mod
else:
mod = numOne + 1
v2 = (xmod_p1 + p2mod_p1[-1-i]) % mod
# v = 0
# for j in range(N):
# v *= 2
# v %= mod
# if (X[j] == o1) ^ (i == j):
# v += 1
# v %= mod
# debug(": v, v2", v, v2)
# assert v == v2
v = v2
if v == 0:
ret[i] = 1
continue
if v < 20:
ret[i] = table[v] + 1
continue
v = f(v)
ret[i] = table[v] + 2
return ret解けなかった問題の感想
Dが終わった時点で残り35分、普段のペースから考えて解けない可能性が高いだろうなと諦め気味(自分に負けてる)
ラクダが何番目までにいたいかのKの値でソートして順番に「先頭グループに入れるか、入れないか」の二択で、先頭グループのサイズを定義域にしてDP…
このDP、二乗のオーダーだからTLEなのでは…
とりあえず素朴にDPしてみる(残り15分)
テストケース1は通るが、残りは落ちる
このバグを直したとしてもTLEの問題が…
なぜフェイルするのか眺めてて、残り6分くらいで「後ろが好きなラクダもいる」とようやく気付いた
Kの小さい順に判断していくと「一番後ろの時だけとても喜ぶラクダ」の判断タイミングが遅れて最適解にならない
諦めてFを見る(残り3分)
これの方が簡単では？？
→簡単ではなかった
本当に簡単かどうか解いてないからわからないが、残り35分の段階で両方の問題を見るべきだったかもな
→2つの値の和が決まった場合、そこから先は式で求まる 積と和の交換
それをコンビネーションで掛け合わせるところがわからなかったが形式的べき級数っぽいなぁと思ったらまさにその方法でmaspyさんが解いていた
よかったこと
何度か「素朴に」って書いてるように、まず素朴に書いてから高速化するアプローチを取った
これは良いと思う
Related Pages
- →オイラー路×グリッド上の幅優先探索×ハンガリアン法×二部グラフの最大マッチング×二重辺連結成分分解×二重頂点連結成分分解×全点対間最短路×単一始点最短路×強連結成分分解×彩色数×最大クリーク×最大流×最大独立集合×最小全域有向木×最小全域木×最小流量制限付き最大流×最小費用流×橋/関節点×bit×binary-trie×convex-hull-trick-add-monotone×li-chao-tree×link-cut木_部分木クエリ×link-cut木×ウェーブレット行列×スパーステーブル×スライド区間の昇順k個の和×セグメント木×トライ木×マージ可能ヒープ×列の平方分割×平衡二分探索木×永続配列×素集合データ構造×unionfind×ローリングハッシュ×接尾辞配列×最長共通接頭辞×最長回文×回文×複数文字列検索×hl分解×全方位木dp×最小共通祖先×木の直径×木の重心分解×根付き木に変換×mod-pow×オイラーのφ関数×オイラーのφ関数テーブル×ベル数×ラグランジュ補間×二項係数×二項係数テーブル×任意mod畳み込み×分割数×分割数テーブル×商列挙×形式的冪級数×形式的べき級数×拡張ユークリッドの互除法×拡張ユークリッド互除法×第2種スターリング数×約数列挙×素因数分解×素数テーブル×素数判定×組合せ×行列演算×進数変換×階乗×離散対数問題×高速フーリエ変換×divide-and-conquer-optimization×monotone-minima×スライド最小値×一次元累積和×二次元累積和×個数制限付きナップサック×最大長方形×最適二分探索木×最長増加部分列×ダブリング×包除原理×燃やす埋める問題×燃やす埋める×牛ゲー×mo’s_algorithm×offline-dynamic-connectivity×座標圧縮×アルゴリズム→
- →ホッケースティック恒等式×二項係数の公式×vandermondeの恒等式×巨大なnについての二項係数×形式的べき級数×ARC110D_FPS×oeis×重複組合せの畳み込み×arc110d_nonfps×arc110→
"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]