準急が飛んだ(物理) + 1ヵ月ぐらい全くコードを書いてないことに気づいたので参加

無事Mが炎上。反省したらシンプルに書けたので投稿。そもそもADD DIV モノイド に帰着できますよね、というのは置いておいて…

オーバーフローに目をつぶればそのままsegtreeに乗る

struct S {
    Int len;
    Int v;
};

Int pow2(Int n) { return Int(1) << n; }

S op(S l, S r) {
    Int len = l.len + r.len;
    Int v = l.v + r.v * pow2(l.len);

    return {len, v};
}

オーバーフローを回避するためには、ある程度区間が長くなったら短い区間に帰着、という操作を入れればよい。

using Int = __int128;

struct S {
    Int len;
    Int v;
};

Int pow2(Int n) { return Int(1) << n; }

S op(S l, S r) {
    Int len = l.len + r.len;
    Int v = l.v + r.v * pow2(l.len);

    if (len > 40) {
        // 長さ40の区間に帰着する
        // v = div * 2^len + rem (0 <= rem < 2^len)として、
        // v'= div * 2^40  + rem'に変換する。
        Int div = floor_div(v, pow2(len));
        Int rem = v - div * pow2(len);

        if (rem < pow2(35)) {
            // remが小さい => そのまま
        } else if (rem > pow2(len) - pow2(35)) {
            // remが大きい => 繰り上がりとの距離を保持
            rem = rem - pow2(len) + pow2(40);
        } else {
            // その他 => 適当に真ん中に設定
            rem = pow2(39);
        }

        len = 40;
        v = rem + div * pow2(40);
    }

    return {len, v};
}

背景

• Daily Akari というサイトがあって、結構面白い
• LLMで400点ぐらいまでの問題はサクサク解ける => サクサク作問もできるんじゃないだろうか
• 毎日100-200-300-400みたいなDaily ABCが出来たら面白いんじゃないだろうか
• 本当はARC Div2とかの難易度まで作れないのかと思うが、とりあえず難しそうなので
• Geminiのクレジットが余っているのでなんか使いたい

進捗報告

とりあえず(Claude codeが)ガッと実装し、ひな形を作った。

4題生成させたので、これを貼って進捗報告とさせていただきます。400点ってなんだよって問題群ですが、なんか適当にプロンプトでdiffを指示してもうまくいかないので、今後の課題とさせていただきます。

ついでにest diff / interestも生成させてみた。diffはCF基準 / interestは1-10(だけど5以下が出力されているのは見たことない)。

Problem 1: 全域木クエリ (est diff: 2300 / interest: 8)

# 全域木クエリ

## 問題文
$N$個の頂点が与えられます。これらの頂点には$1, 2, \dots, N$のラベルが付けられています。
これらの頂点を接続する辺には2種類あります。

1.  **パス辺**: $1$から$N-1$までの各$i$に対し、頂点$i$と頂点$i+1$を重み$W_i$で接続する辺が存在します。
2.  **ショートカット辺**: $1 \le u < v \le N$を満たす任意の頂点ペア$(u, v)$に対し、「ショートカット」辺を作成できます。$N$個の正の整数からなる配列$A$が与えられます。$u$と$v$間のショートカット辺の重みは$A_u + A_v$です。

$Q$個のクエリが与えられます。各クエリは$1 \le L \le R \le N$を満たす整数のペア$(L, R)$で記述されます。
各クエリに対し、頂点集合$\{L, L+1, \dots, R\}$によって誘導される部分グラフを考えます。この部分グラフで利用可能な辺は次の通りです。
-   $L \le i < R$を満たすすべてのパス辺$(i, i+1)$。
-   $L \le u < v \le R$を満たすすべての可能なショートカット辺$(u, v)$。

各クエリに対し、対応する部分グラフの最小全域木 (MST) の総重みを求めるのがあなたの課題です。

## 制約
-   $2 \le N \le 2 \cdot 10^5$
-   $1 \le Q \le 2 \cdot 10^5$
-   $1 \le A_i \le 10^9$ ($1 \le i \le N$)
-   $1 \le W_i \le 10^9$ ($1 \le i < N$)
-   各クエリ$(L, R)$に対し、$1 \le L \le R \le N$かつ$R - L \ge 1$
-   入力される値はすべて整数である。

感想: 1日目なのに普通に問題が出てきてびっくりしています。ブログに貼ろうか正直悩んだ

Problem2: バランスの取れたインデックス (est diff 1600 / interest 6)

# 問題タイトル
バランスの取れたインデックス

## 問題文
`(1, 2, ..., N)` の順列 `P = (P_1, P_2, ..., P_N)` が与えられます。

各インデックス `i` ( `1` から `N` まで) について、以下の2つの値を定義します。
- `L_i`: `j < i` かつ `P_j > P_i` を満たすインデックス `j` の数。
- `R_i`: `k > i` かつ `P_k > P_i` を満たすインデックス `k` の数。

インデックス `i` は、`L_i = R_i` の場合に**バランスの取れた**インデックスと呼ばれます。

バランスの取れたインデックスの総数を求めてください。

## 制約
- `1 ≤ N ≤ 2 * 10^5`
- `P` は `(1, 2, ..., N)` の順列である。
- 入力値はすべて整数である。

感想: そう…

Problem3: 多項式の融合 (est diff 2300 / interest 8)

## 問題文
$N$ 個の正の整数 $A_1, A_2, \ldots, A_N$ が与えられます。
最初、 $N$ 個の多項式の集合があります。 $i$ 番目の多項式は $P_i(x) = 1 + x^{A_i}$ です。

多項式 $P(x)$ の非ゼロ係数の個数を $T(P)$ と定義します。

以下の操作を $N-1$ 回行います。
1. 現在の多項式の集合から、非ゼロ係数の個数 $T(P)$ と $T(Q)$ が最小となる2つの多項式 $P(x)$ と $Q(x)$ を選択します。複数の選択肢がある場合は、任意の一つを選択して構いません。
2. 選択した $P(x)$ と $Q(x)$ を集合から削除します。
3. それらの積 $R(x) = P(x) \cdot Q(x)$ を集合に追加します。

$N-1$ 回の操作後、集合には一つの多項式 $F(x)$ のみが残ります。
$F(x)$ の係数を $c_0, c_1, c_2, \ldots$ とします。整数 $K$ が与えられます。 $F(x)$ の係数のうち、$K$ 個の最大値の和を求めてください。

和を $998244353$ で割った余りを出力してください。

## 制約
- $2 \le N \le 10^5$
- $1 \le A_i$
- 全ての $A_i$ の合計は $2 \cdot 10^5$ を超えない。
- $S = \sum_{i=1}^{N} A_i$ とします。このとき $1 \le K \le S + 1$ です。
- 入力される値は全て整数である。

感想: 壮大な問題文で多項式の総積を求めよと言っている。そんな…

Problem4: 生成パターンマッチング(est diff 2300 / interest 8)

## 問題文
文字列 `S` を、最初は空文字列として定義します。
以下の操作を `N` 回行います。

1.  `k` を、以下の条件を全て満たす最長の文字列の長さとします:
    *   その文字列は `P` の**真の接頭辞**である。
    *   その文字列は現在の文字列 `S` の接尾辞である。
    ここで、`P` の真の接頭辞とは、`P` 自身を除く `P` の任意の接頭辞を指します。
2.  文字 `T[k]` (0-indexed) を `S` の末尾に追加します。

操作を `N` 回行った後の最終的な文字列 `S` において、`P` が部分文字列として出現する総回数を求めてください。
ここで、部分文字列としての出現とは、`S` の `j` 番目 (1-indexed) から始まる長さ `|P|` の部分文字列が `P` と等しいような `j` の個数を指します。

## 制約
- `1 ≤ N ≤ 10^18`
- `1 ≤ |P| ≤ 2000`
- `|T| = |P|`
- `P` および `T` は、英小文字 ('a'-'z') からなります。

感想: まあ、いいんじゃない…

感想まとめ

• そこはかとない希望を感じたのでクレジットが尽きるまでもう少しやってみようと思った。
• 調べたらAtCoderがもうやってるって情報が出てきた。企画倒れ…

UPD: 区間add / 0存在判定 Ω*(N^(1.5)) - よすぽの日記

太古に考え、メモってなかったのですが、最近思い出そうとして苦労したのでメモっておきます。

問題

以下の問題の計算量下界について考えます。

• 長さ $N$ の数列 $a_1, \cdots, a_N$ が与えられる。$N$ 個の以下のクエリを処理する。
  • 加算クエリ: $l, r, d$ が与えられるので、 $a_l, ..., a_r$ に $d$ を加算する。
  • 調査クエリ: $a_1, ..., a_N$ に $0$ は存在するか？

3-SUM / 使用する予想

今回は、サイズ $M = N^{2/3}$ の 3SUM を、この問題に帰着していきます。3-SUMは $O(M^{2 - \epsilon}) = O(N^{1.333 - \epsilon})$ 時間で解けないと信じられています(参考: wikiや https://lealgorithm.blogspot.com/2018/07/hardness-in-p-seth.html 等) 。

今回は 3-SUM の variant として、3つの配列が与えられるバージョンを使用します(wikiのThree different arraysを参照)。

サイズ $M$ の配列 $X, Y, Z$ が与えられる。$X_i + Y_j + Z_k = 0$ なる $(i, j, k)$ は存在するか？

帰着

サイズ $M = N^{2/3}$ の3-SUMのインスタンス $X, Y, Z$、および上記の数列の問題を $O(N^{1.333 - \epsilon})$ で解くsolverがあると仮定したときに、この 3-SUM が $O(M^{2 - \epsilon}) = O(N^{1.333 - \epsilon})$ 時間で解けることを示せばよい。

• $X$ を $N^{1/3}$ 回繰り返したサイズ $N$ の配列を用意し、数列の問題の初期値とする。
• $Y$ をサイズ $N^{1/3}$ の $N^{1/3}$ 個の配列に切り分け、それぞれについて下記の操作を行う。切り分けられた $Y$ を $Y'$ とする。
  • 数列は$X$ を $N^{1/3}$ 回繰り返したものになっているのだが、加算クエリを用いて、$Y'$ の要素をそれぞれの$X$全体に足しこむ。これにより、数列には $x + y (x \in X, y \in Y')$ が全て現れる。
  • $Z$ の各要素 $z$ について、数列に $-z$ が存在するかを判定する。これは3クエリ(全体 $+z$ → 調査クエリ → 全体 $-z$) で可能である。
  • 足しこんだ $Y'$ の要素を引くことで、数列を初期値に戻す

クエリの回数はループの中の $-z$ 存在判定がボトルネックであり、$O(N^{1/3} \times N^{2/3}) = O(N)$ である。よって示された。

ギャップ

この数列の問題は平方分割で $O(N^{3/2})$ で解くことが出来ますが、$\Omega(N^{4/3})$ と$O(N^{3/2})$ の間にギャップが残っています。

値域

倍数クエリ のように、値域が $O(N)$ である (ので、平方分割がhashmapなしでも動作する) という出題例があります。

このような問題のために、この記事の数列の問題に「常に $|a_i| \le N$ であるようなクエリしかこない」という制約を加えた場合はどうなるでしょうか？ 実は今回の帰着はこの制約を加えるとうまくいきません。具体的には、値域が $O(N)$ の 3-SUM しか解けなくなってしまいます。そしてこれはそもそもFFTで $O(N \log N)$ で解けます。"値域が $O(N)$ の 3-SUM を解くぐらいには難しい"というそれなりに説得力のある(が、理論的には特に何も言っていない)事実は得られます。

感想

3-SUMや、$4/3$ が何か出てきたのが面白いですね。でもなんか $\Omega(N^{3/2})$ が示せるんじゃないのかなとは思っています。