AtCoder Regular Contest 116のきろく

AtCoder AtCoder Regular Contest 競技プログラミング 参戦記

AtCoder Regular Contest 116でレート微増しました

A - Odd vs Even (300点)

N の素因数 2 の重複度(2-進付値)を e とし、N の約数で 2-進付値が i であるような数の集合を S_i とします。このとき 1 \leq i \leq e について S_i = \{2d \mid d \in S_{i-1}\} であり、i \gt e について S_i = \{\} = \emptyset です。

これらより N の正の奇数の約数の個数は \#S_0 であり、正の偶数の約数の個数は \displaystyle \sum_{i = 1}^{e} \#S_i = e\#S_0 であるので、e=0 のときは正の奇数の約数の方が多く、e=1 のときは両者の数は等しく、e \geq 2 のときは正の偶数の約数の方が多くなります。

B - Products of Min-Max (400点)

A をソートすると \max B \times \min B =\displaystyle \max_{i \in S} A_i \times \min_{i \in S} A_i の値は選んだ最大のインデックスと最小のインデックスで決まることになります。

最大のインデックスが i, 最小のインデックスが j である選び方について考えます。このとき \max B = A_i, \min B = A_j より \max B \times \min B = A_iA_j です。i = j のときはこのような選び方は 1 通りです。i \neq j のとき i \gt j であり、このような選び方は j+1, j+2, \dots, i-1 の i-j-1 個のインデックスをそれぞれ選ぶかどうかの 2^{i-j-1} 通りであるので、答えは \displaystyle \sum_{i = 1}^{N} A_i \left( A_i + \sum_{j = 1}^{i-1} 2^{i - j - 1}A_j \right) となります。

括弧の中の \displaystyle \sum_{j = 1}^{i-1} 2^{i - j - 1}A_j については \displaystyle \sum_{j = 1}^{i-1} 2^{i - j - 1}A_j = 2\sum_{j = 1}^{(i-1)-1} 2^{(i-1) - j - 1}A_j + A_{i-1} であるので累積和のような要領で O(N) 求めていくことができ、全体で O(N \log N) で解くことができます。
公式解説 では上記の最大と最小を逆にした考えで答えを求めているようです。

C - Multiple Sequences (500点)

最初は A_1 の値で場合分けをしようとして時間を食ってしまいました。左側から倍数を考えていくのは数が多く、かつ 1 \leq A_i \leq M という条件を満たすと考えるのは非常に困難です。

今回は重複組み合わせ {}_{n}\mathrm{H}\,{}_{r} を用います。これは n 種類のものから重複を許して r 個を選ぶ組み合わせの数で高校の数学Aでやるように {}_{n}\mathrm{H}\,{}_{r} = {}_{n+r-1}\mathrm{C}\,{}_{r} = \displaystyle\binom{n+r-1}{r} となります。丸と仕切りを並べるやつです。

A_N の値を固定したとき A_1,\,A_2,\,\dots,\,A_{N-1} の選び方についてみていきます。A_N の各素因数 p について重複度を e_p とすると A_1,\,A_2,\,\dots,\,A_{N-1} の素因数 p の重複度は 0 以上 e_p 以下の広義単調増加整数列となります。よって A_1 での素因数 p の重複度との差を r とすると重複度が増える箇所を N-1 箇所の中から重複を許して r 箇所選んだ時の場合の数となり(重複するときその箇所で 2 以上増加)、その場合の数は {}_{N-1}\mathrm{H}\,{}_{r} となります。これは各素因数ごとに独立です。よって、整数 n について素因数 p の重複度を e_{i,p}とすると 答えは \displaystyle \sum_{i = 1}^{M} \prod_{p;\ i の素因数}\hspace{5mm} \sum_{j = 0}^{e_{i,p}} {}_{N-1}\mathrm{H}\,{}_{j} となります。素因数も重複度も高々 O(\log M) であるので、組み合わせが高速に求まるように前計算しておくことで O(M(\log M)^2) で求めることができます。

また \displaystyle \sum_{j = 0}^{e_{i,p}} {}_{N-1}\mathrm{H}\,{}_{j} の部分は次の2通りの考え方で高速化することができます。

0個目を考える

便宜上 A_0 = 1 というものを最初に追加することで 重複度が増える箇所を N-1 箇所の中から重複を許して e_{i,p} 箇所選んだ時の場合の数に帰着することができるので {}_{N}\mathrm{H}\,{}_{e_{i,p}} となります。

計算する(数学的帰納法)

\displaystyle \sum_{j = 0}^{k} {}_{N-1}\mathrm{H}\,{}_{j} = {}_{N+k-1}\mathrm{C}\,{}_{k} となることを証明します。

I) k = 0 での成立
{}_{N-1}\mathrm{H}\,{}_{0} = {}_{N-2}\mathrm{C}\,{}_{0} = 1 = {}_{N-1}\mathrm{C}\,{}_{0} より成立します。

II) k で成立 \Longrightarrow k+1 で成立

\begin{align} \sum_{j = 0}^{k+1} {}_{N-1}\mathrm{H}\,{}_{j} &= \sum_{j = 0}^{k} {}_{N-1}\mathrm{H}\,{}_{j} + {}_{N-1}\mathrm{H}\,{}_{k+1} = {}_{N+k-1}\mathrm{C}\,{}_{k} + {}_{N+k-1}\mathrm{C}\,{}_{k+1} \\ & = {}_{N+k}\mathrm{C}\,{}_{k+1} = {}_{N+(k+1) - 1}\mathrm{C}\,{}_{k+1} \end{align}
より成立します。

故にI), II)より数学的帰納法により成立します。
この2つの考え方ですが、{}_{N}\mathrm{H}\,{}_{e_{i,p}} = {}_{N+e_{i,p}-1}\mathrm{C}\,{}_{e_{i,p}} より両者は同じです。

D - I Wanna Win The Game (600点)

3つ目の条件 A_1\ \mathrm{xor}\ A_2\ \mathrm{xor}\ \cdots\ \mathrm{xor}\ A_N = 0 と1つ目の条件 0 \leq A_i より二進法での桁DPを考えます。2つ目の条件 \displaystyle \sum_{i = 1}^{N} A_i = M より各 A_i の桁数は M の桁数以下であるので*1、\lfloor \log_2 M \rfloor + 1 桁だけ考えればいいことが分かります。M \leq 5000 なので \lfloor \log_2 M \rfloor + 1 \leq 13 ですね。また、3つ目の条件より各桁について A_i のその桁が 1 となるような i は偶数個でなければならないことが分かります。

$$ {\mathrm{dp}}_{i,j} = (\text{下から \(i\) 桁を 3 つ目の条件を満たすように決めたときの和が \(j\) となる場合の数}) $$ とし、このとき

{\mathrm{dp}}_{0,j} = \left\{ \begin{array}{ll} 1 & (j = 0)\\ 0 & (\text{otherwise}) \end{array} \right.
であり、i \geq 1 について$$ {\mathrm{dp}}_{i,j} = \sum_{k=0}^{\min\left\{ \left\lfloor \frac{N}{2} \right\rfloor ,\, \left\lfloor \frac{j}{2^i} \right\rfloor\right\}} {}_N \mathrm{C}_{2K}\, {\mathrm{dp}}_{i,j - 2k 2^{i-1}} = \sum_{k=0}^{\min\left\{ \left\lfloor \frac{N}{2} \right\rfloor ,\, \left\lfloor \frac{j}{2^i} \right\rfloor\right\}} {}_N \mathrm{C}_{2K}\, {\mathrm{dp}}_{i,j - 2^i k} $$ となります。 総和の上限が少し複雑ですが、これは「配るDP」で書くことによって上限について考えずにコードを組むことができます。

E - Spread of Information (800点、実行時間制限: 3 sec): 未提出

グラフは木となるので葉から...みたいに考えましたが分かりませんでした...

F - Deque Game (800点): 未提出

ゲーム問題苦手...

結果、感想

f:id:Flkanjin:20210329165234p:plain
C問題で前計算の数が少なすぎて3WA出してしまい、それに思い至るまでに時間を食ってしまいました... D問題でも上の桁から考えていたのでそれで考えが少し複雑になってしまい、バグ取りに時間がとられてしまいました。もっと早く通せていれば黄色パフォだったかも...

*1:3つ目の条件より「以下」の部分は「未満」、すなわち同じになることがないことは分かりますが別にそこまで考える必要はないです

AtCoder Beginner Contest 197のきろく

AtCoder 競技プログラミング AtCoder Beginner Contest 参戦記

AtCoder Beginner Contest 197（Sponsored by Panasonic）に参加。微増しましたがHighest更新ではありませんでした。

A - Rotate (100点)

std::rotateやstd::string.substrを使ってもできますが、今回は3文字固定なのでS[1], S[2], S[0]の順に出力すればいいです。

B - Visibility (200点)

マス (X,\,Y) から4方向それぞれへ範囲外に出る、もしくは障害物がにぶつかるまで数えながら進んでいけばいいです。実装方法によってはスタートマスの重複カウントに注意。

C - ORXOR (300点)

区間の分け方は最後を除くどの要素の後で区切るかの 2^{N-1} 通りでこれをbit全探索していくことで答えを出すことができます。
答えの初期値を 10^9 にしていたのですが、この問題では最大 2^{30}-1 = 1\,073\,741\,823 になりうるので、1WA出してしまいました...

またこの問題はDFSでも答えを出すことができ、こっちの場合は関数の返り値を答えにすればいいので、初期値に悩まされる心配はありません。

D - Opposite (400点)

N が偶数であり、p_0 と p_{\frac{N}{2}} の中点が正 N 角形の対称中心*1になり、この点を o とします。この正 N 角形の頂点は点 o を中心とする円の演習を N 等分する N 点であり、p_0,\,p_1,\,\dots,\,p_{N-1} は反時計回りに並んでいるので、\overrightarrow{o\,p_1} は \overrightarrow{o\,p_0} を点 o 中心で反時計回りに \displaystyle \frac{360}{N}^\circ = \frac{2\pi}{N} 回転させたものであるので、点 p_1 の座標を計算することができます。

\begin{pmatrix} x \\ y \\ \end{pmatrix} を始点中点で反時計周りに角度 \theta だけ回転させるとき、x = r \cos \alpha, y = r\sin\alpha となる実数 r,\,\alpha を用いると回転後のベクトルは \begin{pmatrix} r \cos (\alpha + \theta) \\ r \sin (\alpha + \theta) \\ \end{pmatrix} = \begin{pmatrix} x \cos \theta - y \sin \theta \\ x \sin \theta + y \sin \theta \\ \end{pmatrix} となります(途中式は加法定理を用いて計算)。これを直接計算さてもいいですし、回転は一次変換であることから回転行列 \boldsymbol{R}_{\theta} = \begin{pmatrix} \cos\theta & -\sin\theta \\ \sin\theta & \cos\theta \\ \end{pmatrix} を用いた行列積でも求まりますし、Gauß平面上の回転は複素数の積であることから (x + \mathrm{i}y)(\cos \theta + \mathrm{i}\sin \theta) = (x\cos \theta - y\sin \theta) + \mathrm{i}(x \sin \theta + y \sin \theta) でも計算することができます。

また、別解として \triangle{p_0p_1p_{\frac{N}{2}}} は \angle p_1 = 90^\circ (p_0p_{\frac{N}{2}} が直径より円周角), \angle p_{\frac{N}{2}} = \displaystyle \frac{180}{N}^\circ = \frac{\pi}{N} (これも円周角) の三角形であることから \overrightarrow{p_{\frac{N}{2}}p_1} は \overrightarrow{p_{\frac{N}{2}}p_0} を点 p_{\frac{N}{2}} 中心で反時計回りに \displaystyle \frac{\pi}{N} 回転させたものを \displaystyle \cos \frac{\pi}{N} 倍したものになる、という解法があります。

E - Traveler (500点)

回収するボールの色を表す整数が広義単調増加でなければならないので色の回収順は固定されています。

色が c であるようなボール(のインデックス)の集合を S_c とすると色 c を回収しているときに \displaystyle \min_{i \in S_c} X_i と \displaystyle \max_{i \in S_c} X_i の両方を訪れる必要があり、その一方を訪れたのちもう一方へ向かう途中に色 c であるようなボールを全て回収することができます。同じ色の改修中に両端点を複数回訪れることに意味はないため、どちらの端点を先に訪れるかを決めたときこのような回収方法が最適手の1つとなります。

さて各色ごとにどちら向きに進むのが最善かを判断することになりますが、これは前の色をどちら向きで回収するかによって最後の位置が決まるのでそれを基にDPで求めることができます。
色について座標圧縮しておいて i 番目に小さい色を k_i とし、この色の個数を n とします。ただし、最初と最後には座標 0 にいなければならないため、便宜上 k_0,\,k_{n+1} (\forall i, k_0 \lt C_i \lt k_{n+1}) と存在しない色を追加し、この色のボールが座標 0 にあるものとします。また、d_i = \displaystyle \max_{i \in S_{k_i}} X_i - \min_{i \in S_{k_i}} X_i とします。


$$ {\mathrm{dp}}_{i,j} = (\text{色 \(k_i\) のボールを (\(j=0\) ? 右 : 左) 向きにとる時の最後までの最小移動距離}) $$ としたとき $$ {\mathrm{dp}}_{0,0} = {\mathrm{dp}}_{0,1} = 0 $$ であり、0 \lt i \leq n+1 について
$$
{\mathrm{dp}}_{i,0} = \min\left\{{\mathrm{dp}}_{i-1,0} + \left|\max_{i \in S_{k_{i-1}}} X_i - \min_{i \in S_{k_i}} X_i \right|,\,{\mathrm{dp}}_{i-1,1} + \left|\min_{i \in S_{k_{i-1}}} X_i - \min_{i \in S_{k_i}} X_i \right| \right\} + d_i
$$ $$
{\mathrm{dp}}_{i,1} = \min\left\{{\mathrm{dp}}_{i-1,0} + \left|\max_{i \in S_{k_{i-1}}} X_i - \max_{i \in S_{k_i}} X_i \right|,\,{\mathrm{dp}}_{i-1,1} + \left|\min_{i \in S_{k_{i-1}}} X_i - \max_{i \in S_{k_i}} X_i \right| \right\} + d_i
$$

という漸化式が成り立ち、答えは {\mathrm{dp}}_{n+1,0} = {\mathrm{dp}}_{n+1,1} となります。

F - Construct a Palindrome (600点、実行時間制限: 3 sec)

回文ができる時、「1 \rightarrow v と N \rightarrow v で同じ文字列のパスが存在するような頂点 v が存在する」、または「1 \rightarrow u と N \rightarrow v で同じ文字列のパスが存在するような隣接頂点組 (u,\,v) が存在する」が成立します。始点である頂点 1 と終点である頂点 N から同時に同じ文字が書かれている辺を辿って同じ頂点もしくは隣接頂点に到達するかどうかを調べればいい、という所まではコンテスト中に考察できましたが、そこから何も進めませんでした。

次のようなグラフを考えます。N^2 頂点で、各頂点は元のグラフの2頂点の組に対応する(2つが同じ頂点でもよい)、ここで (u,\,v) に対応する頂点を \mathrm{node}(u,\,v) と表記します。辺については元のグラフで u_1,\,u_2 の辺と v_1,\,v_2 の辺で同じ文字が書かれている辺が存在する場合 \mathrm{node}(u_1,\,v_1) と \mathrm{node}(u_2,\,v_2) の間に無向辺を張ります。

このグラフにおいて元の「1 \rightarrow v と N \rightarrow v で同じ文字列のパスが存在するような頂点 v が存在する」ことは \mathrm{node}(1,\,N) から \mathrm{node}(v,\,v) への経路が存在し、その距離の2倍が回文の長さになります。
また、「1 \rightarrow u と N \rightarrow v で同じ文字列のパスが存在するような隣接頂点組 (u,\,v) が存在する」については \mathrm{node}(1,\,N) から \mathrm{node}(u,\,v) への経路が存在し、その距離の2倍 + 1 が回文の長さになります。

よって \mathrm{node}(1,\,N) から各頂点への最短距離を求めることで答えを導くことができます。この最短距離はBFSで求めることができます。

結果、感想

f:id:Flkanjin:20210328174145p:plain
レートはギリギリ暖まりました。もっとCやDを早く通せていればパフォーマンス1800行ってかもしれないと思うともっと精進しなければと思います。

*1:外心でもある

Codeforces Round #710 (Div. 3)のきろく

Codeforces 競技プログラミング Codeforces Div. 3 参戦記

青に復帰しました。問題文和訳はこちら

A. Strange Table / Странная таблица

i 行 j 列 (i,\,j は0オリジン) の"by columns"での数値は jn + i + 1 であるので、x = jn + i + 1 より i = (x-1) \bmod{n}, \displaystyle j = \left\lfloor \frac{x-1}{n} \right\rfloor が求まります。
i 行 j 列の"by rows"での数値は im + j + 1 となるのでこれに代入して答えが求まります。

B. Partial Replacement / Частичная замена

条件を満たしつつできるだけ置き換える'*'を離した時が最適解です。'*'の位置を配列等で記憶しておいてstd::upper_boundなどの二分探索系の関数を用いたり、実際に探していくことで求めることができます。

C. Double-ended Strings / Двусторонние строки

制約が小さいので a,\,b 両方の開始位置と作る文字列の長さを全探索することができます。長さに関しては尺取り法によって高速化できます。
長さが n のとき操作回数は |a| + |b| - 2n となります。よって最大の長さを探せばいいです。

D. Epic Transformation / Эпическая трансформация

制約が小さいので毎回最多2つを減らしていくという貪欲法で通すことはできます。しかし、次のようにも求められます。

一番多いのが過半数の場合

一番多いのとそれ以外のものをペアにして消していくことができ、その個数を c とすると n - 2(n-c) = 2c - n を達成することができます。それ以外の消し方ではこの数を達成することができません。

そうでない場合

n が奇数の時はどうしても1つ残りますが、毎回最多2つを減らしていくことで全てのペアを消すことができます。
この時 n を 2 で割った余りだけ残ります。

E. Restoring the Permutation / Восстановление перестановки

左から順に答えを作っていきます。辞書順最小のものを a, 最大のものを b とします。

i = 1 または q_i \neq q_{i -1} のときは a_i = b_i = q_i となります。

そうでないとき、a についてはこれまで a に選ばれていない数のなかで最小のものが a_i になります。b についてはこれまで b に選ばれてない数のうち q_i 未満で最大のものが b_i です。

F. Triangular Paths / Треугольные пути

三角形内において上から下へしか動くことができないので r の小さい順に訪れまるのでそのようにソートしておきます。

(r,\,c) について (x,\,y) = (r-c,\,c-1) と座標変換します。変換後の座標においては x が偶数の時は右、つまり (x+1,\,y) への辺が活性化していて、奇数の時は上、つまり (x,\,y+1) への辺が活性化しています。

さて、(r_i,\,c_i) から (r_{i+1},\,c_{i+1}) へ行くときのコストはどうなるでしょうか? それぞれの変換後の座標を (x_i,\,y_i), (x_{i+1},\,y_{i+1}) とします。このとき問題文中の経路が必ず存在するという制約から x_i \leq x_{i+1}, y_i \leq y_{i+1} であることが分かります。

$ \displaystyle \left\lfloor \frac{x_i}{2} \right\rfloor \lt \left\lfloor \frac{x_{i+1}}{2} \right\rfloor $ のとき

x が奇数の時 y 座標が y_{i+1} になるまで上に上がり、そこから右に行くことでコスト \displaystyle \left\lfloor \frac{x_{i+1}}{2} \right\rfloor - \left\lfloor \frac{x_i}{2} \right\rfloor で行くことができます。

$ x_i = x_{i+1} $ で偶数のとき

ずっと上に行くことでコスト y_{i+1} - y_i で行くことができます。

その他のとき

活性辺のみを辿って目的地に着くことができます。つまり、コスト 0 である。


よってこれらのコストを合計することで答えを出すことができます。

G. Maximize the Remaining String / Максимизируй оставшуюся строку

本番では解けませんでした...

答えとなる文字列の長さは s 内の文字の種類数となります。
この文字列について左から順にそこの場所を占めてもいい最大の文字で埋めていきます。

ある文字 c がその場所を占めてもいいかは、それよりも右にそれまで出てきていない文字のみを寄せるかどうかの判別で行うことができます。

結果、感想

f:id:Flkanjin:20210326232527p:plain
F問題も通せれば全完だったのに...とは思いますが、何とか青色に復帰できてよかったなぁっていう感じです。地味にHighestも更新。

Codeforces Round #710 (Div. 3) 問題文和訳

Codeforces 競技プログラミング Codeforces 和訳 Codeforces Div. 3 和訳

A. Strange Table / Странная таблица

テストごとの時間制限: 2秒
テストごとのメモリ制限: 256 MB
入力: 標準入力
出力: 標準出力
Поликарп*1は n 行 m 列の長方形の表を見つけました。表の各セルには数字が書かれていて、その数は次のような「列による」アルゴリズムによって得られることに気が付きました。

  • セルは1から順に数が振られる
  • セルは列ごとに左の列から右の列へと数が振られ、各列内では上から下へ向かって数が振られる
  • 各セルの番号は前のセルよりも1大きい整数である

例えば、n =3, m = 5 の場合、表は次のように数が振られます。
$$
\begin{matrix}
1 & 4 & 7 & 10 & 13 \\
2 & 5 & 8 & 11 & 14 \\
3 & 6 & 9 & 12 & 15 \\
\end{matrix}
$$
しかし、Поликарпはこのような番号付けは不便であると考えています。彼は「行による」番号付けを好みます。

  • セルは1から順に数が振られる
  • セルは行ごとに上の行から下の列へと数が振られ、各列内では左から右へ向かって数が振られる
  • 各セルの番号は前のセルよりも1大きい整数である

例えば、n =3, m = 5 の場合、Поликарпは次のような表の番号付けを好みます。
$$
\begin{matrix}
1 & 2 & 3 & 4 & 5 \\
6 & 7 & 8 & 9 & 10 \\
11 & 12 & 13 & 14 & 15 \\
\end{matrix}
$$
Поликарпにはあまり時間がないため、「列による」番号付けで x であるようなセルの「行による」番号付けでの番号が何になるかを調べるよう頼まれています。

入力

1行目には単一の整数 t (1 \leq t \leq 10^4) が与えられる。そののち t 個のテストケースが続く。

各テストケースは単一行で構成され、3つの整数 n,\,m,\,x (1 \leq n,\,m \leq 10^6, 1 \leq x \leq n \cdot m) が与えられる、ここで、n,\,m は行数と列数であり、x はセルの番号である。

数値が 32-bit整数型に収まらないテストケースが存在するため、プログラミング言語の 64-bit以上の整数型を用いる必要があることに注意せよ。

出力

各テストケースについて、「列による」番号付けでのセルの番号を出力せよ。

入出力例

5
1 1 1
2 2 3
3 5 11
100 100 7312
1000000 1000000 1000000000000
1
2
9
1174
1000000000000

B. Partial Replacement / Частичная замена

テストごとの時間制限: 2秒
テストごとのメモリ制限: 256 MB
入力: 標準入力
出力: 標準出力
数 k と、文字'.'と'*'から成る n 文字の文字列 s が与えられます。以下の条件を満たすようにいくつかの'*'文字を'x'文字に置換したいと思っています。

  • 元の文字列の最初の'*'文字は'x'に置換されてなければならない
  • 元の文字列の最後の'*'文字は'x'に置換されてなければならない
  • 置換された隣り合う2つの文字'x'間の距離は k を超えてはならない(より形式的には、位置 i と j (i \lt j) で置換を行い、位置 [i+1,\,j-1] に記号'x'が存在しない場合、j-i はk 以下でなければならない)

例えば、n = 7, s= .**.***, k=3 の場合、以下の文字列は上記の条件を満たしています。

  • .xx.*xx
  • .x*.x*x
  • .xx.xxx

しかし、例えば、以下の文字列は条件を満たしません。

  • .**.*xx (最初の'*'文字は'x'に置換されてなければならない)
  • .x*.xx* (最後の'*'文字は'x'に置換されてなければならない)
  • .x*.*xx (位置 2 と 6 間の距離は k = 3 よりも大きい)

n,\,k,\,s が与えられたとき、上記を条件を満たすために'x'に置換しなければならない'*'文字の最小数を求めてください。

入力

1行目には単一の整数 t (1 \leq t \leq 500) が与えられる。そののち t 個のテストケースが続く。

各テストケースの1行目には2つの整数 n,\,k (1 \leq k \leq n \leq 50) が与えられる。

各テストケースの2行目には文字'.'と'*'から成る n 文字の文字列 s が与えられる。

文字列 s には少なくとも1つの'*'が存在することは保証される。

任意の隣り合う2つの'*'文字の間の距離が k を超えないことは保証される。

出力

各テストケースについて上記を条件を満たすために'x'に置換しなければならない'*'文字の最小数を出力せよ。

入出力例

5
7 3
.**.***
5 1
..*..
5 2
*.*.*
3 2
*.*
1 1
*
3
1
3
2
1

C. Double-ended Strings / Двусторонние строки

テストごとの時間制限: 2秒
テストごとのメモリ制限: 256 MB
入力: 標準入力
出力: 標準出力
小文字のラテン文字から成る文字列 a,\,b が与えられます。以下の操作を任意の回数、任意の順番で行うことができます。

  • |a| \gt 0 の(文字列 a の長さが0より大きい)とき、文字列 a の最初の文字を削除する、つまり、a を a_2 a_3 \dots a_n に置換する
  • |a| \gt 0 のとき、文字列 a の最後の文字を削除する、つまり、a を a_1 a_2 \dots a_{n-1} に置換する
  • |b| \gt 0 の(文字列 b の長さが0より大きい)とき、文字列 b の最初の文字を削除する、つまり、b を b_2 b_3 \dots b_n に置換する
  • |b| \gt 0 のとき、文字列 b の最後の文字を削除する、つまり、b を b_1 b_2 \dots b_{n-1} に置換する

それぞれの操作の後、文字列 a または b が空になることがあることに注意して下さい。

例えば、a= "hello", b= "icpc"の場合、次のような一連の操作を行うことができます。

  • 文字列 a の最初の文字を削除 \Rightarrow a= "ello", b= "icpc"
  • 文字列 b の最初の文字を削除 \Rightarrow a= "ello", b= "cpc"
  • 文字列 b の最初の文字を削除 \Rightarrow a= "ello", b= "pc"
  • 文字列 a の最後の文字を削除 \Rightarrow a= "ell", b= "pc"
  • 文字列 b の最後の文字を削除 \Rightarrow a= "ell", b= "p"

与えられた文字列 a,\,b について、文字列 a,\,b を等しくするための最小の操作回数を求めてください。空文字列同士も等しいものとすることに注意して下さい。

入力

1行目には単一の整数 t (1 \leq t \leq 100) が与えられる。そののち t 個のテストケースが続く。

各テストケースの1行目には小文字のラテン文字から成る文字列 a (1 \leq |a| \leq 20) が与えられる。

各テストケースの2行目には小文字のラテン文字から成る文字列 b (1 \leq |b| \leq 20) が与えられる。

出力

各テストケースについて、文字列 a,\,b を等しくするための最小の操作回数を出力せよ。

入出力例

5
a
a
abcd
bc
hello
codeforces
hello
helo
dhjakjsnasjhfksafasd
adjsnasjhfksvdafdser
0
2
13
3
20

D. Epic Transformation / Эпическая трансформация

テストごとの時間制限: 2秒
テストごとのメモリ制限: 256 MB
入力: 標準入力
出力: 標準出力
整数から成る長さ n の配列 a が与えられます。配列 a に対し、数ステップからなる次の操作を0回以上適用することができます。

  • 配列内の異なる2数 a_i,\,a_j を選ぶ
  • 配列から i 番目と j 番目の要素を削除する

例えば、n = 6, a = [1,\,6,\,1,\,1,\,4,\,4] の場合、次のような一連の操作を行うことができます。

  • i = 1, j = 5 を選び、配列 a は [6,\,1,\,1,\,4] になる
  • i = 1, j = 2 を選び、配列 a は [1,\,4] になる

配列に一連の操作を施した後の配列のサイズの最小値はどうなるでしょうか?

入力

1行目には単一の整数 t (1 \leq t \leq 10^4) が与えられる。そののち t 個のテストケースが続く。

各テストケースの1行目には単一の整数 n (1 \leq n \leq 2 \cdot 10^5) が与えられる、これは配列 a の長さである。

各テストケースの2行目には n 個の整数 a_1,\,a_2,\,\dots,\,a_n (1 \leq a_i \leq 10^9) が与えられる。

全てのテストケースでの n の和が 2 \cdot 10^5 を超えないことは保証されている。

出力

各テストケースについて、配列に一連の操作を施した後の、サイズの可能な最小値を出力せよ。

入出力例

5
6
1 6 1 1 4 4
2
1 2
2
1 1
5
4 5 4 5 4
6
2 3 2 1 3 1
0
0
2
1
0

E. Restoring the Permutation / Восстановление перестановки

テストごとの時間制限: 2秒
テストごとのメモリ制限: 256 MB
入力: 標準入力
出力: 標準出力
順列とは 1 から n までの n 個の整数がちょうど1回ずつ現れるような数列です。例えば、[1], [3,\,5,\,2,\,1,\,4], [1,\,3,\,2] は順列で、[2,\,3,\,2], [4,\,3,\,1], [0] は順列ではありません。

Поликарпは 1 から n までの数の順列 p を貰いました。しかし、Поликарпが家に帰ったとき、ポケットの中の順列 p が以下のルールに従っ配列 q に変わっていることに気が付きました。

  • q_i = \max(p_1,\,p_2,\,\dots,\,p_i)

ここで、Поликарпは与えられた順列としてあり得る辞書順最小の配列と辞書順最大の配列がどんなものか疑問に思いました。

長さ n の配列 a が長さ n の配列 b よりも辞書順で小さいとは配列 a と b の最初の i - 1 個の要素が一致し、配列 a の i 番目の要素が配列 b の i 番目の要素より小さい場合です。例えば、配列 [1,\,3,\,2,\,3] は配列 [1,\,3,\,4,\,2] よりも辞書順で小さいです。

例えば、n = 7, p = [3,\,2,\,4,\,1,\,7,\,5,\,6] の場合、q = [3,\,3,\,4,\,4,\,7,\,7,\,7] となり、この場合、元の p としては次のような順列が考えられます。

  • [3,\,1,\,4,\,2,\,7,\,5,\,6] (辞書順最小順列)
  • [3,\,1,\,4,\,2,\,7,\,6,\,5]
  • [3,\,2,\,4,\,1,\,7,\,5,\,6]
  • [3,\,2,\,4,\,1,\,7,\,6,\,5] (辞書順最大順列)

与えられた配列 q についてПоликарпに最初に渡された可能性のある辞書順最小の順列と辞書的最大の順列を求めて下さい。

入力

1行目には単一の整数 t (1 \leq t \leq 10^4) が与えられる。そののち t 個のテストケースが続く。

各テストケースの1行目には単一の整数 n (1 \leq n \leq 2 \cdot 10^5) が与えられる。

各テストケースの2行目には n 個の整数 q_1,\,q_2,\,\dots,\,q_n (1 \leq q_i \leq n) が与えられる。

配列 q がある順列 p に問題文中のルールを適用して得られたものであることは保証されている。

全てのテストケースでの n の和が 2 \cdot 10^5 を超えないことは保証されている。

出力

各テストケースについて、2行を出力せよ。

  • 1行目に n 個の整数を出力せよ、これらはПоликарпに最初に渡された可能性のある辞書順最小の順列である
  • 2行目に n 個の整数を出力せよ、これらはПоликарпに最初に渡された可能性のある辞書順最大の順列である

入出力例

4
7
3 3 4 4 7 7 7
4
1 2 3 4
7
3 4 5 5 5 7 7
1
1
3 1 4 2 7 5 6 
3 2 4 1 7 6 5 
1 2 3 4 
1 2 3 4 
3 4 5 1 2 7 6 
3 4 5 2 1 7 6 
1 
1

F. Triangular Paths / Треугольные пути

テストごとの時間制限: 2秒
テストごとのメモリ制限: 256 MB
入力: 標準入力
出力: 標準出力
複数の層で構成された無限の三角形を考えてみましょう。三角形の上から(上から下へ)、1から順に番号を振っていきます。三角形の k 層目は左から右に番号が振られた k 点が含まれます。無限三角形の各点は数の組 (r,\,c) (1 \leq c \leq r) で記述されます、ここで、r は層の番号で、c は層内の点の番号です。各点 (r,\,c) からは点 (r+1,\,c) へと (r+1,\,c+1) への2本の有向辺がありますが、そのうち1本のみが活性化しています。r + c が偶数の場合は (r+1,\,c) への辺が活性化され、そうでない場合は (r+1,\,c+1) への辺が活性化されます。よりよい理解のためには図を見てください。

f:id:Flkanjin:20210326134127p:plain
活性辺は黒で色づけられています。非活性辺は灰色で色づけられています。

活性辺のみから成る経路が存在する場合、点 (r_1,\,c_1) から点 (r_2,\,c_2) へ行くことができます。例えば、上図で、(1,\,1) から (3,\,2) への経路は存在しますが、(2,\,1) から (1,\,1) への経路は存在しません。

最初は点 (1,\,1) にいます。各ターン次のことが行えます。

  • 点 (r,\,c) 空の辺を取り換える。点 (r+1,\,c) への辺が活性化されていれば、それの代わりに点 (r+1,\,c+1) への辺が活性化され、そうではなく点 (r+1,\,c+1) への辺が活性化されていれば、それの代わりに点 (r+1,\,c) への辺が活性化される。この行動は経路のコストを 1 増加させる
  • 活性辺を辿って現在の点から次の点へ移動する。この行動は経路のコストを増加させない

無限三角形上の n 点 (r_1,\,c_1), (r_2,\,c_2), \dots, (r_n,\,c_n) が与えられます。(1,\,1) から任意の順序で n 個の点を全て通過する最小コストの経路を求めてください。

入力

1行目には単一の整数 t (1 \leq t \leq 10^4) が与えられる。そののち t 個のテストケースが続く。

各テストケースは単一の整数 n (1 \leq n \leq 2 \cdot 10^5) が与えられる行で始まる、これは訪れる点の個数である。

各テストケースの2行目には n 個の整数 r_1,\,r_2,\,\dots,\,r_n (1 \leq r_i \leq 10^9) が与えられる、ここで r_i は i 番目の点が位置する層の番号である。

各テストケースの2行目には n 個の整数 c_1,\,c_2,\,\dots,\,c_n (1 \leq c_i \leq r_i) が与えられる、ここで c_i は r_i 層目内の i 番目の点の番号である。

全ての n 点が異なることは保証されている。

全ての n 点を横断する方法が常に少なくとも1通り存在することは保証されている。

全てのテストケースでの n の和が 2 \cdot 10^5 を超えないことは保証されている。

出力

各テストケースについて、対応するテストケースの全ての点を通過する経路の最小コストを出力せよ。

入出力例

4
3
1 4 2
1 3 1
2
2 4
2 3
2
1 1000000000
1 1000000000
4
3 10 5 8
2 5 2 4
0
1
999999999
2

G. Maximize the Remaining String / Максимизируй оставшуюся строку

テストごとの時間制限: 2.5秒
テストごとのメモリ制限: 256 MB
入力: 標準入力
出力: 標準出力
小文字のラテン文字で構成された文字列 s が与えられます。文字列 s に少なくとも2回以上出現する文字がある限り、次のような操作を行います。

  • 文字列 s の中で位置 i の文字が少なくとも2回出現するようなインデックス i (1 \leq i \leq |s|) を選び、位置 i の文字を削除する、即ち、s を s_1 s_2 \dots s_{i-1} s_{i+1} s_{i+2} \dots s_n に置換する

例えば、s= "codeforces"の場合、次のような一連の操作を行うことができます。

  • i = 6 \Rightarrow s= "codefrces"
  • i = 1 \Rightarrow s= "odefrces"
  • i = 7 \Rightarrow s= "odefrcs"

文字列 s が与えられたとき、その文字列のすべての文字がユニーク*2になるような一連の操作を行った後に得られる、辞書順最大の文字列を求めて下さい。

長さ n の文字列 a が長さ m の文字列 b よりも辞書順で小さいのは、以下の場合です。

  • 文字列 a と b の最初の i-1 文字が同じで、文字列 a のi 文字目が文字列 b の i 文字目よりも小さいようなインデックス i (1 \leq i \leq \min(n,\,m)) が存在する場合
  • または文字列 a と b の最初の \min(n,\,m) 文字が同じで、n \lt m である場合

例えば、文字列 a= "aezakmi"は文字列 b= "aezus"よりも辞書順で小さいです。

入力

1行目には単一の整数 t (1 \leq t \leq 10^4) が与えられる。そののち t 個のテストケースが続く。

各テストケースは、小文字のラテン文字からなる文字列 s (1 \leq |s| \leq 2 \cdot 10^5)によって特徴づけられる。

全てのテストケースでの文字列の長さの和が 2 \cdot 10^5 を超えないことは保証されている。

出力

各テストケースについて、文字列の全ての文字がユニークになるような一連の操作を行った後に得られる、辞書順最大の文字列を出力せよ。

入出力例

6
codeforces
aezakmi
abacaba
convexhull
swflldjgpaxs
myneeocktxpqjpz
odfrces
ezakmi
cba
convexhul
wfldjgpaxs
myneocktxqjpz

*1:露[pəlʲɪˈkarp]、ポリカルプ、ポリカープ、Polycarp: 古希Πολύκαρπος/po.lý.kar.pos/、ポリュカルポスに由来する人名

*2:全ての文字が重複しない

Codeforces Round #709 (Div. 2) 問題文和訳

Codeforces 競技プログラミング Codeforces 和訳 Codeforces Div. 2 和訳

A. Prison Break / Побег (500点)

テストごとの時間制限: 1秒
テストごとのメモリ制限: 256 MB
入力: 標準入力
出力: 標準出力
Michaelはソーシャルディスタンスをとるルールに違反し*1、コロナウイルスの拡散の危険性をを生じさせたと告発さています。彼は今、刑務所に送られています。幸いなことに、Michaelは刑務所の内部構造を知っていて、それはとてもシンプルなものです。

刑務所は ab 個のセルに分割される a \times b の長方形として表すことができ、各セルが刑務所の独房を、セル間の辺は独房間の壁を、外側の辺は外壁を表しています。Michaelは判決を受ける前に刑務官の友人に頼んでいくつかの壁(独房間の壁および外壁)に(隠れた)穴をあけてもらうことができます。Michaelは、自分がどの独房に入ったとしても刑務所から出られるようにしたいです。しかし一方で、できるだけ壁を壊さないようにしたいと思っています。

どの独房からも外に出る経路ができるように壊さなければならない壁の最小枚数を求めてください。

入力

1行目には単一の整数 t (1 \leq t \leq 100) が与えられる、これはテストケース数である。

つづく t 行のそれぞれには2つの整数 a,\,b (1 \leq a,\,b \leq 100) が与えられる、これらは対応するテストケースを表している。

出力

各テストケースについて各行に単一の整数を出力せよ、その数とは問題hwの答えである。

入出力例

2
2 2
1 3
4
3

注記

テストケース例で考えられる逃走計画を以下に示します。壊した壁は灰色で、壊されていない壁は黒で表されています。
f:id:Flkanjin:20210322155935p:plain
f:id:Flkanjin:20210322155942p:plain

B. Restore Modulo / Восстановление модуля (1250点)

テストごとの時間制限: 1秒
テストごとのメモリ制限: 256 MB
入力: 標準入力
出力: 標準出力
大会で優勝したЛёша*2は整数配列をたくさん獲得し、それらが非常に高価であると確信しました。授賞式の後、Лёшаはそれらを売ることにしました。配列の市通夜には次のようなルールがあります: 配列を圧縮して生成器にできるときのみ配列を売ることができるというものです。

この生成器は4つの非負数 n,\,m,\,c,\,s を受け取ります。n と m は正でなければならず、s は非負で、c については 0 \leq c \lt m でなければなりません。長さ n の配列 a が以下のルールに従って生成されます。

  • a_1 = s \bmod{m}, ここで x \bmod{y} は x を y で割った余りを表す
  • 1 \lt i \leq n である全ての i について a_i = (a_{i-1} + c) \bmod{m}

例えば、n = 5, m = 7, c = 4, s = 10 とすると、a = [3,\,0,\,4,\,1,\,5] となります。

このような配列の価格は、この生成器の m の値になります。

Лёшаは疑問に思いました、それぞれの配列についてどれだけの金額を得ることができるのだろうかと。全ての配列について、この配列を生成する4数 n,\,m,\,c,\,s が存在するかどうかわかるように手助けしてください。もし存在するならば m を最大化してください。

入力

1行目には単一の整数 t (1 \leq t \leq 100) が与えられる、これは配列の個数である。

配列についての記述の1行目には単一の整数 n (1 \leq n \leq 10^5) が与えられる、これはこの配列のサイズである。

配列についての記述の2行目には n 個の整数 a_1,\,a_2,\,\dots,\,a_n (0 \leq a_i \leq 10^9) が与えられる、これらはこの配列の要素である。

全てのテストケースでの配列サイズの和が 10^5 を超えないことは保証されている。

出力

全ての配列について以下のものを出力せよ。

  • この配列を生成するような4数が存在しない場合; -1
  • m が任意の大きさになる場合: 0
  • その他の場合 m の最大値と適切な c (0 \leq c \lt m)

入出力例

6
6
1 9 17 6 14 3
3
4 2 2
3
7 3 4
3
2 2 4
5
0 1000000000 0 1000000000 0
2
1 1
19 8
-1
-1
-1
2000000000 1000000000
0

C. Basic Diplomacy / Базовая дипломатия (1500点)

テストごとの時間制限: 2秒
テストごとのメモリ制限: 512 MB
入力: 標準入力
出力: 標準出力
Алексей*3には n 人の友人がいます。彼は今休暇中であり、この新しい流行りの協力型ゲームを遊ぶ時間が m 日あります。Алексейはこの m 日のそれぞれに1人ずつチームメイトを必要としています。

各日に何人かの友人はプレイ可能で、その他の友人はプレイができません。毎日Алексейはプレイ可能な友人のうち1人を選んで、プレイすることを申し出ます(勿論、彼等は常に承諾します)。しかし、彼らのうち誰かが \displaystyle \left\lceil \frac{m}{2} \right\rceil 回より厳密に多く選ばれてしまうと、他の全ての友人は気分を害してしまいます。勿論、Алексейは誰かを怒らせてしまいたくありません。

誰も \displaystyle \left\lceil \frac{m}{2} \right\rceil 回よりも厳密に多い回数選ばれないように、彼がチームメイトを選ぶのを手伝ってください。

入力

各テストは複数のテストケースから成る。1行目にはテストケース数 t (1 \leq t \leq 10\,000) が与えられる。テストケースについての記述が続く。

各テストケースの1行目にはそれぞれ友人の人数とプレイ日数を表す2つの整数 n,\,m (1 \leq n,\,m \leq 100\,000) が与えられる。

つづく m 行の i 行目には 1つの整数 k_i (1 \leq k_i \leq n) が与えられ、それに空白区切りの k_i 個の異なる整数 f_{i1},\,\dots,\,f_{ik_i} (1 \leq f_{ij} \leq n) が続く、これらは i 日に目にプレイ可能な友人のインデックスである。

全てのテストケースでの n,\,mの和が(それぞれ) 100\,000 を超えないことは保証されている。全てのテストケースの全ての日での k_i の和が 20\,000 を超えないことは保証されている。

出力

各テストケースについて答えを出力せよ。目標を達成する方法がない場合は"NO"と出力せよ。

そうでない場合、1行目に"YES"と出力し、2行目に空白で区切られた m 個の整数 c_1,\,\dots,\,c_m を出力せよ。各 c_i は i 日目に選ばれた友人を表していなければならない(したがって、f_{ij} の1つでなければならない)。

どの値も \displaystyle \left\lceil \frac{m}{2} \right\rceil 回よりも多く出現してはいけない。複数の答えが存在する場合、そのいずれかを出力せよ。

入出力例

2
4 6
1 1
2 1 2
3 1 2 3
4 1 2 3 4
2 2 3
1 3
2 2
1 1
1 1
YES
1 2 1 1 2 3 
NO

D. Playlist / Плейлист (2000点)

テストごとの時間制限: 2秒
テストごとのメモリ制限: 256 MB
入力: 標準入力
出力: 標準出力
Аркадий*4は初期状態で n 曲からなるプレイリストを持っていて、各曲にはプレイリストに出てくる順に 1 から n までの番号がつけられている。プレイリストは循環しています、即ち、最後の曲を聴いた後、Аркадийは最初から聞き続けます。

各曲には正整数であるジャンル a_i が振られています。Аркадийがジャンル y の曲を聴き終え、その前に聴いていた曲のジャンルを x とします。\gcd(x,\,y) = 1 の場合、最後に聴いていた(ジャンル y の)曲をプレイリストに削除します。その後、削除された曲をスキップし、前に聴いた曲について忘れて、通常通り曲を聴き続けます。言い換えれば、ある曲を削除した後、すぐに次の曲を削除することはできません。

ここで \gcd(x,\,y) は整数 x,\,y の最大公約数(GCD)*5を表します。

例えば、初期状態の曲のジャンルが [5,\,9,\,2,\,10,\,15] であったとすると、プレイリストは次のように変換されます: [\mathbf{5},\,9,\,2,\,10,\,15] \rightarrow [\mathbf{5},\,\mathbf{9},\,2,\,10,\,15] \rightarrow [5,\,2,\,10,\,15] (\gcd(5,\,9) = 1 であるため) \rightarrow [5,\,\mathbf{2},\,10,\,15] \rightarrow [5,\,\mathbf{2},\,\mathbf{10},\,15] \rightarrow [5,\,2,\,\mathbf{10},\,\mathbf{15}] \rightarrow [\mathbf{5},\,2,\,10,\,\mathbf{15}] \rightarrow [\mathbf{5},\,\mathbf{2},\,10,\,15] \rightarrow [5,\,10,\,15] (\gcd(5,\,2) = 1 であるため) \rightarrow [5,\,\mathbf{10},\,15] \rightarrow [5,\,\mathbf{10},\,\mathbf{15}] \rightarrow \dots。太数字は、最後に再生された2つの曲を表しています。曲が削除された後は、Аркадийはその曲と前の曲を聴いたことを忘れてしまうことに注意してください。

初期状態のプレイリストが与えられるので、どの曲が最終的に削除されるか、そして、度の順に削除されるかを判別してください。

入力

各テストは複数のテストケースから成る。1行目にはテストケース数 t (1 \leq t \leq 10\,000) が与えられる。テストケースについての記述が続く。

各テストケースの1行目には単一の整数 n (1 \leq n \leq 10^5) が与えられる、これは曲数である。

各テストケースの2行目には n 個の整数 a_1,\,a_2,\,\dots,\,a_n (1 \leq a_i \leq 10^9) が与えられる、これらは曲のジャンルである。

全てのテストケースでの nの和が 10^5 を超えないことは保証されている。3

出力

各テストケースについて、単一行に出力せよ。まず、単一の整数 k を出力せよ、これは削除された曲数である。そのあと、k 個の異なる整数を出力せよ、これらは削除された順番で削除された曲を表している。

入出力例

5
5
5 9 2 10 15
6
1 2 4 2 4 2
2
1 2
1
1
1
2
2 2 3 
2 2 1 
2 2 1 
1 1 
0

注記

1つ目のテストケースについての説明は問題文中にあります。

2つ目のテストケースではプレイリストは次のように変換されます。[\mathbf{1},\,2,\,4,\,2,\,4,\,2] \rightarrow [\mathbf{1},\,\mathbf{2},\,4,\,2,\,4,\,2] \rightarrow [1,\,4,\,2,\,4,\,2] (\gcd(1,\,2) = 1 であるため) \rightarrow [1,\,\mathbf{4},\,2,\,4,\,2] \rightarrow [1,\,\mathbf{4},\,\mathbf{2},\,4,\,2] \rightarrow [1,\,4,\,\mathbf{2},\,\mathbf{4},\,2] \rightarrow [1,\,4,\,2,\,\mathbf{4},\,\mathbf{2}] \rightarrow [\mathbf{1},\,4,\,2,\,4,\,\mathbf{2}] \rightarrow [4,\,2,\,4,\,2] (\gcd(2,\,1) = 1 であるため) \rightarrow [\mathbf{4},\,2,\,4,\,2] \rightarrow \dots

3つ目のテストケースではプレイリストは次のように変換されます。[\mathbf{1},\,2] \rightarrow [\mathbf{1},\,\mathbf{2}] \rightarrow [1] (\gcd(1,\,2) = 1 であるため) \rightarrow [\mathbf{1}] \rightarrow [\mathbf{1}] (Аркадийは同じ曲を2回続けて聴いた) \rightarrow [\,] (\gcd(1,\,1) = 1 であるため)

4つ目のテストケースでは2曲目を削除した後の3つ目のテストケースと同じです。

5つ目のテストケースでは同じ曲を何度も何度も聴いていますが、\gcd(2,\,2) \neq 1 であるため、削除されません。

E. Skyline Photo / Панорама города (2500点)

テストごとの時間制限: 2.5秒
テストごとのメモリ制限: 256 MB
入力: 標準入力
出力: 標準出力
AliceはNew York市を訪れています。旅行を楽しむため、Aliceは街のスカイライン*6の写真を撮って、その写真の集合をプレゼントとしてBobに上げたいと思っています。しかし、彼女は最大の美しさを持つ写真の集合を求めたいので、貴方の助けを必要としています。

街には n 個のビルがあり、i 番目のビルの高さは正の値 h_i です。街にある n 個の全てのビルの高さは異なります。さらに、それぞれのビルの美しさは b_i です。街には醜い建物もあるので、美しさは正にも負にもなりえることに注意してください。

写真の集合はスカイライン上のビルを撮影した1枚以上の写真から成ります。各写真は連続インデックス区間を形成する1つ以上のスカイライン上のビルが含まれます。各ビルはちょうど1枚の写真に写っていなければなりません。つまり、どの写真にも写っていないビルがあったり、複数の写真に写っているビルが存在する場合、その写真の集合は有効ではないという訳です。

写真の美しさは、写っている最も短いビルの美しさ b_i に等しいです。写真の集合の美しさの合計は、その写真に含まれる全ての写真の美しさの合計です。有効な写真の集合が持つ最大の美しさを求めるAliceの手伝いをしてください。

入力

1行目には単一の整数 n (1 \leq n \leq 3 \cdot 10^5) が与えられる、これはスカイライン上のビルの数である。

2行目には n 個の異なる整数 h_1,\,h_2,\,\dots,\,h_n (1 \leq h_i \leq n) が与えられる。i 番目の数は建物 i の高さを表す。

3行目には n 個の異なる整数 b_1,\,b_2,\,\dots,\,b_n (-10^9 \leq b_i \leq 10^9) が与えられる。i 番目の数は建物 i の美しさを表す。

出力

有効なスカイラインの写真の集合についてAliceが達成できる最大の美しさを表す1つの数値を出力せよ。

入出力例

5
1 2 3 5 4
1 5 3 2 4
15
5
1 4 3 2 5
-3 4 -10 2 7
10
2
2 1
-2 -3
-3
10
4 7 3 2 5 1 9 10 6 8
-4 40 -46 -8 -16 4 -10 41 12 3
96

注記

1つ目の入出力例では、Aliceは5枚の写真を撮り、それぞれに1つのビルを写すことで最大の美しさを得ることができます。

2つ目の入出力例では、Aliceは4枚の写真を撮ることで、最大の美しさ 10 を達成することができます。1つのビルを写したビル1,\,2,\,5 の3枚の写真のそれぞれの美しさ -3,\,4,\,7 で、もう1枚の写真はビル3,\,と4 を写し、美しさ 2 です。

3つ目の入出力例では、Aliceは街全体の写真を1枚だけ撮ります。

4つ目の入出力例では、Aliceは最大の美しさを得るために、1つのビルを写したビル 1,\,2,\,8,\,9,\,10 の写真と、ビル 3,\,4,\,5,\,6,\,7 を写した1枚の写真を撮ります。

F. Useful Edges / Полезные рёбра (2750点)

テストごとの時間制限: 5秒
テストごとのメモリ制限:512 MB
入力: 標準入力
出力: 標準出力
n 頂点の重み附き無向グラフと q 個の三つ組 (u,\,v,\,l) が与えられます、ここで各三つ組の u と v は頂点で l は正整数です。以下の条件を満たすような少なくとも1つの三つ組 (u,\,v,\,l) と経路(必ずしも単純ではない)が存在する場合、辺 e は有用といいます。

  • u と v がこの経路の端点である
  • e はこの経路の辺の1つである
  • この経路の全ての辺の重さの合計が l を超えない

このグラフ上の有用な辺の数を出力してください。

入力

1行目には2つの整数 n,\,m \biggl(2 \leq n \leq 600, \displaystyle 0 \leq m \leq \frac{n(n-1)}{2} \biggr) が与えられる。

つづく m 行の各行には3つの整数 u,\,v,\,w (1 \leq u,\,v \leq n, u \neq v, 1 \leq w \leq 10^9) が与えられる、これらは u と v を結ぶ重さ w の辺を表す。

次の行には唯一の整数 q \left(\displaystyle 1 \leq q \leq \frac{n(n-1)}{2} \right) が与えられる、これは三つ組の個数である。

つづく q 行の各行には 三つ組 (u,\,v,\,l) を表す3つの整数 u,\,v,\,l (1 \leq u,\,v \leq n, u \neq v, 1 \leq l \leq 10^9) が与えられる。

次のことは保証されている。

  • グラフにはループや多重辺は含まれない
  • 三つ組内の全ての組 (u,\,v) は異なる

出力

グラフ内の有用な辺の数を表す単一の整数を出力せよ。

入出力例

4 6
1 2 1
2 3 1
3 4 1
1 3 3
2 4 3
1 4 5
1
1 4 4
5
4 2
1 2 10
3 4 10
6
1 2 11
1 3 11
1 4 11
2 3 11
2 4 11
3 4 9
1
3 2
1 2 1
2 3 2
1
1 2 5
2

注記

1つめの入出力例では重み 5 のものを除いてすべての辺が有用です。

2つ目の入出力例では、1 と 2 の間の辺は、経路 1-2 に属し、10 \leq 11 であるため、唯一有用です。一方で、3 と 4 の間の辺は、有用ではありません。

3つ目の入出力例では、長さがちょうど 5 の経路 1-2-3-2 が存在するので、両方の辺が有効です。経路が1つの頂点を2回以上通過することがあることに注意してください。

*1:ロシア語版ではマスクをせず

*2:Леша 露[ˈlʲɵʂə] (Ljosha): Алексе́й [ɐlʲɪkˈsʲej] の愛称、Alexanderなどと同語源 英語版ではAlex

*3:露[ɐlʲɪkˈsʲej] Aleksej, Aleksey, Alexey

*4:露[ɐrˈkadʲɪ] Arkadij, Arkady

*5:原文では英語、ロシア語のWikipediaへのリンク

*6:空を背景とした高層建築物や山岳が描く輪郭線の事

AtCoder Beginner Contest 196のきろく

AtCoder 競技プログラミング AtCoder Beginner Contest 参戦記

AtCoder Beginner Contest 196に参加。レートが1700以上に回復しました。

A - Difference Max (100点)

x - y は x について狭義単調増加、y について狭義単調減少であるため、x = b, y = c のとき x - y は最大値をとります。

B - Round Down (200点)

文字列として'.'が出てくるまで1文字ずつ出力すればOKです。
'.'が存在しなければ元から整数なのでそのまま出力します。

C - Doubled (300点)

1 ≤ N < 10^{12} より全探索では間に合いません。ただし、N 以下で問題文の条件を満たすものは繰り返し文字列が高々 10^6 - 1 より、条件を満たすものを小さいものから順に N より大きくなるまで個数をカウントすれば答えが出ます。

また、公式解説 にある O(1) の解法として、次のように繰り返す整数の数を求める方法が考えられます。
N の桁数を d とします。
d が奇数の時は 1 から \underbrace{99\dots99}_{\frac{d - 1}{2}\ 桁} までの \displaystyle 10^{\frac{d - 1}{2}} - 1 個の整数が条件を満たす数を生成します。
d が偶数の時は N の前半部 n_1 と後半部 n_2 について、n_1 \leq n_2 のとき 1 から n_1 までの n_1 通り、n_1 \gt n_2 のとき 1 から n_1 - 1 までの n_1 - 1 通りです。

D - Hanjo (400点)

公式解説のように全ての敷き詰め方をDFSで確かめる方法がありますが、少し別の方法を用いました。
重なりやはみ出ることを無視すると長方形の畳の配置方法は各畳の左上の位置とどちら向きに置くかの 2^A {}_{HW}\mathrm{C}_{A} 通りで、このうち、重なりやはみ出しのないものが条件を満たす敷き詰め方です。ここで各畳の左上の位置の {}_{HW}\mathrm{C}_{A} 通りの列挙についてある状態から次の状態へ O(1) で遷移できるならば O(2^A {}_{HW}\mathrm{C}_{A} HW) で答えを求めることができます。

集合 \{0,\,1,\,\dots,\,n-1\} の大きさ k の部分集合の列挙は蟻本にある通り以下のようにして処理をすることができます。

int bit = (1 << k) - 1;
while(bit < (1 << n)){
    // 各集合についての処理をここに書く
    int x = bit & -bit, y = bit + x;
    bit = (((bit & ~y) / x) >> 1) | y;
}

この問題のコードを書くのに少し時間がかかってしまい、EやF問題に避ける時間が少なくなってしまいました。

またこっちの解法では長方形の畳が存在しない A = 0 のケースがコーナーとなってしまうことに注意しましょう(1敗)。

E - Filters (500点)

途中で \max がある場合、定義域のうちある値以上については像の上限に、 \min がある場合は定義域のうちある値以下については像の下限となるため、このような上下限に挟まれる範囲を「有意な範囲」と呼ぶことにします。このとき、函数 f_i(x) についての有意な範囲と像の幅は等しくなります。

f_0(x) = {\mathrm{id}}_{\mathbb{R}}(x) = x とし、i \leq j について (f_i \circ f_{i-1} \circ \dots \circ f_1 \circ f_0)(x) の像を [c_i,\,d_i], 有意な範囲を [c_i - s_i,\,d_i - s_i] とします。

\begin{align} (f_i \circ f_{i-1} \circ \dots \circ f_1 \circ f_0)(x) &= \left\{ \begin{array}{ll} c_i & (x \lt c_i - s_i)\\ x + s_i & (c_i \leq x \leq d_i)\\ d_i & (x \gt d_i - s_i) \end{array} \right\}\\ &= \max\{\min\{x + s_i,\,d_i\},\,c_i\} \end{align}
となるので c_N, d_N, s_N を求めればいいことが分かります。

f_0 については恒等写像であるため始域、有意な範囲、像が全て一致し、c_0 = -10^9, d_0 = 10^9, s_0 = 0 となります。

i - 1 (1 \leq i \leq N) 番目まで求まっていたとき、i 番目のそれぞれの値を求めましょう。このとき f_i(x) の始域は [c_{i-1},\,d_{i-1}] とみなすことができます。

$ t_i = 1 $ のとき

f_i(x) = x + a_i のため、有意な範囲は変化せず、像は [c_{i-1} + a_i,\,d_{i-1}+ a_i] です。よって、c_i = c_{i - 1} + a_i, d_i = d_{i - 1} + a_i, s_i = s_{i - 1} + a_i となります。

$ t_i = 2 $ のとき

f_i(x) = \max\{x,\,a_i\} で、像は [\max\{c_{i-1},\,a_i\},\,\max\{d_{i-1},\,a_i\}] となるためc_i = \max\{c_{i-1}, a_i\}, d_i = \max\{d_{i-1}, a_i\}, s_i = s_{i-1} となります。また、f_i の有意な範囲は像と等しくなり、全体の有意な範囲は [\max\{c_{i-1},\,a_i\} - s_{i-1},\,\max\{d_{i-1},\,a_i\} - s_{i-1}] となります。

$ t_i = 3 $ のとき

f_i(x) = \min\{x,\,a_i\} で、像は [\min\{c_{i-1},\,a_i\},\,\min\{d_{i-1},\,a_i\}] となるためc_i = \min\{c_{i-1}, a_i\}, d_i = \min\{d_{i-1}, a_i\}, s_i = s_{i-1} となります。また、f_i の有意な範囲は像と等しくなり、全体の有意な範囲は [\min\{c_{i-1},\,a_i\} - s_{i-1},\,\min\{d_{i-1},\,a_i\} - s_{i-1}] となります。

F - Substring 2 (600点、実行時間制限: 3 sec)

コンテスト中には解けませんでした...
文字列ですが整数列して扱います。答えは \displaystyle \min_{0 \leq i \leq |S| - |T|} \sum_{j = 1}^{|T|} (S_{i + j} \oplus T_j) となります(\oplusはXOR演算です)。T を反転させた配列を T' とすると、 \displaystyle \sum_{j = 1}^{|T|} (S_{i + j} \oplus T_j) = \sum_{j = 1}^{|T|} (S_{i + j} \oplus {T'}_{|T| - 1 - j}) となるので畳み込み\displaystyle \left( c_i = \sum_{j = 0}^{i} a_j b_{i-j} \right)のような式になるので、どうにかして積の和に変換できるとAC-Libararyのconvolutionが利用できるので、そのようにできるかを考えます。

x \oplus y はどちらか一方のみが 1 のとき、1 となり、そうでない場合 0 となるので x(1-y) + (1-x)y と表すことができます。これで変換できたので、実装することができました。

結果、感想

f:id:Flkanjin:20210321172142p:plain
1700を下回っていたのが、それを1700以上に戻せたので、よかったなと思っていますが、D問題をもっと早く解けたらな、と思いました。
因みにF問題の(1)は少し改善したE問題用のコードを間違えてFに提出した結果です(オイ)。

Educational Codeforces Round 106 問題文和訳

Codeforces 競技プログラミング Codeforces 和訳 Educational Codeforces Round 和訳

A. Domino on Windowsill / Домино на подоконнике

テストごとの時間制限: 1秒
テストごとのメモリ制限: 256 MB
入力: 標準入力
出力: 標準出力
2 \times n のセルからなる格子で表される盤面があります。

1行目の最初の k_1 セルと2行目の最初の k_2 セルが白で塗られています。その他のセルは黒で塗られています。

w 枚の白いドミノ(2 \times 1 タイルで、両方のセルが白で着色されている)と b 枚の黒いドミノ(2 \times 1 タイルで、両方のセルが黒で着色されている)があります。

白いドミノは盤面のその下の2つのセルに他のドミノが置かれておらず、両方のセルが白である場合、盤面に置くことができます。同様に、黒いドミノはその下の2つのセルに他のドミノが置かれておらず、両方のセルが黒である場合、盤面に置くことができます。

ドミノを縦にも横にも置くことができるとすれば、w + b 枚のドミノを全て置くことができるでしょうか?

入力

1行目には単一の整数 t (1 \leq t \leq 3000) が与えられる、これはテストケースの個数である。

各テストケースの1行目には3つの整数 n,\,k_1,\,k_2 (1 \leq n \leq 1000; 0 \leq k_1,\,k_2 \leq n) が与えられる。

各テストケースの1行目には2つの整数 w,\,b (0 \leq w,\,b \leq n) が与えられる。

出力

各テストケースについて、w + b 個のドミノを全て盤面に置くことができればYESと、そうでなければNOと出力せよ。

各文字について大文字で出力しても小文字で出力してもよい(それゆえ、例えば、文字列yEs, yes, Yes, YES は全て肯定の答えとして認識される)。

入出力例

5
1 0 1
1 0
1 1 1
0 0
3 0 0
1 3
4 3 1
2 2
5 4 3
3 1
NO
YES
NO
YES
YES

注記

1つ目のテストケースでは n = 1, k_1 = 0, k_2 = 0 です。これは 2 \times 1 の盤面には黒のセル (1,\,1) と白のセル (2,\,1) があることを表します。白いセルが1つしかないので、白いドミノを置くことができません。

2つ目のテストケースでは同じ大きさ 2 \times 1 の盤面ですがどちらのセルも白です。 w = 0, b = 0 なので 0 + 0 = 0 枚のドミノを置くことができます。

3つ目のテストケースでは盤面は 2 \times 3 ですが、全て黒で塗られている(k_1 = k_2 = 0 であるため)ので、白いドミノを置くことができません。

4つ目のテストケースではセル (1,\,1), (1,\,2), (1,\,3), (2,\,1) が白で、そのほかのセルは黒です。2 枚の白いドミノを位置 ( (1,\,1),\,(2,\,1) ) と ( (1,\,2),\,(1,\,3) ) に、2 枚の黒いドミノを位置 ( (1,\,4),\,(2,\,4) ) と ( (2,\,2),\,(2,\,3) ) に置くことができます。

B. Binary Removals / Двоичные удаления

テストごとの時間制限: 2秒
テストごとのメモリ制限: 256 MB
入力: 標準入力
出力: 標準出力
文字'0'と'1'のみから成る文字列 s が与えられます。s の長さを |s| とします。

ある整数 k (k \gt 0) を選び、次のような長さ k の数列 a を求めて下さい。

  • 1 \leq a_1 \lt a_2 \lt \cdots \lt a_k \leq |s|
  • 2 から k までの全ての i について a_{i-1} + 1 \lt a_i

位置 a_1,\,a_2,\,\dots,\,a_k の文字は削除され、残りの文字を順序を変えずに連結します。つまり、配列 a の位置が隣接してはいけません。

この結果得られる文字列を s' とします。2 から |s'| の全ての i について s'_{i-1} \leq s'_i であるとき s' はソートされているといいます。

得られる文字列 s' がソートされているような配列 a は存在するでしょうか?

入力

1行目には単一の整数 t (1 \leq t \leq 1000) が与えられる、これはテストケースの個数である。

その後、t 個のテストケースについての記述が続く。

各テストケースについての唯一の行には文字列 s (2 \leq |s| \leq 100) が与えられる。各文字は'0'か'1'のいずれかである。

出力

各テストケースについて位置 a_1,\,a_2,\,\dots,\,a_k の文字を取り除き、順番を変えずに連結することで、ソートされている文字列が得られるような配列 a が存在する場合、"YES"と出力せよ。

そうでない場合、"NO"と出力せよ。

各文字について大文字で出力しても小文字で出力してもよい(それゆえ、例えば、文字列yEs, yes, Yes, YES は全て肯定の答えとして認識される)。

入出力例

5
10101011011
0000
11111
110
1100
YES
YES
YES
YES
NO

注記

1つ目のテストケースでは列 a = [1,\,3,\,6,\,9] を選ぶことができます。"10101011011"から下線附きの文字を取り除くと文字列"0011111"ができ、これはソートされています。

2つ目と3つ目のテストケースでは列は既にソートされています。

4つ目のテストケースでは列 a = [3] を選ぶことができます。s' = "11"となり、これはソートされています。

5つ目のテストケースでは s' がソートされているような列 a を選ぶ方法はありません。

C. Minimum Grid Path / Минимальный путь на поле

テストごとの時間制限: 2秒
テストごとのメモリ制限: 256 MB
入力: 標準入力
出力: 標準出力
XY-平面の点 (0,\,0) に立っていて、点 (n,\,n) に行きたいと思っています。

2方向にしか動くことができません。

  • 右方向: 水平方向で、x 座標が大きくなる方向
  • 上方向: 垂直方向で、y 座標が大きくなる方向

つまり、経路は次のような構造になっています。

  • 最初、右に行くか上に行くかを選択する
  • 次に、選択した方向にある正整数の距離だけ進む(距離は独立して選ぶことができる)
  • その後、方向を変えて(右から上、もしくは上から右)、このプロセスを繰り返す

方向転換を何度もしたくないので、 n - 1 回よりも多く方向転換はしません。

結果として、経路は、各線分が正整数の長さを持ち、垂直線分と水平線分が交互に出てくる高々 n 本の線分から成る (0,\,0) から (n,\,n) までの折れ線の鎖となります。

全ての経路が等価であるというわけではありません。n 個の整数 c_1,\,c_2,\,\dots,\,c_n があり、ここで c_i は i 番目の成分のコストを表します。

これらのコストを用いて、経路のコストをその経路の線分の長さとコストの積の和として定義できます、すなわち、経路が k 本の線分 (k \leq n) から成る場合、経路のコストは \displaystyle \sum\limits_{i=1}^{k}{c_i \cdot length_i} (線分は 1 から k まで経路の順に番号が振られている)となります。

最小コストの経路を求め、そのコストを出力してください。

入力

1行目には単一の整数 t (1 \leq t \leq 1000) が与えられる、これはテストケースの個数である。

各テストケースの1行目には単一の整数 n (2 \leq n \leq 10^5) が与えられる。

各テストケースの2行目には n 個の整数 c_1,\,c_2,\,\dots,\,c_n (1 \leq c_i \leq 10^9) が与えられる、これらは各線分のコストである。

全てのテストケースでの n の和が 10^5 を超えないことは保証されている。

出力

各テストケースについて、高々 n 本の交互に並ぶ線分から成る (0,\,0) から (n,\,n) までの経路の可能な最小コストを出力せよ。

入出力例

3
2
13 88
3
2 3 1
5
4 3 2 1 4
202
13
19

注記

1つ目のテストケースでは、(2,\,2) に到達するためには少なくとも1回は曲がらなければならないので経路はちょうど 2 本の線分から構成されます: 長さ 2 の水平線分と長さ 2 の垂直線分です。経路のコストは 2 \cdot c_1 + 2 \cdot c_2 = 26 + 176 = 202 となります。

2つ目のテストケースでは、最適経路の1つが 3 本の線分から構成されています: 長さ 1 の1本目と長さ 3 の2本目、長さ 2 の3本目です。

この経路のコストは 1 \cdot 2 + 3 \cdot 3 + 2 \cdot 1 = 13 です。

3つ目のテストケースでは、最適経路の1つが 4 本の線分から構成されています: 長さ 1 の1本目と長さ 1 の2本目、長さ 4 の3本目、長さ 4 の4本目です。この経路のコストは 1 \cdot 4 + 1 \cdot 3 + 4 \cdot 2 + 4 \cdot 1 = 19 です。

D. The Number of Pairs / Количество пар

テストごとの時間制限: 2秒
テストごとのメモリ制限: 512 MB
入力: 標準入力
出力: 標準出力
3つの正の(0より大きい)整数 c,\,d,\,x が与えられます。

等式 c \cdot lcm(a,\,b) - d \cdot gcd(a,\,b) = x が成り立つような正整数の組 (a,\,b) の個数を求めなければなりません。ここで lcm(a,\,b) は a,\,b の最小公倍数で、gcd(a,\,b) は a,\,b の最大公約数です。

入力

1行目には1つの整数 t (1 \leq t \leq 10^4) が与えられる、これはテストケースの個数である。

各テストケースは1行からなり、3つの整数 c,\,d,\,x (1 \leq c,\,d,\,x \leq 10^7) が与えられる。

出力

各テストケースについて1つの整数を出力せよ、その数とは上記の等式を満たす組 (a,\,b) の個数である。

入出力例

4
1 1 3
4 2 6
3 3 7
2 7 25
4
3
0
8

注記

1つ目の入出力例では、正しい組は (1,\,4), (4,\,1), (3,\,6), (6,\,3) です。

2つ目の入出力例では、正しい組は (1,\,2), (2,\,1), (3,\,3) です。

E. Chaotic Merge / Хаотичное слияние

テストごとの時間制限: 2秒
テストごとのメモリ制限: 256 MB
入力: 標準入力
出力: 標準出力
小文字のラテン文字のみで構成された2つの文字列 x,\,y が与えられます。|s| を文字列 s の長さとします。

列 a をちょうど |x| 個の0とちょうど |y| 個の1がある順序で構成してる場合、それをマージ列を言います。

マージ z は次のルールによって列 a から生成されます。

  • a_i = 0 のとき、x の先頭から文字を削除し、z の末尾に追加する
  • a_i = 1 のとき、y の先頭から文字を削除し、z の末尾に追加する

a_i \neq b_i となるような位置 i がある場合、2つのマージ列 a,\,b は異なります。

2 から |z| までの全ての i について z_{i-1} \neq z_i であるばあい、文字列 z をカオスであるといいます。

ある 1 \leq l \leq r \leq |s| について s[l,\,r] を、位置 l で始まり、位置 r で終わる s の連続した文字の部分列とします。

f(l_1,\,r_1,\,l_2,\,r_2) を x[l_1,\,r_1] と y[l_2,\,r_2] のカオスなマージを生成する異なるマージ列の数とします。x と y の空でない部分文字列のみを考慮することに注意してください。

\displaystyle \sum \limits_{1 \leq l_1 \leq r_1 \leq |x| \\ 1 \leq l_2 \leq r_2 \leq |y|} f(l_1,\,r_1,\,l_2,\,r_2) を計算してください。答えはmodulo 998\,244\,353 で出力してください。

入力

1行目には文字列 x (1 \leq |x| \leq 1000) が与えられる。

2行目には文字列 y (1 \leq |y| \leq 1000) が与えられる。

何方の文字列も小文字のラテン文字のみで構成される。

出力

単一の整数を出力せよ、その数は 1 \leq l_1 \leq r_1 \leq |x| かつ 1 \leq l_2 \leq r_2 \leq |y| での f(l_1,\,r_1,\,l_2,\,r_2) の和 modulo 998\,244\,353 である。

入出力例

aaa
bb
24
code
forces
1574
aaaaa
aaa
0
justamassivetesttocheck
howwellyouhandlemodulooperations
667387032

注記

1つ目の入出力例では次のようになります。

  • 6 組の部分文字列"a"と"b"の組について、それぞれ"01"と"10"が有効なマージ列となる
  • 3 組の部分文字列"a"と"bb"の組について、それぞれ"101"が有効なマージ列となる
  • 4 組の部分文字列"aa"と"b"の組について、それぞれ"010"が有効なマージ列となる
  • 2 組の部分文字列"aa"と"bb"の組について、それぞれ"0101"と"1010"が有効なマージ列となる
  • 2 組の部分文字列"aaa"と"b"の組について、それぞれ有効なマージ列はない
  • 1 組の部分文字列"aaa"と"bb"の組について、それぞれ"01010"が有効なマージ列となる

従って、答えは 6 \cdot 2 + 3 \cdot 1 + 4 \cdot 1 + 2 \cdot 2 + 2 \cdot 0 + 1 \cdot 1 = 24 となる。

F. Diameter Cuts / Разрезы диаметров

テストごとの時間制限: 2秒
テストごとのメモリ制限: 256 MB
入力: 標準入力
出力: 標準出力
整数 k と n 頂点から成る無向木が与えられます。

ある頂点組間の単純経路(各頂点が高々1回しか現れない経路)の長さは、その経路の辺の数です。木の直径はその木の全ての頂点組間の単純経路の最大長です。

木から辺を1集合分取り除こうとしています。辺が削除されると気は複数の小さな気に分裂します。結果として得られる全ての木の直径が全て k 以下であれば、辺の集合は有効です。

2つの辺の集合は一方にしか現れないような辺がある場合、異なります。

有効な辺の集合の数 modulo 998\,244\,353 を数えてください。

入力

1行目には2つの整数 n,\,k (2 \leq n \leq 5000, 0 \leq k \leq n-1) が与えられる、それぞれ木の頂点数と最大許容直径である。

つづく n-1 行のそれぞれには辺の記述が与えらえる: 2つの整数 v,\,u (1 \leq v,\,u \leq n, v \neq u)。

与えられた辺は木を形成する。

出力

単一の整数を出力せよ、その数は有効な辺の集合の数 modulo 998\,244\,353 である。

入出力例

4 3
1 2
1 3
1 4
8
2 0
1 2
1
6 2
1 6
2 4
2 6
3 6
5 6
25
6 3
1 2
1 5
2 3
3 4
5 6
29

注記

1つ目の入出力例では、与えられた木の直径は既に k 以下です。したがって削除する辺の集合を任意に選べ、結果として得られる木の直径は k 以下です。集合は空のものも含め 2^3 個あります。

2つ目の入出力例では、唯一の辺を削除しなければなりませんうでなければ、直径が 1 となり、0 よりも大きくなります。

3つ目と4つ目の入出力例の木はこちらです。
f:id:Flkanjin:20210319152538p:plain

G. Graph Coloring / Раскраска графа

テストごとの時間制限: 7秒
テストごとのメモリ制限: 1024 MB
入力: 標準入力
出力: 標準出力
第1部の n_1 頂点、第2部の n_2 頂点、1 から m の番号が附いた m 本の辺からなる二分グラフが与えられます。各辺を赤と青のうちいずれかの1色で塗らなければなりません。次の値 \displaystyle \sum_{v \in V} |r(v) - b(v)| を最小化しなければなりません、ここで、V はグラフの頂点の集合で、r(v) は v についている赤い辺の本数で、b(v) は v についている青い辺の本数です。

古典的で簡単そうな響きでしょう? さて、次の形式の q 個のクエリを処理しなければなりません。

  • 1\ v_1\ v_2 — 第1部の頂点 v_1 と第2部の頂点 v_2 を結ぶ新しい辺を追加する。この辺は次のように新しいインデックスを取得する: 最初に追加された辺はインデックス m + 1, で2番目は m + 2 等々という感じである。辺の追加後、現在の最適彩色のハッシュを出力しなければならない(最適彩色が複数存在する場合、そのいずれかのハッシュを出力する)。実際には、このハッシュは確認されず、このクエリへの答えとして任意の数を出力することができるが、このハッシュを持つ彩色を出力するように求められることがある。
  • 2 — 前のクエリを処理したのと同じハッシュのグラフの最適彩色を出力します。このタイプのクエリはタイプ1のクエリの後にしか来ず、高々 10 回までしか来ない。このハッシュに対応する最適彩色が複数ある場合、そのうちのいずれかを出力せよ。

ある彩色で辺が赤や青だったとしても次の彩色ではその色が変わるかもしれません。

彩色のハッシュは次のように計算されます: R を赤い辺のインデックスの集合とした時ハッシュは \displaystyle \left( \sum_{i \in R} 2^i \right) \bmod 998244353 となります。

この問題はonlineで解かなければならないことに注意してください。つまり、入力全体を一度に読むことができないということです。最後のクエリの応答が出力されてから初めて各クエリを読むことができます。プログラム内で各出力ののち、C++ではfflush、JavaではBufferedWriter.flushという関数を用いてください。

入力

1行目には3つの整数 n_1,\,n_2,\,m (1 \leq n_1,\,n_2,\,m \leq 2 \cdot 10^5) が与えられる。

その後、m 行が続き、その i 行目には2つの整数 x_i,\,y_i (1 \leq x_i \leq n_1: 1 \leq y_i \leq n_2) が与えられる、これは i 番目の辺が第1部の頂点 x_i と第2部の頂点 y_i をと結んでいることを表す。

次の行には1つの整数 q (1 \leq q \leq 2 \cdot 10^5) が与えられる、これは処理しなければならないクエリの数である。

つづく q 行には問題文に記載されている形式のクエリが与えられる；

入力の追加制約:

  • どの時点においてもグラフ多重辺を持たない
  • タイプ 2 のクエリは前のクエリがタイプ 1 のクエリであるときにしか来ない
  • タイプ 2 のクエリは最大 10 個である

出力

タイプ 1 に答えるためには1つの整数を出力せよ、その数は最適彩色のハッシュである。

タイプ 2 に答えるためには1行を出力せよ。これは整数 k で始まっていなければならない、この数は赤い辺の本数である。そののち、k 個の異なる整数が続く、これらは彩色における赤い辺のインデックスで、順番は問わない。各インデックスは既存辺に対応してなければならず、生成する彩色のハッシュは1つ前の1つ前のクエリの答えとして出力したハッシュと同じでなければならない。

クエリに対する答えが複数ある場合、そのいずれかを出力せよ。

入出力例

3 4 2
1 2
3 4
10
1 1 3
1 2 3
2
1 3 3
2
1 2 4
2
1 2 1
1 1 1
2
8
8
1 3
40
2 3 5
104
3 5 6 3
104
360
4 5 6 3 8