問題概要
文字列 $S$ が与えられる.$S$ に対し,$S$ の添字 $i, j$ ($1 \leq i < j \leq |S|$) を選び,$S_i$ と $S_j$ を入れ替える操作をちょうど $1$ 回行う.この操作によって作られる文字列は何種類あるか?
制約
- $1 \leq |S| \leq 10^6$
- $S_i \in \mathcal C$
ここで,$\mathcal C$ はすべての英小文字からなる集合とする.
文字列 $S$ が与えられる.$S$ に対し,$S$ の添字 $i, j$ ($1 \leq i < j \leq |S|$) を選び,$S_i$ と $S_j$ を入れ替える操作をちょうど $1$ 回行う.この操作によって作られる文字列は何種類あるか?
ここで,$\mathcal C$ はすべての英小文字からなる集合とする.
$1 \times 1$ のセルからなる $h \times w$ のグリッド状の盤面と $n$ 枚のタイルがあり,タイル $i$ は $A_i \times B_i$ の長方形状である.
各タイルについて,グリッドに沿い,かつ盤面からはみ出さない範囲で自由に位置と向きを決めてグリッドに配位することができる(配置しなくてもよい).
グリッドのすべてのセルがちょうど $1$ 枚のタイルに被覆されている状態にできるか?
文字列の列が $n$ 個与えられる.$i$ ($1 \leq i \leq n$) 番目の列は $S_i = \langle S_{ i, 1 }, S_{ i, 2 }, \dots, S_{ i, A_i } \rangle$ である.
ここで,次の処理を行う.
操作終了後の $S$ を与えられる文字列 $T$ に一致させるとき,$S$ に代入する操作の回数の最小値はいくらか? 不可能な場合はそのことを報告せよ.
*1:ここで,$\epsilon$ は空文字列を表す.
相異なる $n$ 項からなる数列 $A = \langle A_1, A_2, \dots, A_n \rangle$ がある.
次の 2 種からなるクエリを $q$ 個,順に処理せよ.
各クエリの処理後,$A$ は空でなく,要素は相異なる.
最終的な $A$ を出力せよ.
$1$ から $n$ で番号付けられた $n$ 個の駅があり,$m $ 種類の路線が運行されている.各路線は 6 個の整数 $l, d, k, c, a, b$ *1で説明され,その意味は,
である.
駅 $s$ から駅 $n$ に到達できる時刻の内最遅のものを $f( s )$ で表す.到達できない場合は $-\infty$ と定義する.
$f( 1 ), f( 2 ), \dots, f( n - 1 )$ を求めよ.
*1:書くのが面倒だったので端折っていますが,正確には添字が付きます.原文参照のこと.