ALGO ARTIS Programming Contest 2023 Autumn（AtCoder Regular Contest 168）B,C,D問題メモ

ALGO ARTIS Programming Contest 2023 Autumn（AtCoder Regular Contest 168）

B - Arbitrary Nim

• $N$ 個の山 $A_1,...,A_N$ でNimをおこなう
• あなたは最初に任意の $k$ を決め、「山から1度に取れるのは1個以上 $k$ 個以下」というルールを追加できる
• 先手が（最善手を取れば）必ず勝てるようにしたい
• 可能か判定し、以下を出力せよ
  • 不可能なら 0
  • 可能だが、$k$ の上限が決められない場合は -1
  • 可能で、$k$ に上限がある場合は、最大値
• $1 \le N \le 2.5 \times 10^5$
• $1 \le A_i \le 10^9$

前提知識として、取れる個数が1個以上 $k$ 個以下のNimは、 「各山の $A_i$ を $k+1$ で割ったあまり」がGrundy数となる。

初期状態のGrundy数の総xorが0なら後手必勝、それ以外なら先手必勝と判定できる。

今回の $A_1,...,A_N$ の総xor ≠ 0（$k$ の制約がなくても既に先手必勝）の場合は、 $k$ を例えばめっちゃ大きい数にすれば制約がないのと一緒になるので、上限はない。-1。

そうでなく、Grundy数の総xorが0の場合を考える。後手必勝なので現状を変える必要がある。

「$A_i$ のどれかを1個だけ変更する」と、必ず総xorは変化する。

$k$ を小さくしていくと、$A$ の大きい方から順に影響があるので、$A$ の最大値を1つだけ変更できればよい。

よって、$k=Aの最大値-1$ とすることで、$A_i$ を1つだけ変更でき、これが $k$ の最大である。

……というのは間違いで、最大値が偶数個あったら「1つだけ」変更することができない。
偶数個の同じ値は、$k+1$ で割ったあまりも同じ値になるので、その部分のxorは変更前も変更後も0であり、総xorは変わらない。

正確には「$k=$（$A$ の中に奇数回登場する値の中で最大の $A_i$）-1」とすればよい。

全てが偶数回登場する場合、不可能となる。

Python3

C - Swap Characters

• 'A','B','C' の3種類の文字からなる、長さ $N$ の文字列 $S$
• 0回以上 $K$ 回以下、好きな2つを選んでスワップできる
• 操作後の $S$ の状態としてあり得るものの個数を、$\mod{998244353}$ で求めよ
• $1 \le N \le 2.5 \times 10^5$
• $1 \le K \le 100$

いくつか実験や考察し、以下のことがわかる。

スワップは好きな位置でできるので、$S$ に出てくるA,B,Cの個数だけが重要で、位置の情報は捨ててよい。

$S$ に含まれるA,B,Cの個数を、それぞれ $F_A,F_B,F_C$ とする。

$K$ 回のスワップで変更できる文字はせいぜい $2K$ 文字なので、$N$ が大きい場合、ほとんどは元の $S$ と同じになる。

$K$ はそこそこ小さいので、変わった部分だけに着目すると上手く数えられないか？

$F_A$ 個のA中、いくつがAのまま残って、いくつがBになって、いくつがCになるか、というのを、全て固定する。

      操作後
      A  B  C  計
操 A  2  9  5  FA=16    縦と横の計が一致する
作 B  6  4  4  FB=14
前 C  8  1  3  FC=12
  計 16 14 12

S = AAAAAAAAAAAAAAAABBBBBBBBBBBBBBCCCCCCCCCCCC
T = AABBBBBBBBBCCCCCAAAAAABBBBCCCCAAAAAAAABCCC  操作後の一例

動く数字は9個もあるが、縦横の合計値が固定で、全て非負という制約があるので、意外と全探索できる（後述）。

もしこの変換テーブルが $K$ 回以内のスワップで達成可能なら、操作後の $S$ の個数は以下になる。

• $\dfrac{16!}{2!6!8!} \times \dfrac{14!}{9!4!1!} \times \dfrac{12!}{5!4!3!}$

最初がAだった箇所を、Aのまま、Bになる、Cになるの3グループに分ける組合せ、というのをB,Cでもやる。

本番では、スワップ箇所（A→A,B→B,C→C を除いた合計）が $2K$ 以下なら全てできると思って、 サンプル合わないな～と唸っていた。

愚直解法と比べると、以下のようなケースが余計に数えられていた。
（愚直を書いて比べるの、大事）

S = AABBCC  K = 3

変わった箇所は6箇所（≦2K）だが、実際は4手必要
BBCCAA, CCAABB

つまり、AをB、BをC、CをA にする循環があると、3箇所に2手必要になる。A→C→B→A の循環も同様。

2種類の循環が同時にあると、それは組み替えれば AB同士, BC同士, AC同士のスワップにできるので、 あくまで残る循環はどちらか片方のみとなる。

変換テーブルから、AB同士、BC同士、CA同士でスワップできる箇所は貪欲にスワップしていくと、 最後にはどちらかの循環が、A→B,B→C,C→A（または逆）が同数だけ残ることになる。

なので、変換テーブルを作成する際は逆から作る。

①循環する個数を決定（t = 0 ～ min(K/2,FA,FB,FC)）
②循環する方向を決定（t > 0 の場合のみ2通りあるが、対称なので最後に2倍すればよい）

↓こんな感じで三角形に配置
      操作後                     操作後
      A  B  C                    A  B  C
操 A  0  t  0    または    操 A  0  0  t
作 B  0  0  t              作 B  t  0  0
前 C  t  0  0              前 C  0  t  0

③AB同士のスワップ個数を決定 (x = 0 ～ min(K-2t,     FA-t,   FB-t  ))
④AC同士のスワップ個数を決定 (y = 0 ～ min(K-2t-x,   FA-t-x, FC-t  ))
⑤BC同士のスワップ個数を決定 (z = 0 ～ min(K-2t-x-y, FB-t-x, FC-t-y))

↓それぞれ対象な位置に加算
      操作後
       A   B   C
操 A   0  x+t  y
作 B   x   0  z+t
前 C  y+t  z   0

⑥合計がFA,FB,FC になるように残りを埋める
      操作後
       A   B   C  計
操 A   a  x+t  y  FA
作 B   x   b  z+t FB
前 C  y+t  z   c  FC

これで、実際にK回以内で可能な変換テーブルを作成できる。

①③④⑤で $O(K^4)$ のループを回すが、$K$ を分割しているだけなので、定数倍で何分の一かになり、間に合う。

Python3

D - Maximize Update

• 長さ $N$ の横一列に並んだグリッドと、$M$ 個の区間 $[L_i, R_i]$ がある
• はじめ、グリッドは全て白で、以下の操作を繰り返し行う
  • 区間を1つ選んでその範囲を全て黒で塗る
• 1回の操作で1マスでも新規で黒に塗られたとき、その操作で「更新が発生した」とする
• 上手く操作順を決めることで、最大で何回の更新を発生させることができるか
• $1 \le N \le 500$
• $1 \le M \le N(N+1)/2$

区間DP だけど、分割の仕方がちょっと珍しいやつ。
$DP[l,r]$ を求めるのに、よくあるのは分割位置 $m$ を全探索して $DP[l,m]+DP[m,r]$ をするタイプだが、 この問題は $DP[l,m]+(マス m に関する値)+DP[m+1,r]$ とするタイプ。たまに見る。

以下のDPで解く。

• $DP[l,r]=[l,r)$ の区間をはみ出すことなくおこなえる更新の最大回数

これは、以下で更新できる。

更新が発生するマス m を固定すると、

...   l       m          r
...  □□□□□□□□□□

         ■■■■■          ①区間をはみ出さず、m を塗れる区間があるか？(0:ない/1:ある)
                                ＋
     □□□□                ②DP[l,m]
                                ＋
               □□□□□    ③DP[m+1,r]

$DP[l,r]$ は、$m$ を $l～r-1$ まで動かして調べた中の、①+②+③の最大値となる。

②と③は区間をはみ出さない更新回数なので、それぞれ独立に操作できる。
それぞれが最大となるように操作した後、①に該当する区間（あれば）で操作すれば、 確実に $m$ は白マスであり、更新が発生する。

これで、$O(N^3)$ の計算量でDPを埋め、$DP[0,N]$ が答え。

……とは言ったものの、まだちょっとした課題はある。

「$m$ を含み、両端が $[l,r)$ を超えない区間があるか」を $O(1)$ で判定しなければならない。

これは、以下を定義すれば、

• $cnt[l,r]=[l,r)$ に完全に含まれる区間数

(②の範囲の区間数 $cnt[l,m]$) + (③の範囲の区間数 $cnt[m+1,r]$) ＜ (対象範囲全体の区間数 $cnt[l,r]$) なら、②と③にまたがった箇所に区間があるということになる。

cntの計算は、まず各区間に対して $cnt[L_i,R_i]+=1$ した後、lが減る方向、rが増える方向に累積和を取っていけばできる。

l\r  0  1  2  3  4  5      区間
0          1               [0,2)
1                1         [1,4)
2                          [3,5)
3                   1
4
  ↓
l\r  0  1  2  3  4  5
0          1  1  2  3   ↑と→方向に累積和
1                1  2
2                   1
3                   1
4

Python3

または、矩形Chmin、1点取得を行える双対2次元セグメント木を使って、以下を管理してもよい。

• $pre[l,m]=$ 左端が $l$ 以右で、$m$ をカバーできる区間のうち、最小の $R_i$（なければINF）

ある $l,m,r$ に対し、$pre[l,m] \ge r$ なら、はみ出さない区間はないということになる。