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