これの続き
sugarknri.hatenablog.com
何を埋めてないかぐっと睨まれると垢バレする気がするけど気にしないぜ
301
Nimの必勝法を知っていますか？
302
上からDFS
303
BFSやるだけ
D - Small Multiple
桁数を2倍にしたときどうなるかのチェックを挟むと早くなるらしい
値の分布がランダムならexpectedでO(√N)になるのはわかるが、実際のところはよくわからず
304
前半：区間篩なりミラーラビン
後半：fib[n]はO(logn)で求まるが、fib[10^14],fib[10^14+1]さえ求めたらあとは愚直でもオーダーは同じ
305
切れ目がどこにあるか考える
306
grundy数を知っていますか
実験
307
余事象
308
https://en.wikipedia.org/wiki/FRACTRAN
brainf*ckの読解と頭の使い方は同じ。高級言語のアルゴリズムに変換して考える
309
直角三角形が見えますね
310
grundy数を知っていますか
不等号の制約があるのでいい感じに1/6にする必要がある
ABC288Hは似て非なる問題
311
未
312
算数
実験＋エスパーでも解けなくはない
313
前半は算数パズル
後半はpを全探索
実は答えは単純な形になってい つ も の でO(N^(2/3))
314
を求める問題なので、答えを二分探索
315
やるだけ
10^10^4以下の整数すべてとかでも1分で解けるはず（1手だけ真面目にやる）
316
マルコフ連鎖なので行列計算するとO( (logn)^3)でg(n)が求まる
KMP+DPでO(logn)
PGBattle2021かつおぶしD
317
放物線群の包絡線を求めてその回転体の体積を計算する問題
ゴリゴリの数学
318
古くはGCJ2008の時代から競プロ文脈でも無限回既出
線形漸化式の一般項の話をしていると思うこともできるし、2次方程式の解と係数の話をしていると思うこともできる
ただし今回の問題の場合、その前段階で十分条件が必要十分であることをいうのはかなり非自明で難しい。例えばこれを参照
https://sci-hub.se/https://doi.org/10.1007/s000130050442
319
3番目の条件でとりあえず変数分離テクして、maxを決めると実は全部決まる。
残りはい つ も のでO~(N^(2/3))
320
Legendreの定理を使いつつで二分探索すると求まる
二分探索ではなくp進で上の桁から決めていく感じにすると桁ごとにO(1)になるので素因子1つあたりO(log i)、iあたりO(ω(i)log i)になる
ω(i)=O(loglog i)だったはずなので、全体でO(NlogNloglogN)
321
直感的な操作をすると最短になるので、M(n)をnの式で書くのは難しくない
残りはPell方程式
322
一般には高速に解けないが、N,Mが特殊な性質を持つので解けるというタイプのやつ
10ではなく2ならLucasの定理で桁DPやるだけ。
実はmod 2^40でありえる値が十分少ないのでDPするまでもなく全探索できる
323
33状態のマルコフ連鎖だと思ってもいいし、期待値=∑(n回目の操作をする確率)だと思ってもいい。
有限和の形の閉な式もある。なにをやっても解ける
324
行列累乗
雑にやると512状態、parityを考慮すると126状態、回転・反転などを考慮すると23状態まで減らせる
325
実験をすると法則がわかる。証明は簡単
残りは実質floor sumみたいなものなので、うまく再帰すると求まる
軸を入れ替える方ではなく、SB木で分解するみたいなやつの方
計算量はO(logN)
326
実験すると法則がわかる。残りはZero-Sum Rangesやるだけ。O(M)
327
Cを固定してRが小さい方から考える。Cを固定するごとにM(C,R)はO(R)
328
未
329
DPやるだけ。分母が小さいので数え上げの問題だと思って解けば良い
マスの数をN、ジャンプ回数をTとしてO(NT)
330
一般には高速に解けないが、MODが特殊なので解けるというタイプのやつ
漸化式を作ってにらむ
331
まずはいくつか手で解いてみると解法がわかる
理詰めでやるなら、「1マスだけをflipさせることはできるか？」みたいなことを考えるとよい
残りのパートは一般にはO(N^2)。今回は黒い部分が特殊な形をしているので頑張ると線形時間になる
332
球面幾何学。やるだけ
対称性を考慮するとかなり早くなる
333
がvalid partitionのとき、(A_i,B_i)をソートして、A_iを狭義単調増加、B_iを狭義単調減少にできる。
なのでA_1は一意。B_1を全探索してメモ化再帰すればO(NlogN)で解ける。
実はB_1を全探索することなくvalid partitionを1つ求めることはできる。...(*)を満たすような最大のeとする。
とおき、N'に対して同様の手順で再帰的にvalid partitionを求める。ord_2(N')>ord_2(N)と(*)から、この再帰アルゴリズムで構築されるN'のvalid partitionは、(ord_2(N),e)を加えてもvalid partitionである。証明終わり
この貪欲アルゴリズムと最初に述べた全探索アルゴリズムを比較することで、Nのvalid partitionが一意であるための必要十分条件は、「eを貪欲にとらなかった場合にはN'にはvalid partitionが存在しない」かつ「eを貪欲にとった場合にはN'のvalid partitionが一意である」とわかる。
よって貪欲アルゴリズムの手順を逆に回す、すなわちvalid partitionが一意な奇数から、適当なa>0, b>B_1を用意して、2^aN+3^b< 3^{b+1}であって3の最大指数がb未満であるvalid partitionが存在しないものへ遷移することで、valid partitionが一意な奇数のみへ遷移していくことができる。
計算量はO(N^0.8)とかO(N^0.631)とか言われているがよくわからず。
さらに、今回は2を固定して3を貪欲したが、3を固定して2を貪欲することもでき、この2つのvalid partitionが一致することがuniqueであることの必要十分であるらしいので、polylog解けるらしいが、"It is fairly easy to check that ..." と書かれている部分の証明がわからないので正当性は理解できてない
334
GCJ2010で既出 https://www.acmicpc.net/problem/12560
終了条件を満たす状態に、1つ豆を加えた状態から操作を開始して、再び終了条件を満たす状態に至るまでに何が起こるかを観察することで、O(豆の個数)で解ける
実はO(皿の個数)でも解ける。終了条件を満たす状態がどのような形であるかを考え、豆の座標の和が不変量であることと、豆の座標の平方和が操作ごとに2増えることを合わせるとcloseな式が得られる
335
実験してエスパーで解ける
1周するごとの状態の変化を睨むと再帰構造を見つけることができるので、それを使えば証明もできる。
2^k+1に限らず、実は一般のNでもM(N)をO(logN)で求められる
336
DFS/BFSやるだけ
337
末尾がnである数列の個数を実家DP
O(NlogN)
338
未
339
小さいnで実験して最適な戦略を見つける
そうするといつもの吸収マルコフ連鎖になる。遷移が特殊なので諸々の計算が簡単に済んで全体でO(n^2)
もうちょっと計算するとO(n)にもできるらしい
340
a > c なのが肝
実験。証明は帰納法
341
再帰構造があるので、再帰する。
OEISによるとG(n)はO(n^(1/φ))らしいので、2回再帰すると必要な項数がO(n^(1/φ^2))となり、十分高速
342
最大素因子の指数が満たすべき条件を考えて適当に探索。241の簡単版
空間計算量はO(√N)、時間計算量は自明にO(N)だが実際のところはよくわからない
343
最初に約分が発生するとき、割る数が何であるか考えると、最後に何になるかがわかる。
あとは因数分解すると2次式の篩 O(NlogN)。あるいはフェルマーの小定理を使ってpごとにnを列挙するほうが簡単か
344
蟻本第2版P278
数式の問題に帰着したら下から桁DPをするとARC107DになるのでO(C^2 logN)
DPの遷移を多項式乗算だとみなせてO(C^2logN)になるらしい
345
ハンガリアン法
346
nはbase n-1で11になるので3桁以上のrepunitになるbaseが存在することが必要十分。O(N^(1/3))
Goormaghtigh予想の成立を認めるならもっと早くなる。
ABC293Fの方が難しい
347
普通に篩って辞書に突っ込むとO(NlogN)
でかいところをまとめて計算しようとすると素数和を求めるやつになるのでO(N^(3/4))でできる
348
回文を列挙して全探索すればO~(ans^(5/6))
349
実験
ラングトンのアリ - Wikipedia
350
LはGの倍数なのでL=L'GとしてLの代わりにL'を全探索すると、「lcmがL'でgcdが1の個数は？」になるので解ける
