Codeforces Round 1034

A. Blackboard Game

$n\equiv 0\pmod{4}$ ならば完全マッチングが存在して,それに沿ってプレイすることで後手勝ちです.そうでないならば Alice は$4$ の倍数を選び続けることで勝てます.

B. Tournament

$k\geq 2$ ならば必ず目的を達成できます.その人が戦わないようにすればよいです.$k=1$ のときはその人が最強のうちのひとりであるというのが条件になります.

C. Prefix Min and Suffix Max

長さ $m\geq 2$ の prefix min をとる操作は,長さ $2$ の prefix min 操作 $m-1$ 回と等価です.suffix max も同様で,したがって操作はすべて長さ $2$ の prefix, suffix にのみ行うとしてよいです.

最後の操作を行う直前の要素数は $2$ で,このとき列は $(\min(a_1,\ldots,a_{i}),\max(a_{i+1},\ldots,a_n))$ のようになっています(この形の列は逆にすべて作れる).ここから $1$ 回操作を行うパターンを試すことで,残る値として可能なものを全列挙できます.

D. Binary String Battle

$N\leq 2K-1$ のとき,Alice は必勝であることを示します.

この場合常に Bob の操作対象となるインデックスが存在します.これをひとつとって固定します.Bob の操作では,それ以外のインデックスからちょうど $K-1$ 個を $1$ にすることになります.Alice の操作ではその $K-1$ 個を含む $K$ 個を $0$ にしていけば,すべて $0$ になるまで $0$ の個数を増やしていけます.

以下 $N\geq 2K$ とします.Alice が初手で勝てる場合を除き,Bob が必勝であることを示します.

Alice の手番のあと $1$ がひとつ以上残っているとします.Bob はこのうちひとつに注目し,それを含まないような連続 $K$ 文字(例えば prefix または suffix)について操作をすると,$1$ が $K+1$ 個以上あるようにできます.Bob の手番終了時に $K+1$ 個以上ある状態を維持できます.

E. MEX Count

まずは $k, x$ を固定して,「$k$ 回の削除後に mex を $x$ にできるか」という判定問題を考えます.削除操作で mex は非増加なので,以下 $x\leq \mathrm{mex}(a)$ とします.

まず $x$ はすべて削除しなければいけません.$x$ 未満の値はひとつ以上は残す必要があり,それ以外は自由に削除できます.ここから条件を満たす $k$ は $\mathrm{cnt}[x]\leq k\leq n-x$ を満たすもの全体であることが分かります.

すべての $x$ についてこの範囲を求めて,範囲内の $\mathrm{ANS}[k]$ に $1$ を足す(区間加算)ようにすればよいです.

F. Minimize Fixed Points

$1$ および,$2p>n$ となる素数 $p$ は不動点とならざるを得ません.それ以外は不動点にならないようにできます.

まず,どの $2$ つも共通素因数を持つようなグループに分けます.例えば $n=10$ であれば

  • 素因数 $2$ を持つグループ:$2,4,8$
  • 素因数 $3$ を持つグループ:$3,6,9$
  • 素因数 $5$ を持つグループ:$5,10$

とします.あとは各グループ内で,$2\to 4, 4\to 8, 8\to 2$ などと組み合わせていけばよいです.

どのグループの大きさも $2$ 以上になるように分けるには,各 $p$ に対するグループが $p, 2p, \ldots$ の形になるようにして,それ以外の合成数は自由にグループ分けしていけばよいです.例えば最大素因数のグループに割り当てるとうまくいきます.

G. Modular Sorting

$k$ を何度でも足せるというのは,$d=\gcd(m,k)$ として $\pmod{d}$ で定数であるような範囲で好きな値にできるということです.

$id+j$ を $(i,j)$ と書くことにすると,

  • $(y_1,\ldots,y_n)$ が与えられている.
  • $(x_1,\ldots,x_n)$ を上手く選んで,$0\leq x_i < m/d$ かつ,$(x_i,y_i)$ がペアの比較について単調増加になるようにせよ.

となります.これは手前から貪欲に $x_i$ を割り当てていく貪欲で解けます.

変更クエリに対応します.$d$ を固定して解くというのを,すべての $M$ の約数 $d$ について行います.貪欲に割り当てたときの $x_{i+1}-x_i$ は $y_i,y_{i+1}$ だけから決まるので,$y$ の点変更が来たときにその総和を差分更新できます.

$d$ を固定するごとに $O(N+Q)$ 時間,全体で $O(\sigma_0(M)(N+Q))$ 時間になります($\sigma_0(M)$ は $M$ の約数の個数).

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