Kotlin Heroes はコンテストには参加せず,他の言語で書いたコードを chatgpt に変換してもらうことで AC しています.コンテスト中にこれをやるのはルール違反です.
A. Game
読解した通りに判定します.
B. Two Towers
同時に加算させられる回数が $[a,c]\cap[b,d]$ から求まります.
C. Minesweeper
$2$ 行ありますが,$1$ 行目にだけ置くと思ってよいです.
$3$ 列あたり $1$ 個は mine が必要で,おおよそ $3/5k$ 程度の列数が必要ということになります.
このことから $k\pmod{5}$ で場合分けをして慎重に構築します.
D. Two Arrays
何らかの長さで一致させられれば,そのあと同じように操作することで長さ $1$ での一致が可能です.よってそれぞれの列で,長さ $1$ になるまで操作したときに残る値としてありうるものが列挙できればよいです.
初期状態が長さ $1$ の場合は例外です.それ以外は min, max 以外を残せるという形になります.
E. Supersequence
基本的に $a_i$ から $a_{i+1}$ まで最小長さの連番でつなぐ,ということになりますが,$a_i=a_{i+1}$ のときだけ,$a_i\pm 1$ のどちらを経由するかの自由度があります.
F. Self-Produced Sequences
数えるべき列は $[0,0,0,x,x,0,0,0]$ のようなものしかないことが分かります.$0$ でないものがあればちょうど $2$ 個連続.
G. Jammer
円の中心を bounding box の外側にとることは禁止されていることに注意.
$n\leq m$ となるようにして $x$ 座標を固定して解きます.valid な場所は空または区間になってくれます.
「左下を覆わない」「右上を覆わない」「左辺または上辺と接触」「右辺または下辺と接触」の AND をとるだけです.
H. Sum of MEX
置き換えが $300$ 個以下だという特殊制約に注意します.
この個数を $K$ としたとき,置き換え後の mex の候補としては $K+1$ 値しかありません.
つまりその時点で出現していないもののうち小さい方から $K+1$ 個です.
prefix ごとの答えは,これら $K+1$ 個の mex および,置き換える回数だけから決まります.よって prefix ごとにこれらが求められるようにして,$O(K)$ 時間で処理するという方針で解けます.
前計算として,次のようなものを計算しておけばよいです.
- $a$ 個の値を好きに決めたとき,注目する $b$ 個の値($N$ 以下)がすべて出現するような決め方は?
これは包除原理などで計算しておくことができます.
I. Strange Process
ラス問ですが読解できれば非常に素直.判定問題を考えます.
- 整数の距離を,素数の multiset の対称差の大きさとして定義.
- $[0,N]$ からなる長さ $M$ の列 $b$ を数えてください.
- $0<b_i=b_j$ かつ $|j-i|<\mathrm{dist}[c_i][c_j]$ というのは禁止.
- $0<b_i$ かつ $i<\mathrm{dist}[1][c_i]$ というのは禁止.
任意の $2$ 数の距離が $8$ 以下になることを考慮して dp をします.$b_i$ を手前から順に定めていきますが,まず末尾 $8$ 項程度の情報しか要りません.その中では $b_i>0$ となっているところについて,同じ $b_i$ の最後の出現だけを代表して持てばよいです.
最後の出現の集合を dp の key として,$2^7$ 状態程度の素直な dp で解けます.
