あけましておめでとうございます。去年 12 月初めから更新が止まっていた日記を再開します。
過去に「12/15 くらいから再開する予定」と書いたのは見なかったことに。

1/4

競プロ

ARC137 - E. Bakery (800) に突撃。LP で書いてみたり双対を取ってみたりしたが、うまくいかず断念して解説を開いた。フロー以外で解けないだろうとは思ったが、どうしても「流量が 0 または R-L」みたいな変な形になってしまっていた。imos 法に思いを馳せるべきだったのか…
MCF への理解が浅いため、どんな設定なら解きやすくて、逆にどんな設定なら解けないのかといったことが判断できず、考察中によからぬ方向へ行って沼ってしまったときに抜け出せない。経験値ゲーなのか？

とりあえず、

よくある「sink, source, 中間ノード」という形だけで表せると思い込んではいけない
辺のコストが区分線形凸関数でなくなってしまったら、別の条件設定を考えてみた方がよい
「s-t パスに流す」ではなく、最小費用循環流なども含めた b-flow の形を考えてみるべき

といったところだろうか。

＜解法＞

以下の最小費用循環流の答えを -1 倍したものが元の問題の答え。

頂点 $0, \dots, N$
$i \rightarrow i-1$ に容量 $A_i$ 、コスト $-D$ の辺
$i \rightarrow i-1$ に容量 $M-A_i$ 、コスト $0$ の辺
$L_j - 1 \rightarrow R_j$ に容量 $1$ 、コスト $C_j$ の辺

$i \rightarrow i-1$ の辺にめいいっぱい流しておいてから調整すると考えると負辺が消える。

数オリ

もうすぐ予選なので、2015 年の予選の過去問を解いた。若干記憶に残っていたのもあり、一時間ちょっとで 9 問目まで解けた。明日 10 問目を考えてみよう

その他

チェンソーマン二部、ナユタちゃん（おそらく）が秀才なの解釈一致で助かる

1/5

競プロ

数理最適化のお勉強

今までいい加減だった LP への理解を深めたくなった。梅谷俊治教授の「しっかり学ぶ数理最適化」を読んでいく。理解が甘かったところを以下にまとめる。

そもそも LP (線形計画問題）とは、線形な目的関数の値を最大化・最小化する問題であって、制約条件が全て線形の等式（不等式）で与えられるものを指す。LP は全て以下の標準形に書き換えられる。

maximize $\boldsymbol{c}^\top \boldsymbol{x}$
subject to
- $A \boldsymbol{x} \leq \boldsymbol{b}$
- $\boldsymbol{x} \geq 0$

最小化問題、非負制約がない変数、不等号の向きが逆、不等号じゃなくて等号…などの場合も全て上の形に帰着できる。ついでに $|\boldsymbol{a}^\top \boldsymbol{x}| \leq b$ みたいな条件も OK。ただしこれは不等号の向きが逆だと OR の条件になってしまうので無理。

subject to 以下の条件を満たす点 (ベクトル) の集合は凸多面体になる。凸多面体とは、集合 $S \subset \mathbb{R}^d$ であって、任意の $\boldsymbol{x}, \boldsymbol{y} \in S, 0 \leq t \leq 1$ に対して $(1 - t)\boldsymbol{x} + t\boldsymbol{y} \in S$ となるものである。

x, b がそれぞれ n, m 次元のとき、合計 n+m 個の条件 (平面) が存在するが、最適な値を与える点の少なくとも一つはこれらの平面のうち n 個が交わる点である。平面を通るというのは不等号に対して等号を成り立たせることと同じである。スラック変数を導入すると n+m 変数、n+m 個の非負条件、m 個の等号条件に置き換わる。n 個の平面が交わる点というのは、n 個の変数を 0 にすることと同じである。残りの m 個の変数 (0 でないとは限らない) を基底変数と呼ぶ。

単体法では目的関数の値が増加するように、0 にする変数を 1 つずつ入れ替えることを繰り返している。0 である基底変数が存在する解を退化している (degenerate) と呼ぶ (フローで聞いたことがあるような) 。

実行可能解が自明でない場合も、制約の違反量を人工変数として導入し、この違反量を最小化する (つまり、0 にする) というステップを踏んで解を見つけることができる。

主問題、双対問題は (解なし, 解なし), (非有界, 解なし), (解なし, 非有界), (有界, 有界) のいずれかである。最後の場合、最適値は一致し (強双対定理)、これは単体法を経由して証明することができる。

$\boldsymbol{x}^\top (A^\top\boldsymbol{y} - \boldsymbol{c}) = 0 \land \boldsymbol{y}^\top (\boldsymbol{b} - A \boldsymbol{x}) = 0$ を相補性条件 (complementary slackness condition) という。

ARC151 - E. Keep Being Substring (700)

本質ケースがサンプルにない。X のどの要素も Y に含まれないとき、どうせ X の要素は消すことになるので、一つだけ残して全て消してしまった方が自由度が上がってよい。結局 X と Y から一つずつ要素 a, b を選んで a を b に一致させるための最小の操作回数を求めればよい。

数オリ

'15 予選 10 番、解説を見てしまった…これもうちょっと考えたら解けたな
N_1 = 10x + y と N_2 = x + 4y を足し引きして mod M での関係を導く

その他

はてなブログの数式めちゃくちゃ書きにくいな…そもそもこれが最初に Zenn を使うことにした理由だった

1/6

競プロ

JOI2022sc - Ants and Sugar

本番最高点が 6 点だっただけあって難しい

この問題に限らず、最大二部マッチングは (max-flow min-cut 定理より) 片側の頂点集合を L として、 $S \subset L$ に対する $|L| - |S| + |\mathrm{out}(S)|$ の最小値である。これは今までも暗黙のうちに使ったことがあるはずだが、改めて一般化しておくと今後も使えそう。

区間種類数クエリも似たような考え方を使うが、「区間に一個以上」といった形の条件を各々の要素の寄与と隣接する 2 つの要素の寄与に分解することでセグ木に乗せられる。非常に賢い

1/7

競プロ

CF Round 841 (Div. 2) バチャ

14 分残しで全完できたが、これは 1 時間で全完するべきセットだった。

A: a+b <= ab+1 なので一つを残して全て 1 にする
B: 対角線上を通っていく。帰納法で証明できる (i + j = 2n となるマス (i, j) では (n, n) までジグザグで行ったときが最大)
C: 平方数を列挙 & 累積 XOR で数える
D: 二分探索 + 二次元累積和
E: k が大きいものから貪欲に使ってよい
F: 多項式補間

部分和問題 O(NW)

全ての重みが W 以下の部分和問題の O(NW) アルゴリズムを履修した。参考

順番に重みを加えていって、初めて目標の値 S を超えた位置を b とする。もし和を S にできるなら、この状態から b 以降の要素をいくつか追加し、b 以前の要素をいくつか削除することで実現できる。さらに、この追加・削除は重みの和と S の差が W 未満である状態を保ったまま行うことができる。

dp[i][j][k] を、「b,b+1, ..., i について追加するかどうか決め、b-1, b-2, ..., i+1, i について削除するかどうか決めたとき、和を k にできるか」と定義する。このままだと O(N² W) だが、dp'[i][k] を「dp[i][j][k] = True となる j の最大値」と定義することで O(NW) に落とすことができる。

数オリ

'16 予選を解いた。10 番面白かった

1/8

競プロ

CGR 24 バチャ

悪くなさそう？G1 解きたかったな

A: ギャグ、(1, n) を出力
B: g = gcd(a_1, ..., a_n) とすると、最大値以下の g の倍数が全て作れる
C: 二部グラフになるので、値でソートして split する位置を決め打つ。ただし全ての値が同じ場合は floor(n/2) が答えになることに注意
D: 対称なので、最後に a に追加されるのは 1 であるとしてよい。1 を取り除いた直後に n/2+1 以上離れた 2 点が現れるので、この 2 点の距離と a に追加する個数を決め打つ
E: k <= a_1, k > a_1 + b_1 の場合は簡単。そうでない場合、k-b_1 <= x <= a_1 となる x が少なくとも一つすでに塗られていなければならない。ここで、k-b_1 が塗られているとしてよい。この考え方を繰り返し用いると、結局「k <= a_i + b_i となる i を選んで k から b_i を引くことを繰り返して、まだ選んでいない i に対して k <= a_i が成り立つようにする」という問題になる。k <= a_i を成り立たせる i を決め打つことにすると、j ≠ i となる j を a_j+b_j の昇順に並べ、現在 a_j+b_j 以下なら b_j 引くことを繰り返すことになる。この処理は、うまくやると遅延セグ木を用いて全ての i について同時に行うことができる。
F: 頂点 1 を含む部分木を徐々に確定させていくと考える。現在確定した頂点集合を S とする (最初 S = {1})。S に含まれない u であって、f(1, u) が最大になるものを取ると、u は S のどれかの頂点に接続している。そして、その頂点とは、S に含まれる v であって f(u, v) が最大になるものである。f(u, u), f(u, v), f(v, v) を用いると uv 間の辺の重みがわかる。
G1 (upsolve): 2 で割って切り捨てた値が等しいものどうしに辺を張ると、次数が 0 なのは 1 と、n が奇数のときは n の最大 2 個である。query(l, r, 2) を用いると区間に完全に含まれる辺の個数がわかる。query(0, m, 2) と query(m, N, 2) を用いると次数 0 のものが左右に何個ずつあるかがわかるので、1 が存在する区間を二分探索できる。左右に 1 個ずつある場合、どちらが 1 でどちらが n かを知るために、長さが 2 以上の区間に対して query(l, r, N) を投げればよい。二分探索の両端が [l, r) のときに、query(l, m) と query(m, r) ではなく query(0, m) と query(m, N) に注目するのはレアな気がする。

1/9

数オリ

JMO 予選。やばいミスがなければ通ったはず。9 番は似たようなのを見たことがあって、ARC なら 600 点くらいで出そう？

作問

去年「今年は ARC を開きたいな」というツイートをしていたらしい。この人原案作りすらしてないですよ
とりあえず設定を一問生やした。さあ何日続くだろうか

1/10

作問

二日目

アプリ開発

訳あって Flutter の勉強をすることになった。とりあえず環境構築をしたので、Dart の公式ドキュメントを読んでいく。
このためだけに Xcode インストールするの嫌なんだが (異様に容量がデカく、動作も遅いため)

1/13

二日飛んだのは気にしない

作問

三日目（？）

競プロ

ARC099 - F. Eating Symbols Hard (1200)

https://atcoder.jp/contests/arc099/tasks/arc099_d

A を多項式の係数だと思うことにし、ローリングハッシュの要領で一致判定を行う。

先頭 i 文字を処理した時のハッシュを H_i, P の値を P_i とおき、base を x とおく。
[i, j) を処理した結果が [0, N) を処理することは $\frac{H_j - H_i}{x^{P_i}} = H_N$ すなわち $H_j = H_N \times x^{P_i} + H_i$ と言い換えられるので、i を固定して j の個数を数えることができる。

一致判定だけでも愚直で $\Theta(N)$ かかるんだから、ましてそれの数え上げなんてハッシュ使わな到底無理やろ！という発想。
衝突確率を雑に見積もると mod 2⁶¹ でも危ない気がするが、大丈夫だった。

atcoder.jp

その他

久しぶりに Yunomi さんの曲を聴いていたら、いい曲に出会った

枕元にゴースト (feat. nicamoq) - YouTube

1/14

競プロ

Codeforces Round 842 (Div. 2) バチャ

E までは自明だったので省略

i→j を一気に行く場合と一つずつ行く場合を比較すると、a_i, ..., a_j の最小値を m として、m(j - i) >= n ならば一つずつ行ったほうがよい。
m = a_k となる i < k < j となる k が存在するなら i→j→k と行った方がよい。

B = sqrt(n) とおくと、m >= B となる場合は O(B) で調べ尽くせる。m < B となる場合を、a_i = m となるか a_j = m となるかでさらに場合分けする。

a_i = m のとき : monotonous stack で B 未満の要素を管理しておけば O(B) で調べられる。
a_j = m のとき : まず monotonous stack を更新する (a_k >= a_j となる k を取り出す) 。最後に取り出されたのが k であるとする。a_k = a_j なら、k とそれ以前の場所は調べる必要がないので k+1 から j の間を調べる。a_k > a_j なら、stack に残った末尾の要素を k' として、k'+1 から j の間を調べる。一見 Θ(N²) になってしまいそうだが、各 i が調べられるたびに、「i より右で i に最も近い B 未満の要素の値」が真に減少するので、それぞれ最大 O(B) 回調べられることになり、償却 O(NB) になっている。

ARC 153

4 完 & 久しぶりの赤 prf。C で凡ミスしたのと D で実装に手間取ったのは良くなかったが、考察スピードは戻ってきている気がする。

1/15

競プロ

Educational Codeforces Round 14 バチャ

E: ceil(a_i/k) <= ceil(b_i/k) が成り立つかを判定する。ある k が条件を満たすか調べるとき、ceil(b/k) の値を固定して (n とおく)、 b_i <= nk となる全ての i に対して a_i <= nk かどうかを調べればよい。各 k に対しありうるすべての n を試しても O(N log N) である。

F: 順列が一つの場合は、i→p_i に辺を張ったグラフを考えると、「ソートされる⇔全てのサイクルについて、そのサイクル内で一度も選ばれなかった頂点は高々 1 つ」が成り立つことがわかる。一度も選ばれない頂点の個数を最大化することを考えると、次のような最大二部マッチングに帰着できる : 左側に 1 つ目のグラフのサイクルに対応する頂点を並べ、右側に 2 つ目のグラフのサイクルに対応する頂点を並べる。各 u について、u が一つ目のグラフで属するサイクルと二つ目のグラフで属するサイクルに対応する 2 頂点を結ぶ。

作問

過去の ARC の問題を眺めながら設定をいくつか生やすとやりやすいことに気づいた。盗作みたいにはならないよう気をつけたい