Project Euler 251-300 解説

これの続き
sugarknri.hatenablog.com

何を埋めてないかぐっと睨まれると垢バレする気がするけど気にしないぜ

251
x^3+y^3=(x+y)^3-3xy(x+y)は受験数学典型
後半パートは特殊な形の数たちの素因数分解をosa_k法っぽくやるやつ
整数問題みたいにmodとかgcdとかで丁寧にreductionすると早くなるらしい

252
F - Integer Convex Hull

253
状態がヤバイDPをやるだけに見えるが、シンプルな3乗があるらしい。見えません……

254
2つの操作をやっているので2つに分けて全探索

255
実験するとだいたい同じ進行をするようなので、適当にまとめる

256
2×n,3×n,4×n,…で条件を満たす敷き方ができるようなnの構造を実験により探る

257
やりようはいくらでもある
3変数2次方程式の解の列挙だと思って143,195のoverviewのテクをするか、いい感じに因数分解して全探索+素因数分解するのが正解者掲示板ではメジャー

258
いつもの
2乗かけていいので簡単

259
区間DP

260
普通にDPしようとすると空間3乗時間4乗になるが累積ORさえあれば十分なので空間2乗時間3乗になるやつ
ABC224Eが類題

261
未
式を整理するとペル型方程式になるので頑張ると解けます（多分）

262
まずは図を描いてみる
コースの概形がわかればあとは幾何の問題

263
素数の条件から、nは2の倍数であり3の倍数でなく5の倍数であり……。
practicalの条件から、nは2の倍数で……と小さいmodで十分たくさん場合分けして高速化すると間に合います

264
nごとにx^2+y^2=nとなる(x,y)の組を生成して、ここから3点を選ぶと外心の条件は満たす
垂心の条件は？　答え：オイラー線

265
De Bruijn graphのオイラー閉路を求める問題です

266
部分和問題
半分全列挙

267
乗算で効くので順序に依存せず、「表が何回出ればいいか」という問題に
あとは高校数学

268
包除

269
桁DP
Pの根になりうる整数は……？

270
DP
正方形ではなく円だったらカタラン数になります（へー）
3乗で解けるが、制約が小さいので雑に4乗でやったほうが実装が楽という説もある

271
中国剰余定理

272
乗法群(Z/p^nZ)^*の構造を知っていますか？
あとは268と同じ

273
二個の平方数の和 - Wikipediaに式変形が書いてあるが、それよりもZ[i]での素因数分解だと理解した方が後々の役に立つだろう
雑にやると計算量はO(4^(素数の個数))、メモ化すると3ベキ

274
10と互いに素なpについて、xがpで割り切れるかどうかと10xがpで割り切れるかどうかは同じ

275
ポリオミノの賢い数え上げ方を知っていますか？　英語版wikipediaに書いてあります
Polyomino - Wikipedia

276
gcdの条件を無視したものは定数時間で求められます（面倒）
C - 擬二等辺三角形
あとは約数包除
いつものテクでO(N^(2/3))
約数包除原理 - メモ

277
3種類の操作のうち、操作後も整数であるのは、anのmod 3によって問題文中で与えられた1通り
an mod 3を気にせずに与えられた文字列に対応する操作をしたとき、全ての値が整数であるための必要十分条件は、最後の値が整数であること

278
フロベニウスの硬貨交換問題
wikipediaにもう少し一般的なケースについて答えが書いてある
Coin problem - Wikipedia
今回のケースについては合同式をこねると初等的に求まるらしい
答えを少し式変形するといつものでO(N^(3/4))とかO~(N^(2/3))とかになる
似たような問題として718がある

279
余弦定理を考えると「tan1°は有理数か？」みたいなやつになる
あとは143とかでやった
賢いことをするとO(N^(2/3))で、超賢いことをするとO(N^(3/5))で求められるらしい。何それ怖…

280
適当に状態を圧縮すると解ける。すごいライブラリを持っているなら圧縮しなくても解ける
圧縮後の状態はDAGなので普通に確率DPしたくなる。実はDPの遷移行列はO(2^N)種類しかないので、O(N^2)の行列をO(2^N)回解いて全部でO(2^N N^6)で前計算でき、これで遷移がO(N)になって全体でO(4^N N^0.5)

281
バーンサイドの補題

282
テトレーションはここ
https://judge.yosupo.jp/problem/tetration_mod

283
未
まだまともに考えてない

284
CRT
10進で4桁くらい計算してみるとわかるんじゃないですか
別解、Henselをやろうとすると(2x-1)で割る計算をする必要があるように思えるが、x^2-x=0なので、(4x^2-4x+1)=(2x-1)^2を掛けると割り算を消せて高速化できます。びっくり

285
積分をしてください
……という問題に見えるが、図を描きましょう

286
にぶたん＋DP
50次方程式を解くのでもいいらしい

287
ある種の単調性があるので、ある領域が1色かどうかのチェックをO(1)でできる
あとはやるだけ
for文回すだけの解法もあるらしい。なにそれ

288
ルジャンドルの定理

289
連結性DP
TDPC Qなど

290
桁DP
4次元でDPしたりしないように

291
こういうのはまずd=gcd(x,y)とおくのが定石。エスパーでも解けるが。
残りのパートは216で見た

292
DP
辺の候補を列挙するとだいたい「部分集合で、和が0になるものはいくつ？」になる
多分O(N^4.5)だと思う。
上の方は疎なことを使って、下はDP上は再帰にするともっと早くなる（オーダーはわからん）