エイシング プログラミング コンテスト 2020 - AtCoder
- 二乗の項があるのでx,y,zは100未満、全探索しても10^6だから十分余裕がある
- それをN回やらないといけないことが問題
- 一旦細かいこと考えずに素朴にN回やるコードを書いてテスト通ることを確認
- 10^10 python
if v == n:
ret += 1
elif v > n:
break
- 計算結果がnに一致する時、retを増やして、小さい時には何もしてない
- 一番外のnについてのループは最も大きく1周して、その過程でもっと小さいnの場合の答えも数えたらnについてのループ不要だな、といって書き換える
n = Nの所に元々はfor n in range(N)があった python
def 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:]
- 提出 #15159332 - エイシング プログラミング コンテスト 2020
- おっ、コンテスト中提出のPyPyで最高速度のコードだ、何か実績解除とかないのかな？
- 20万桁の二進数が渡される
- つまりそれを数値として扱うことは無謀
- 問題の関数を素朴に実装して1ステップかけた値を観察してみたら、結構小さな値ばかり
- 素朴に実装=数値を二進法文字列にして1の個数をカウントする python
def 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ページに収まってました
- 実行時間の大きな割合を占めていないコードを高速化しても意味がないので手抜きしてます python
def 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
提出 #15172307 - エイシング プログラミング コンテスト 2020
解けなかった問題の感想
- Dが終わった時点で残り35分、普段のペースから考えて解けない可能性が高いだろうなと諦め気味(自分に負けてる)
- ラクダが何番目までにいたいかのKの値でソートして順番に「先頭グループに入れるか、入れないか」の二択で、先頭グループのサイズを定義域にしてDP…
- このDP、二乗のオーダーだからTLEなのでは…
- とりあえず素朴にDPしてみる(残り15分)
- テストケース1は通るが、残りは落ちる
- このバグを直したとしてもTLEの問題が…
- なぜフェイルするのか眺めてて、残り6分くらいで「後ろが好きなラクダもいる」とようやく気付いた
- Kの小さい順に判断していくと「一番後ろの時だけとても喜ぶラクダ」の判断タイミングが遅れて最適解にならない
- 諦めてFを見る(残り3分)
- よかったこと
- 何度か「素朴に」って書いてるように、まず素朴に書いてから高速化するアプローチを取った
- これは良いと思う