2023-08-01

AGC063D後半

前半は自明です。後半は次の問題に帰着されます

ばかでかい正の整数Mがあります。でかすぎて値はわかりません。正の整数nを渡すとMをnで割ったあまりを返すオラクルが定数回使えます。
ax=b mod M を満たす最小の非負整数xをmで割ったあまりを求めてください。gcd(a,M)=1とします。

たぶんやってることは公式解説と同じです。こっちの方が俺には自然

以下、大文字は計算不可能な値を、小文字は計算可能な値を表すこととします。
まずオラクルを呼んでr:=M%aを求めます。Q:=floor(M/a)としてr=M-aQとなります。
a,rに対して拡張gcdをしてsa-tr=1となる非負整数s,tを求めます。r=M-aQを代入して、a(s+tQ)=1 mod Mを得ます。
a^-1 mod Mが求まったのでこれにbを掛けて、x=b(s+tQ) mod Mです。求める答えはb(s+tQ)をMで割ったあまりをmで割ったあまりです。
0<=u< aによりbt=av+uと書くと、btQ+bs=uQ+(bs-rv) mod M です。
uQ+(bs-rv)が答えなら嬉しいですね。確かめます。
uQ<=(a-1)Q<((a-1)/a)Mなので、a(bs-rv)<=M なら uQ+(bs-rv)< Mです。u>0なら同様にuQ+(bs-rv)>=0です。
u=0かつbs-rv<0のケースは簡単なので適当に処理することにすれば、uQ+(bs-rv)が答えといって良いことになります。
ということであとはQ=floor(M/a)をmで割ったあまりが分かればOKです。これはARCでやりました。
https://atcoder.jp/contests/arc111/tasks/arc111_a
おわりです。

こういうのはQとrを使ってガチャガチャやると解けがち

2023-06-13

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上は再帰にするともっと早くなる（オーダーはわからん）

293
p-smooth numberは少ない、素数は多い

294
ダブリング
遷移に対称性があるので行列累乗よりダブリングの方が真に計算量がよくなるパターン
母関数を考えてもO~で同じ計算量になる
Root of unity filterの練習問題にもなる

295
未

296
初等幾何を頑張るときれいな式になる
gcdでlogがつくかと思いきや、SB木で互いに素な組を列挙することでlogが消せる
上下に分けるいつものテクでO~(N^4/3)くらいになるっぽい

297
ゼッケンドルフ表現は貪欲
wikipediaの図を見ればやるべきことは明らか

298
DP
何を覚えているかを座圧

299
初等幾何を頑張るときれいな式になる
数式パートは257とだいたい同じ

300
全探索やるだけ
適当に状態を圧縮

続き
sugarknri.hatenablog.com

2023-02-21

競プロ小説

「競技プログラミングやろう！」
「なに？」
「競技プログラミング」
「プログラミングの勉強をしたいってこと？」
「それもあるけど、競技プログラミングはゲームだから」
「そうなんだ」
「そうだよ。……テンション低いな？」
「いや、何ヶ月か前にお前が似たようなことを言って俺にスプラ3を買わせた時のことを思い出しただけだよ。俺はでんせつになったけど、お前の最終ログインいつ？とか思ってないから安心してくれ」
「その節はどうも。今回はなんと初期投資0円で始められるから頼む」
「いいけどさ。それで、プログラミングするの？」
「そう。毎週土曜の21時にコンテストが開かれて、100分間の制限時間で解いた問題に応じてレーティングが増減する。目指せ、トップランカー！　……というゲーム」
「対人ゲームではないってことか」
「PvPではないね。全員に共通の問題が出されて、多く解いた人が上位」
「要するに学校でやってるテストで競う感じ？」
「そうそう。お前そういうの好きだろ、いつも上の方にいるじゃん」
「別に好きというわけでもないが……。それで、どんな問題が出るわけ？　兵庫県警を呼べるプログラムを作るとか？」
「兵庫県警？」
「いや、知らないならいい。話を進めてくれ」
「おーけー。出る問題は、簡単にいったら数学だな。具体的には……、っと、お前ってプログラミングできるんだっけ？」
「できるよ」
「マジ？」
「マジマジ。見てろよ」

>>> def plus(a, b): return a + b
>>> plus(1, 2)
3

「ほんとにできるんだ。知らなかった……」
「電卓の代わりに使ってるくらいだけどな。それで、話の続きは？」
「あーはいはい。いや、話が早くて助かるね。一番初心者向けの問題が『整数A,Bが与えられるのでA+Bを出力してください』なんだよね」
「いま作ったな。言語は何でもいいのか？」
「うん。ほんとは入出力もしないといけないんだけど、お前が実はすでにプログラミングをできることがわかったからその辺の話は省略する。知らなかったらあとでググってくれ」
「わかった。で、これを大量に解いたら勝ち？　タイピング大会じゃん」
「まあこれは一番簡単な問題だからね。もうちょっと難しい問題だとこういうのがある。『何個かの正整数が与えられます。ここから和が偶数になるように2つ選ぶとき、和の最大値は？』」
「偶数が作れないときは？」
「じゃあとりあえずそういうケースはないものとして解いてくれ」
「わかった。別にそんなに難しいとは思わないけどな」

def f(array):
  n = len(array)
  ans = 0
  for i in range(n):
    for j in range(i+1, n):
      if (array[i] + array[j]) % 2 == 0:
        ans = max(ans, array[i] + array[j])
  return ans

「うーん、この言語は知らないけど、雰囲気的に合ってそう。いやー、やっぱお前賢いから話がスムーズに進むな」
「もっと褒めてくれていいぞ」
「うんうん、想定した通りの誤解法を書いてくれてありがとう」
「は？」
「いやいや、これは俺が説明してない要素だからお前は悪くない」
「わざわざこのコードを書いた俺の労力を返せ」
「まあまあ。実は、提出するプログラムには実行時間に制限がある。大抵の問題は2秒だ」
「こんなシンプルな処理で2秒も掛かることなくない？」
「じゃあ試してみよう。実行時間ってどうやって測れるか知ってる？」
「知らないけど、2秒以上かどうか判定するだけなら見てれば十分だろ」
「たしかに。それじゃあ、適当に作った長さ1万の配列を渡してみて」
「全部1でもいいか？」
「いいよ」

>>> f([1] * 10000)
2

「5秒くらいかかってるな」
「そう。これをどうにか2秒以内におさめてください」
「うーん……。ソートして枝刈りすれば良さそう」
「なに？？」

def f(array):
  n = len(array)
  array.sort()
  array.reverse()
  ans = 0
  for i in range(n):
    for j in range(i+1, n):
      if array[i] + array[j] <= ans:
        break
      if (array[i] + array[j]) % 2 == 0:
        ans = max(ans, array[i] + array[j])
  return ans

>>> f([1]*10000)
2

「一瞬になったな。これで正解か？」
「えっ、どうなんだろう？」
「なんで出題者がわからないんだよ」
「用意してる答えと違うことされたから……」
「実際にはどうやって正誤判定してるんだ？」
「出題者が何十個か入力のバリエーションを先に用意しておいて、それに全部正解したら正解」
「じゃあ今からお前が作れ」
「えー」

問題：作中で提示されたコードが十分高速に動作するか判定せよ。

2022-11-19

包除原理

■いわゆる包除原理
$|\cup_{i\in S} A_i|=\sum_{\emptyset\neq T \subset S} (-1)^{|T|+1} |\cap_{i\in T}A_i|$
$|\cap_{i\in S} A_i|=\sum_{\emptyset\neq T \subset S} (-1)^{|T|+1} |\cup_{i\in T}A_i|$
N個の条件を全て満たすものの個数を求めてください→N個の条件いずれかに違反するものの個数を求めてください、と読み替えて包除しがち
2乗のDPになりがち

■min・max
$\max(S)=\sum_{\emptyset\neq T \subset S} (-1)^{|T|+1}\min(T)$
$\min(S)=\sum_{\emptyset\neq T \subset S} (-1)^{|T|+1}\max(T)$
期待値とかで使うらしい。ところでいわゆる包除原理とどういう関係にあるんですか？

■ゼータ変換・メビウス変換系（束上の累積和/imos・メビウスの反転公式）
累積和・imosは包除原理！（素振り）
・自然数の自然な大小関係に関する順序に対してやるやつ
・集合の包含関係に関する順序に対してやるやつ
・自然数の整除関係に関する順序に対してやるやつ
・分割の細分に関する順序に対してやるやつ

■逆行列を掛けるやつ
二項係数
$G(s) = \sum_{t=0}^s \binom{s}{t} F(t) \Longleftrightarrow F(s) = \sum_{t=0}^s (-1)^{s-t} \binom{s}{t} G(t)$
スターリング数
$G(s) = \sum_{t=0}^s {s \brace t} F(t) \Longleftrightarrow F(s) = \sum_{t=0}^s (-1)^{s-t} {s \brack t} G(t)$
$G(s) = \sum_{t=0}^s {s \brack t} F(t) \Longleftrightarrow F(s) = \sum_{t=0}^s (-1)^{s-t} {s \brace t} G(t)$
係数がs-tのみで決まるなら畳み込み逆元だがそうではないので……？
追記：
これって集合の包含関係に関する順序についての反転、分割の細分に関する順序についての反転らしい。
集合の包含関係に関する順序についての反転は
$G(S)=\sum_{T\subset S}F(T) \Longleftrightarrow F(S)=\sum_{T\subset S}(-1)^{|S|-|T|}G(T)$
で、もしここで $|S|=|T| \Longrightarrow F(S)=F(T)$ が成り立つなら、シグマの部分を $\sum_{t=0}^{|S|}\sum_{T\subset S, |T|=t}$ と分解するとさっきの式が出てくる。知らなかったそんなの……

■主客転倒
これ包除じゃなくない？　でもメビウス関数とかでてきたら実質包除だろ（ガバ判定）
・N以下のsquare-free numberの数え上げを $\sum_{d\leq \sqrt{N}}\lfloor\frac{N}{d^2}\rfloor\mu(d)$ でやるやつ
[x=1]を $(\zeta*\mu)(x)=\sum_{d|x}\mu(d)$ と読み替えるのが本質。（畳み込みはDirichlet convolution）
包除じゃなくない？
・累積和の変形
$\sum_{x\leq N}F(x)=\sum_{x \leq N}(\mu*F)(x)\lfloor\frac{N}{x}\rfloor$
（畳み込みはDirichlet convolution）
これは本当に主客転倒してるだけ。包除なんも関係ない

2022-10-17

ABC220Ex O(N^3)解法

これを読解した
Submission #27805654 - AtCoder Beginner Contest 220

参考にしたツイート

これやっと読解できた気がする
適切に行列作ると求めたいものは二次形式の値が偶数になるような01ベクトルの個数になる
問題の性質から作れる操作と直交変換かますことで3重対角行列になる
あとはDP https://t.co/TQmiButUHQ
— さんせん (@akakimidori) 2022年6月13日

なお以下の説明は、これらを自分なりに再解釈したものであり、#27805654の実際の実装は異なっているので混乱のなきよう

・ $A_{i,j}$ を、 $i< j$ かつ $i,j$ 間に辺があるとき1、それ以外0とする。 $X_i$ を頂点 $i$ にカメラを置かないとき1、それ以外0とする。
・監視されていない辺の個数は $Q_A(X):=\sum_{i,j}A_{i,j}X_iX_j={}^tXAX$ なので、 $Q_A(X)$ が偶数になるようなXの個数がわかれば十分。
・行列の成分を $\mathbb{F}_2$ とみなして、 $Q_A(X)=0$ を考えれば良い。
・正則行列PによってAを ${}^tPAP$ に置き換えても $Q_A(X)=0$ を満たすXの個数は変わらない。
・適切な正則行列Pを取ることで ${}^tPAP$ を二重対角行列にできる（←？）
・二重対角行列に変換したあとの行列を元の問題に戻すと、「パスグラフに自己辺がいくつかついたものの上で問題を解いてください」となり、自明にO(N)DPができる

「適切な正則行列Pを取ることで ${}^tPAP$ を二重対角行列にできる」というのは嘘です。
しかし、よく考えると、任意の $(i,j)$ で $A_{i,j}$ と $A_{j,i}$ をswapしても $Q_A(X)$ の値は変わらないので、「i行目を使ってi-1列目の成分を掃き出すとき、i行目に溜まった邪魔な成分はi列目に押しつける」とする掃き出し法で二重対角行列にできます。

おわり

追記
二重対角行列って言葉は存在しないらしいです。ここで二重対角行列と呼んだものは、帯行列の1,0のパターン、すなわち、三重対角行列かつ下三角(or上三角)なもののことを意図しています