メモ

yukicoderでゆるふわgolf

Project Euler 201-250 解説

これの続き
sugarknri.hatenablog.com

201
DP

202
前座パートは中受典型
No.306 さいたま2008 - yukicoder
本編前半は3種類の直線をZ[ω]座標系で書いて考える
本編後半は素因数分解してDPなり包除原理なり

203
やるだけ
クンマーの定理を思い出してもいい

204
O(N^(3/4))で素数を求めるDPの逆 O(√N)
普通にDFS/BFSで全探索してもいい O(ans)

205
さんすう
DPするまでもなく全探索が許される制約

206
自明な枝刈りだけで残りは10^7通りです
下から2桁ずつ決めるのが早い

207
センター数学とかでよくみる
電卓ありなら楽々手で解ける

208
前半パート:
向いている方向は5種類なので、移動量のベクトルは10種類。これらの登場回数が満たすべき条件は?
後半パート:
適当にDPすると解ける
実はO(N)解法もある。前半パートで求めた条件を1つ固定して、向いている方向を頂点、移動を辺としたグラフを考えると、オイラー路の数え上げになる
BEST theorem - Wikipedia
Kirchhoff's theorem - Wikipedia
BEST theoremの証明はこれを読ん……でません……
https://pure.tue.nl/ws/portalfiles/portal/3311129/597493.pdf
類題:
No.310 2文字しりとり - yukicoder
D - C4

209
問題文の条件を τ(x) and τ(f(x)) = 0と書いて、(x,f(x))の64頂点グラフを考える
類題? F - Cards

210
図を書く
適当にやってO(N)
格子点テクでO(N^(2/3))になる

211
やるだけO(NlogN)
素数ごとに計算しておいて平方数になる組合せを探すのでも解けるらしいが計算量はわからん

212
2次元の問題をO( (N+X)logX)で解く方法知ってる?
それを10^4回やれば O(X(N+X)logX)
wikipediaによるとO(N^1.5)の解法が存在しているらしい
Klee's measure problem - Wikipedia
dx,dy,dzが小さいことを使って、平面走査ならぬ空間走査でO(XΣdydz)でも間に合う
適当に空間を分割して、関係者が少なくなったら包除とかでも解けるらしい

213
期待値の線形性・独立な確率変数の積の期待値

214
O(NlogN)
φ^k(N)=1になる最小のkはθ(logN)

215
DP
縦に見ても横に見ても

216
131で見た
二次式の篩 O(NlogN)
ミラーラビンとかで雑に殴ってもいい

217
桁DP O(BN^2)

218
ギャグ
原始ピタゴラス数の生成式をぐっと睨む

219
N要素の最適な集合からN+1要素の最適な集合が構成できることを証明しましたか?
あとは適当にやるとできます O(logN)くらい

220
ドラゴン曲線 - Wikipedia
再帰構造がありそうな雰囲気があるのでぐっと睨む

221
適当に式変形すると約数を求める問題っぽくなるので、小さいところで適当に探索を打ち切ればAC
ところで、小さいところで適当に探索を打ち切っていいことの証明をできますか?(私はできません&掲示板にも誰も書いてなさそう)
ちなみに、ad-bc=1を満たす4整数abcdでparametrizeされるのでStern-Brocot treeを使ってO(NlogN)で解けます(は?)

222
2次元の問題になるのでbitDP O(2^N N^2)
ちなみに、2-optでswapした方が得になるケースを考えると最適な順序がただちにわかります(!)

223
式変形すると積=積の形になるので約数を求める
素因数分解するんじゃなく(xy)(zw)=(xz)(yw)とparametrizeするとxy-zw=2を満たす4整数xyzwが出てくるのでStern-Brocot treeを使っても解けるっぽい?(未確認)
ちなみに、ピタゴラス数の生成行列はa^2+b^2-c^2を保っているので、この問題もこれを使って解けます(!)
再掲:Pythagorean Triple -- from Wolfram MathWorld

224
223と同じ式変形をして、2次式の篩
生成行列を使う解法だと223と全く同様に解ける

225
愚直
計算量はよくわからない 自明な上界はO(ans^4)だが……

226
積分と無限和の順序を交換
普通に区分求積法でやっても精度足りるらしい

227
O(N)状態になので収束するまで適当にDP
Absorbing Markov Chainなので、手計算で解けるらしい
Absorbing Markov chain - Wikipedia

228
辺の傾きをぐっと睨む
適当にやるとO~(R(R-L))だが包除するとO(RlogR)になる

229
1つ目の条件だけなら当然解けますよね
二個の平方数の和 - Wikipedia
ほかも、対応する2次体の類数が1なので、平方剰余に関する自明な条件を満たせばOK
5が入ってなくて優しいね
二次体 Q(√-5) のイデアル類群と xx + 5yy 型の二次形式 - tsujimotterのノートブック

230
再帰構造があるので云々するやつ
類題:D - Christmas

231
素数ごとに個数数えるだけ O(NloglogN)
√Nより大きいところはprime sumなので、トータルでO(N^(3/4))になる

232
確率DP O(N^2logN)

233
229で見た
証明はZ[i]の素因数分解

234
区間(p^2,q^2)で包除

235
s(n)のclosed-formが手計算で出せるので二分探索

236
無意味な水増しを取り除くと、7変数に条件式が4本あるので、3変数全探索すると解ける
面倒なら4変数全探索しても間に合う

237
O(logN)
類題:No.541 3 x N グリッド上のサイクルの個数 - yukicoder

238
周期性
zを固定して探したくなるけど、kを固定した方が早い
なぜならwは乱数列なので、sum(w[:i])>=kとなるiを取ると[0,i)の十分近くに和がkになる区間がありそうなので

239
包除原理

240
挿入DP
D面ダイスN個の上位T個の和をSにする方法の個数を求めるのに O(NNDS)

241
「次に使う素数」を順番に決めるのは難しいが、分子の因数から適当に選んでDFSすると解ける
実はσ(n)/nにはかなり強いupper boundがあり、それを超えるような分子の素因数は全部約分される必要があることを使うとさらに早くなる

242
f(n,k)をn,kの式で書いて、Lucasの定理を使ったり二項係数の畳み込み和を計算したりして式変形する

243
69とほぼ同じだが、n/(n-1)がついているので……

244
最短経路問題

245
最後の1個の素因数をいい感じに決めるやつ
計算量はわからない

246
ひたすら数学をすると比較的簡単な式になる

247
プラキューでO(ans log ans)
最初にサイズを求めておいてそれより大きいものを列挙すればO(ans+hoge)

248
nの素因数の候補は少ないので全探索

249
DP
O(N^3/(logN)^2)くらい?
mod998ならlog,expでO(N^2)くらい

250
DP
周期性を使うと計算量が落ちる

続き
sugarknri.hatenablog.com