Universal Cup 4-19 M

準急が飛んだ(物理) + 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};
}

AHC 053 満点解法

AHC 053で優勝することができました。その解法を延長戦で改善したところ、全ケース満点まで到達できたので、その解法を紹介します。

当初は(詳細は省きますが)闇テクを使っていたのですが、最終的には300ケースに1回程度まで失敗率を下げ、闇テクなしで満点が取れるようになりました。

• Submission #69368404 - 12th Asprova Programming Contest（AtCoder Heuristic Contest 053）

問題

https://atcoder.jp/contests/ahc053/tasks/ahc053_a

マラソンの問題文として前代未聞の短さじゃないだろうかこれ。subset sumの強化版という雰囲気、一方で使う値は自由に指定できる。

解法

カードを使う枚数を固定

各グループのカードの枚数を8枚と固定してしまいます。$A_i$の値から $\frac{10^{15}}{8}$、$B_i$の値から$10^{15}$を引いて考えることで、この問題は次のように考えることができます。

• $A_i$ として 負の値も書くことができる
• $B_i$ として $[-E, +E] (E = 2 \times 10^{12})$ が与えられる

自分の解法だと圧倒的に見通しが良くなるので採用していますが、この言いかえをした方がいいのかは諸説 / 解法依存だと思います。

2段階で合わせる

おそらくここが一番のキーアイデアです。問題を前半 / 後半に分割し、$\sqrt{E}$ 倍ずつ調整します。

• 前半: 250枚のカードを4枚ずつ配る。$B_i$ をすべて $[- \sqrt{E}, + \sqrt{E}]$ の範囲に収める。*1
• 後半: 250枚のカードを4枚ずつ配る。$B_i$ をすべて $0$ にする。

前半と後半の問題は非常に似ており、実際に使用したアルゴリズムもほぼ同一です。

調整アルゴリズム

全てのグループの値を求める範囲に調整する方法ですが、最終的には非常に単純なアルゴリズムになりました。

初期解としてランダムにカードを4枚ずつ配り、以下の遷移をひたすら繰り返します。

• ランダムにグループを選び、4枚 + 未割当50枚から、合計が求める範囲に含まれる4枚組を探す
• 見つかった場合: 見つかった 4枚組を新しく割り当てる
• 見つからなかった場合
  • そのグループがもともと調整済みだった場合: 何もしない
  • そのグループがもともと調整済みではなかった場合: 54枚からランダムに4枚選んで割り当てる

山登りのようなアルゴリズムではありますが、調整済みかどうかだけを気にしており、誤差の大きさなどは一切気にしていないことに注意です*2。

54枚から 4 枚組を探す方法

上記のアルゴリズムのボトルネックは「4枚 + 未割当50枚から、合計が求める範囲となる 4枚組を探す」部分です。素直に探すと $C(54, 4) = 316251$ 程度の組合せを見る必要があります。ここで、

• 54枚をランダムに 27枚 * 2に分割し、 「前半から2枚 + 後半から2枚」という選び方のみを探す

と探索範囲を絞ることで、半分全列挙が行え、高速化ができます。かなり定数倍高速化をしたところ、最終的に2秒で 20万回弱 程度この探索が回るようになりました。

細かい工夫

• 大体の場合2秒もいらないのだが、運が悪いと詰むっぽいので、適当に打ち切って3回実行する
• 27枚 * 2に分割するときに、既存の4枚が2枚ずつ割り振られないようにする。すると既存の組合せが出てこなくなる
• 本番は $A_i$ は一様ランダムだったのだが、中心の方が密度が高い分布の方が性能が高かった。(GPTに聞いて出てきた)三角分布というやつを採用。

おまけ: なぜ2段階調整がよいのか？

まず、1段階調整だと何が難しいのかを考えます。

そもそも満点は取れるのか？500枚を8枚 * 50グループに割り当てる方法は $$ \frac{500!}{(8!)^{50} \times 100!} \approx 2^{2477} $$ であり、入力が $42 \times 50 = 2100$ bit程度であることを考慮すると、実は(無限の計算時間があれば)満点が取れそう。

計算時間の方はどうか？この解法は基本的に「当たり待ち」解法であり、仮に最高効率でbirthday attackをしたとしても、$O(N \sqrt{E} \log {E})$ 程度の計算量は必要そうです。よって、$\sqrt{E} \approx 10^{6}$であることを考えると、満点はかなり苦しそう(が、こうして書いてみるとハチャメチャに定数倍高速化すれば不可能ではない範疇な気もする？)

また、この問題には「指数的に調整する」という別方針もあります。例えばカードとして $10^{15} - 10^{12}, 10^{12}, \frac{10^{12}}{2}, \frac{10^{12}}{4}, \cdots$ を用意していけば、誤差をどんどん半分にできる…というような方針です。これは計算時間は爆速である一方で、精度を出すにはカードが大量に必要になります。

つまり、

• 当たり待ち: カードが少なくても精度が出る / 計算時間が大量に必要
• 指数的に調整: カードが大量に必要 / 計算は爆速

となり、これを眺めると2つの方針のハイブリッドをやりたくなり、自然に2段階調整の方針が出てきます(…と後付けで納得しましたが、本番中は特に何も考えていませんでした)。

実際に、2段階調整だと各段階の自由度は $$ \frac{250!}{(4!)^{50} \times 50!} \approx 2^{1192} $$ であり、$1050$ bitに対してはまだ余裕があります。ていうか $2477 \to 2384(=2 \times 1192)$ で8枚割り当てからあんまり自由度減ってないんですね。

計算時間はどうでしょうか？最終的に一回のイテレーションで $C(27, 2)^{2} = 123201$ 個の値を試しているので、$\frac{123201}{\sqrt{E}} = 8.7$ % 程度で調整済みの値が出てくると見積もれます。よって、雑には50倍して600回程度のイテレーションで全部調整可能というすごい計算になります。実際には

• $123201$ 個の値には大きすぎる / 小さすぎる ものが含まれる
• 使えるカードが毎回入れ替わる仮定だが、そんなことはない

などで更にイテレーションが必要になっていると考えられます。それでも直感的には10万回もイテレーションは必要ない気がしており、もしかしたらさらなる改善が出来るのかもしれません。

*1:実際はパラメーター調整したら $\pm 1.3 \times 10^{5}$ ぐらいに

*2:満点をとれるかだけに注目すると誤差の大きさは無視したほうが性能が良かったですが、満点じゃないときのスコアが壊滅します

競プロAI不正 怪文書

競プロ vs AI不正　ポエム。2,3年後にどれぐらい当たってたか振り返ろう

AI不正はいなくなるのか

他ゲーのチートと比較すると、絶望的な点として

• 誰でも手に入る
• PCに何もインストールする必要がない、危なくない
• 基本無料
• ちゃんと対策したらおそらくほぼ検知不可能

がある。一方で、以下の点で救いがある

• 多少チートがいてもゲームが壊れない
• そもそも(チートが蔓延するようなゲームと比べると)参加者の数がそんなに大きくない

検出回避が不可能というのは(もちろん！)真面目に取り組んでないのであくまで直感。検知回避最強プロンプト！みたいなのが有料で売られ出したらオモロイ

今後状況が改善に転ぶ可能性はあるのか？いくつか救済シナリオを考える

救済？シナリオ: 競プロが廃れる

シンプルにもっと競プロが廃れて、進学や就学に使えなくなればAI使用者も減るだろう。オンサイトコンテストや賞金も無くなってるだろうが。

別方向として、AIでプログラマー不要になってｲﾗﾈ→競プロ採用も辞めます　で普通に廃れる可能性もありますね

救済シナリオ: AIがもっと強くなる

AIが破壊できるのがちょうどボリュームゾーンのABCなのが良くない説。ARC Div1やAGCを破壊できるようになれば、ABCに多少の平和は戻るのではないか。

救済シナリオ: AI側がこの問題には答えません機能を提供する

AI側に事前に出題問題を提供することで、AI側がこの問題には答えません、という機能を提供する可能性。

学生のカンニングやレポート制作の文脈で、LLMがより一層社会問題になる→LLMベンダーが圧力に屈してやむなく機能を実装→競プロもおこぼれにあずかる、という可能性が0ではないかもしれない、いや0かなぁ…。

救済シナリオ: オンサイトが本質みたいな文化になる

PASTオンサイト、AJO等オンサイトコンテストでの結果が本質であり、レートはあくまで参考値、みたいな文化になると解決する説。

救済シナリオ: AI不正を許さないという文化が強まり、治安が良くなる

スーパー性善説。競プロ界隈の治安を守っていこう。実際もう現時点でもっとグチャグチャになってない時点で治安がいいという説はある。

• 不正erとかの内輪用語をやめて普通にチーターかカンニングって呼ぶ
• 不正した人をハチャメチャに叩く

あたりが効果的なんだろうか？治安の悪い提案やめてください！

競プロ問題自動生成2日目 ~ ちゃんと簡単な問題を作ろう ~

2日目です。

プロンプトや諸々を調整し、ちゃんと簡単な問題を作らせてみようの会

今日も生成された問題を張り付けて進捗報告とします

• A問題 * 4 : https://gist.github.com/yosupo06/4390fedc2225ff07b78dbc87209c03dd
• D問題 * 5 : https://gist.github.com/yosupo06/cb9d2035472fe95af158bfc9e43b798e

感想

• 難易度感としてはそこまで大外ししないようになった気がする
• 難易度 / 面白さ評価のほうのチューニングはこだわったほうがよさそうである　解けてない問題を解けてると言ったり、謎の問題に謎の高評価をつけたり
• 2.5proが高いので2.5 flashを使い始めたが、やっぱり結構クオリティに差がある気がする
• 次は実際の問題準備をやらせてみたいと思います

競プロ問題自動生成1日目 ~ Daily ABCを目指して ~

背景

• 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がもうやってるって情報が出てきた。企画倒れ…

区間add / 0存在判定 Ω*(N^(1.5))

区間add / 0存在判定 Ω(N^(1.333)) - よすぽの日記 を公開したらhosさんからΩ*(N^1.5)の証明が届いたので紹介します。前記事を読んでいることを前提とします。

Conv 3-SUM

3-SUMの wiki の Convolution sumとして紹介されているvariant(の、3array版)を考えます。

• 3つの長さ $N$ の配列 X, Y, Zが与えられる。X[i] + Y[j] = Z[i + j]なる$i, j (0 \le i, j \lt N)$は存在するか？

実はこれと元の3-SUMは、($O(N^{1.999})$ で解けるかという観点で)同じ難易度であることが知られています。

(3-SUM => Conv 3-SUM)の方向の帰着が難しい方向です。

例えば入力がランダムケースならば適当に $\bmod N$ で要素を分類することで帰着できます(関連: https://x.com/jcvbcn/status/1927106217819726132 )。これを発展させ、$N$ に近い $p$ とランダムな基数 $b(0 \le b \lt p)$ を取り、$x$ をグループ $bx \bmod p$ に割り振ることでいい感じに計算量が抑えられるという仕組みのようです。

参考: https://conferences.mpi-inf.mpg.de/adfocs18/karl/3-3SUM.pdf

帰着

サイズ $M = O(N^{3/4})$ のConv 3-SUMが、サイズ $N$ の数列の問題に帰着できることを示せばよいです。

まず、Conv 3-SUMを更に次のvariantへ帰着します(ここの帰着自体は自明ではないが難しくはないです)。

• 3つの(長さ $M^{2/4}$ の配列)の長さ $K = M^{1/4}$ の列 $X = X'_0, X'_1, \cdots, X'_{K-1}, Y, Z$が与えられる。$x + y = z (x \in X_i, y \in Y_j, z \in Z_{i + j})$ なる$i, j, x, y, z$は存在するか？

この問題を数列の問題に帰着します。

数列の初期値として $X'_0$ を $M^{1/3}$ 回連打, $X'_1$ を $M^{1/3}$ 連打, ... としたものを使用します。これの長さは $M^{4/3} = N$です。

各 $Z'_k$ に対する調査が、$O(M)$ クエリで出来ることを示せばよいです。これは以下の手順で可能です。

• 各 $Y'_0, \cdots, Y'_k$ から要素を $M^{1/3}$ ずつ取り出し、これらに対する調査をまとめて行う。これが $O(M^{2/3})$ クエリで出来ることを示せばよい。
  • $Y_i$ から取り出した要素を $X_{k - i}$ に加算クエリでマッピングする (計 $O(M^{2/3})$ クエリ)
  • $Z_k$ の各要素について、調査クエリを飛ばす (計 $O(M^{2/3})$ クエリ)
  • $Y_i$ のマッピングを戻す (計 $O(M^{2/3})$ クエリ)

よって合計 $O(M^{4/3}) = O(N)$ クエリであり、帰着が完了した

区間add / 0存在判定 Ω(N^(1.333))

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})$ が示せるんじゃないのかなとは思っています。