EPIC Institute of Technology Round Summer 2025 (Codeforces Round 1036)

A. Deranged Deletions

$a$ が昇順なら達成不可能.昇順でないならその $2$ 要素だけを残すと条件を満たします.

B. Minimise Sum

$a_1\geq a_2$ のとき $(a_1+a_2,0,a_3,a_4,\ldots)$ を作ることでスコア $a_1+a_2$ を達成可能です.$a_1,a_2$ のうち少なくともひとつを減らす操作が $(i,j)=(1,2)$ しかないことからこれ以外の操作ではスコアが $a_1+a_2$ 以上になります.よってこの場合は解けました.

$a_1\leq a_2$ とします.$n=2$ ならばスコアは $a_1+a_2$ です.$n\geq 3$ のときは $(a_1,a_2+a_3,0,a_4,\ldots)$ を作ることでスコアを $2a_2$ にできます.$a_1,a_2$ の一方を減らす操作が $i=1,j=2$ しかないことからこれより小さいスコアは実現不可能だとわかります.

C. Subset Multiplication

$b_i\nmid b_{i+1}$ のところで列を切り分けて,subarray $[l_j,r_j] (1\leq j\leq m)$ に分割します.$m=1$ ならば明らかなので以下 $m\geq 2$ とします.

$x$ を固定したときの判定について考えると,次の必要条件があります.

  • 各 $j$ ($1\leq j\leq m-1$)について $b_{r_j}/x\mid b_{l_{j+1}}$
  • 各 $j$ ($2\leq j\leq m-1$) について,ある $k \in [l_j,r_j)$ が存在して,$b_k\mid b_{k+1}/x$
  • すべての $k\in [l_1,r_1]$ について $x\mid b_k$ である,または,ある $k\in[l_1,r_1)$ が存在して $b_{k}\mid b_{k+1}/x$ である.

ひとつめの必要条件は,subarray の境界部分では左の要素が $x$ 倍されていて,右の要素は $a_i$ のままであることから分かります.ふたつめの条件は,各 subarray の中で先頭の項はもとのまま,末尾の項は $x$ 倍されているので,このどこかに「もとのまま」「$x$ 倍されている」の境界が少なくともひとつ存在することから分かります.

これらは十分条件にもなります.$2, 3$ 番目の条件から各 subarray の適当な後半を $x$ 倍された要素ということにして,$j=m$ に対応する subarray はすべてもとのままということにすればよいです.

まずひとつめの条件について処理すると,ある $c$ が存在して「$x$ は $c$ の倍数」という条件に言い換えられます(境界ごとの $c$ の最小公倍数).そして後半 $2$ つの条件は,$x$ を倍数に置き換えるほど成り立ちにくくなるので,解が存在するならば $x=c$ としても解が存在します.

この問題では解の存在が保証されているため,ひとつめの必要条件だけから $c$ を求めてそれを出力すればよいです.

D. Make a Palindrome

操作では,列全体において昇順 $k$ 番目以降であるものを自由に削除できます.$k$ 番目より後ろであるならば,$[l,r]$ を縮めていくとどこかでちょうど $k$ 番目になります.

列全体を昇順ソートしたときの $k$ 番目を $c$ とします.すると,

  • $c$ より大きいものは自由に削除可能
  • $c$ 未満であるものは削除不可能
  • ちょうど $c$ であるものは,$c$ 以下の要素の個数が $k$ 未満にならない範囲で削除可能

となります.回文を作るうえで,$c$ より大きいものはすべて削除してしまってよいことも分かります.

あとは両端から貪欲します.両端の文字が同じ文字ならば残すとしてよいです.不一致な場合,削除可能なものがあれば削除,そうでなければ詰みです.これを最後まで実行できて,削除した要素数が適切な範囲におさまっていれば YES になります.

E. Make it Zero

全体の総和が奇数だと NO です.

過半数の要素があると NO です.(ある要素を $x$ 減らしたとき,総和は $2x$ 以下しか減らないため).

これらの必要条件のもと,必ず $2$ 回で達成可能です.$b_1+\cdots+b_{i-1}, b_{i+1}+\cdots+b_n$ がともに半分以下であるような $i$ をとって,$[1,i-1],[i,n]$ および $[1,i],[i+1,n]$ に操作すればよいです.これが可能なのは,例えば $[1,i-1]$ および $[i+1,n]$ 部分をまとめて $3$ 要素の列の場合に帰着して証明できます.

$1$ 回で達成可能かを判定し,不可能ならば上述の $2$ 回が最小回数です.

F2. Appending Permutations (Hard Version)

以下インデックスも値も 0-based index です.$0\leq a<b$ に対して $S(a,b)$ とは $[a,\ldots,b-1,0,\ldots,a-1]$ のこととします.

まず重複なく数える方法を考えます.そのために列に対する構築方法を一意にすることを考えます.

[0,1,2,3][4,5,0,1,2,3] は [0,1,2,3,4,5],[0,1,2,3] にできます.このような置換を考えることで,「$S(0,a)$ のあとには $S(a,*)$ を置けない」という制約をつけます.

これで列の構築方法が一意になることが分かります(手前から順に決まっていく).これを適当な dp にすれば F1 が解けます.私のソースコードでは $DP[i]$ は $[0,i)$ 部分までを作る方法,$dp[i][j]$ はそのうち最後が $S(0,j)$ であるものです.

F2 について考えます.$i$ から $S(0,a)$ を使うタイプの遷移はすべての $i,a$ について行います $O(N^2)$ 通り.これで $dp[i][j]$ のタイプの計算は大丈夫です.

$a>0$ のとき,$DP[i]$ から $DP[i+b]$ への $(a,b)$ を使うタイプの遷移可能条件はどのようになっているかというと,

  • $0\leq k<b-a$ について $(i+k,a+k)$ は禁止条件ではない.
  • $1\leq k\leq a$ について $(i+b-k,a-k)$ は禁止条件ではない.

です.ひとつめの条件では単に,$b$ として使える区間の上限が指定されます.ふたつめの条件は $(i+b,a)$ を与えると判定できる($i,b$ にはよらない)ことに注意します.

$(i,a)$ に対してひとつめの条件から $i+b$ として可能は区間を求めて,適当な $(i+b,a)$ のところへの区間加算をしておきます.区間加算された値を $DP[i+b]$ に反映するかどうかは,値を受け取ったときに判定するようにします.

これで $O(N^2)$ 時間になります.必要な前計算として,$(i,j)$ について,$(i+k,j+k)$ や $(i-k,j-k)$ の形の禁止条件がある最小の $k$ などを持てばよいです.あるいはそこをに何らかの $\log$ をつけても定数倍によっては大丈夫です.

G. Maximise Sum

$i$ を固定して考えます.$L = \min(a_1,\ldots,a_{i-1})$ としたとき,$x=\min(L,a_i+a_j)$ が等しいような $j$ は,そのうち最大のものだけを考えればよいです(目的が最大化であることと,$j-i$ も大きくしたいということから明らか).

制約 $0\leq a_i\leq n$ に注意すると,これだけで,考慮すべき $(i,j)$ は $O(n)$ 通りになります.これは prefix min を $m_i=\min(a_1,\ldots,a_n)$ として $\sum_i(m_i-m_{i+1})\leq n$ であることから分かります.あとは単に,$O(n)$ 個の $(i,j)$ に対するスコアを計算すればよいです.

$i$ について降順に処理します.$b_k=\min(a_1,\ldots,a_k)$ と書くことにします.

  • $1\leq k < i$ の部分:$b_k$ は変化しない
  • $k=i$ の部分:$b_k$ は $x:=\min(b_{k-1},a_i+a_j)$ に変化する.
  • $i<k<j$ の部分:$c_k:=\min(a_{i+1},\ldots,a_k)$ と定めると,$b_k$ は $\min(c_k,x)$ に変化する.
  • $j\leq k$ の部分:$b_k=0$ に変化する.

となります.計算がやや非自明なのは $i<k<j$ の部分です.$i$ をデクリメントしながら列 $c$ を管理すると,$c$ には全体で $O(n)$ 回の区間変更がきます.また列 $c$ は単調減少なので,どこまで $x$ 以上であるかを二分探索して,区間代入と区間和のとれるセグメント木を併用すれば,必要な計算を行うことができます.

全体で $O(n\log n)$ 時間で解けます.

H. Longest Good Subsequence

まだ.

I. Lexicographic Partition

まだ.

CodeForces
スポンサーリンク
シェアする
maspyをフォローする
maspyのHP
タイトルとURLをコピーしました