丸紅プログラミングコンテスト2024（AtCoder Regular Contest 183）A,B,C,D問題メモ

丸紅プログラミングコンテスト2024（AtCoder Regular Contest 183）

A - Median of Good Sequences

• 正整数 $N,K$ が与えられます．
• $1$ 以上 $N$ 以下の整数がそれぞれ $K$ 回ずつ登場する長さ $NK$ の整数列を good な整数列と呼ぶことにします．
• good な整数列の個数を $S$ とおきます．
• 辞書順で $\operatorname{floor}((S+1)/2)$ 番目の good な整数列を求めてください．
• なお，$\operatorname{floor}(x)$ は $x$ を超えない最大の整数を表します．

• $1 \leq N \leq 500$
• $1 \leq K \leq 500$
• 入力される値はすべて整数

あれこれ考えるより、実際に愚直に求めるプログラムを実装して簡単な例から法則を見つけ出す方が速い。

$N$ の偶奇で分かれる。

偶数（たとえば6）の時、先頭の1文字が $1～3$ と $4～6$ のgoodな整数列の個数は等しい。
よって、先頭の1文字が $3$ のgoodな整数列の辞書順最後のものが答えとなる。

N=6 K=3
↓
3 6 6 6 5 5 5 4 4 4 3 3 2 2 2 1 1 1

奇数（たとえば5）の時、先頭の1文字が $1～2$ と $4～5$ のgoodな整数列の個数は等しい。
というわけで先頭1文字目は真ん中の $3$ である。

その中で、2文字目が $1～2$ と $4～5$ のgoodな整数列の個数は等しい。
2文字目も $3$ となる。

連鎖的に考えていくと、先頭 $K$ 文字は $3$（つまり、$\frac{N+1}{2}$）となる。
その後は、$3$ を除いた $1,2,4,5$ で偶数の時と同じことが言えて、「先頭が $2$ の辞書順最後」を後に繋げればよい。

N=5 K=3
↓
3 3 3 2 5 5 5 4 4 4 2 2 1 1 1

Python3

B - Near Assignment

• 長さ $N$ の整数列 $A=(A_1,A_2,\cdots,A_N),B=(B_1,B_2,\cdots,B_N)$ 及び整数 $K$ が与えられます．
• あなたは次の操作を $0$ 回以上行うことができます．
  • 整数 $i,j$ ($1 \leq i,j \leq N$) を選ぶ．ただしここで $|i-j| \leq K$ を満たす必要がある．
  • そして $A_i$ の値を $A_j$ に変更する．
• $A$ を $B$ に一致させることが可能かどうか判定してください．
• $1$ つの入力につきテストケースは $T$ 個あります．

• $1 \leq T \leq 125000$
• $1 \leq K \lt N \leq 250000$
• $1 \leq A_i,B_i \leq N$
• ひとつの入力の中のテストケースすべてにわたる $N$ の総和は $250000$ 以下である
• 入力される値はすべて整数

公式解説を読んでの自分用のメモ。

行える操作の候補数が多すぎて、簡単なケースでも「このケースは不可能っぽく見えるが、本当に不可能か？」を確認するのが 手作業でも、愚直なプログラムを実装するのでも難しい。

操作を逆から考えると上手くいく。
「どうしたらこれで上手くいくと着想できるか？」といわれると難しい。（一応、よくある解法としてセオリーの1つではあるが）

はじめから $A=B$ の場合はもちろんOK。

操作で $A$ にない値を作り出すことはできないので、$B$ に $A$ に無い値が含まれる場合はNG。

また、$K=1$ の場合は、数字を飛び越えることができないので別に扱う。
この場合、並び順を変えない限り、各要素の連続する個数を自由に変えられる。（0個にすることも含め）
よって、ランレングス圧縮して、$B$ が $A$ の部分列であればよい。

上記以外の場合、「最後の操作」を考える。

操作では $A_i$ を $A_j$ に上書きするため、当然、操作直後は $A_i=A_j$ となっている。
これが $B$ と一致するので、$B$ では $K$ 以下離れた2つの要素が同じである箇所が、少なくとも1つなければならない。

K = 2
A  1 2 3 4 5
B  5 5 1 2 1   ←  ○: 1か5を最後に操作したと解釈できる

A  1 2 3 4 5
B  5 1 3 2 1   ←  ×: 最後に操作したと解釈できる要素がない。NG

最後の操作の直前では、$A_i$ の値は何であったと仮定してもよい。これをワイルドカード * とする。

K = 2
A  1 2 3 4 5
B  5 5 1 2 1

   5 5 * 2 1    最後の操作の直前の一例

操作を逆順に考え、$B$ を $A$ に合致させることを目指す。
たとえば * が $2$ であったとすると、最後の操作と同様に $K$ 以下離れた同じ値の一方を * にできる。

   5 5 * 2 1    最後の操作の直前の一例。
   
   5 5 2 2 1 ...であったと仮定し、
   5 5 2 * 1    とできる

これは、結果的に「* を $K$ 以下離れた値とスワップした」と解釈できる。

よって、$K \ge 2$ であれば、スワップを繰り返して好きな値を好きな位置に持っていくことができる。

A  1 2 3 4 5

   5 5 2 * 1    K=2で1を左端に持っていく例
   5 5 2 1 *
   5 5 * 1 2
   5 5 1 * 2
   5 * 1 5 2
   5 1 * 5 2
   * 1 5 5 2
   1 * 5 5 2

$B$ に無い値（または個数が足りない値）は、* を1個消費してその値に変えなければならない。
ただ、$B$ に無い値があるということは、$B$ ではその分だけ、別の値が重複しているということになる。

同じ値を端に固めれば、* を作り出すことができる。

A  1 2 3 4 5 6 7 8 9
B  1 9 1 8 1 7 1 6 1
    ↓
   1 1 1 1 * 9 8 7 6
    ↓
   1 * * * * 9 8 7 6

これで、$K \ge 2$ の場合は、最初の取っかかりさえあれば可能だということが分かった。
距離 $K$ 以内に同じ値がある箇所が1箇所でもあればOK、なければNGとなる。

Python3

C - Not Argmax

• $(1,2,\cdots,N)$ の順列 $P=(P_1,P_2,\cdots,P_N)$ であって，次の $M$ 個の条件をすべて満たすものの個数を $998244353$ で割ったあまりを求めてください．
  • $i$ 番目の条件: $P_{L_i},P_{L_i+1},\cdots,P_{R_i}$ の中の最大値は $P_{X_i}$ ではない．

• $1 \leq N \leq 500$
• $1 \leq M \leq 10^5$
• $1 \leq L_i \leq X_i \leq R_i \leq N$
• 入力される値はすべて整数

区間DP。

本番中にも区間DPの可能性は考えていたが、 「$DP[l,r]$ を求めるのに、$DP[l,m]$ と $DP[m,r]$ を統合した結果と、 $DP[l,m+1]$ と $DP[m+1,r]$ を統合した結果を足したら重複しちゃうな」 など謎の勘違いで行き詰まっていた。

$M$ 個の「条件」は、一般名詞と混同しないよう「禁止条件」と表現する。
また、禁止条件で指定された $[L_i,R_i]$ の区間は「禁止区間」と表現し、区間DPで考慮中の「区間」と区別する。

• $\mathrm{DP}[l,r]:=$ 以下のような、区間 $[l,r)$ を埋める値の決め方。
  • 禁止条件は、$[l,r)$ に内包されるものだけを考慮する。
  • 埋める値は $1～N$ の具体的な値を決めるのでなく、区間内部の相対的な大きさを決める。
    • $1～r-l$ で埋める、と考えてよい

$\mathrm{DP}[l,r]$ を求めるにあたり、 区切る場所 $m$ を様々に変えた結果の重複を防ぐためには、何かしら、排反事象で場合分けする必要がある。
今回の場合、分ける位置 $m$ を「区間内の最大値を置く場所」と考えると上手くいく。

以下、禁止条件は、$[l,r)$ に内包されるもののみを考慮の対象とする。

まず、禁止条件のうち、$X_i=m$ であるようなものがある場合、 $m$ に最大値を置いたら、当然、内包される禁止区間 $[L_i,R_i]$ の中でも最大値になる。 したがって、$m$ には区間最大値は置けない。

以下、$X_i=m$ となる禁止条件が無いとする。無いなら、$m$ に最大値を置ける。
その時の $[l,r)$ の他の値の決め方を求めたい。

禁止区間中に $m$ を含む禁止条件は、もう満たされている。
なぜなら、$m$ が最大値となったため、$X_i \ (\neq m)$ は最大値であり得なくなったから。

残りの禁止条件は、区間 $[l,m)$ または $[m+1,r)$ に内包され、それぞれのDPで既に考慮されている。
この2区間は、左右独立に決められる。 ただし、「相対的な大きさ」を左右で統合するにあたり、${}_{r-l-1}\mathrm{C}_{m-l}$ を掛け合わせる必要がある。

• 区間 $[l,r)$ の $m$ に区間内最大値を置いたときの、残りの値の決め方
  • $f(l,r,m)=\mathrm{DP}[l][m] \times \mathrm{DP}[m+1][r] \times {}_{r-l-1}\mathrm{C}_{m-l}$（$m$ に最大値を置けるとき）
  • $f(l,r,m)=0$（$m$ に最大値を置けないとき）

これで求められる。$\displaystyle \mathrm{DP}[l,r] = \sum_{m=l}^{r-1} f(l,r,m)$ となる。

上記の区間DPでネックとなるのが、「考慮中の区間 $[l,r)$ に内包された禁止条件で、$X_i=m$ であるものがあるか？」を、 各 $(l,r,m)$ につき高速に判定しなければならない点である。

区間DPの時点で、$l,r,m$ の探索に $O(N^3)$ かかり （$\frac{1}{6}$ ほどの定数倍がかかるが、$N=500$ として約 $2 \times 10^7$）、 ほぼ $O(1)$ で判定できなければ間に合わない。

ここで、区間 $(l,r)$ や禁止区間 $(L_i,R_i)$ を2次元座標に落とすと、 $(l,r)$ に内包される禁止条件というのは、右下の範囲になる。

R ^
  |    |
r |----+----
  |    |ここ
 -+----|----> L
       l

$N \times N$ の2次元配列に bitset を使って

• 禁止条件 $L_i,R_i,X_i$ に対して、$(L_i,R_i)$ に $X_i$ 番目のbitを立てる
• 全ての禁止条件を立て終わった後、右下から、bitwise-or で累積和を取る

としておくと、全ての $(l,r)$ につき、そこに内包される禁止条件で指定されている $X_i$ の集合がわかる。

500bitを表現するのに64bit整数を9個ほど使うので定数倍は重くなるが、 $l,r$ が小さい間はbitsetの最大桁もそんなに大きくならないことなどから、なんとか間に合う。

Python3

D - Keep Perfectly Matched

• $1$ から $N$ までの番号のついた $N$ 頂点からなる木があります．
• $i$ 番目の辺は頂点 $A_i$ と頂点 $B_i$ を結ぶ辺です．
• ここで $N$ は偶数で，さらにこの木は完全マッチングを持ちます．
  • 具体的には，各 $i$ ($1 \leq i \leq N/2$) に対し，$A_i=i \times 2-1,B_i=i \times 2$ が保証されます．
• あなたは以下の操作を $N/2$ 回行います．
  • 葉 (次数がちょうど $1$ の頂点) を $2$ つ選び，木から削除する．
  • ただしここで，削除したあとの木も完全マッチングを持つ必要がある．
  • なお，この問題では頂点が $0$ 個の場合も木と呼ぶことにする．

• 各操作について，そのスコアを「選んだ $2$ つの頂点の間の距離 (その $2$ つの頂点を結ぶ単純パス上の辺の個数) 」とします．
• スコアの合計を最大化するような手順を $1$ つ示してください．
• なお，この問題の制約下で $N/2$ 回の操作を完了する手順が常に存在することが証明できます．

• $2 \leq N \leq 250000$
• $N$ は偶数
• $1 \leq A_i \lt B_i \leq N$ ($1 \leq i \leq N-1$)
• $A_i=i \times 2 -1,B_i=i \times 2$ ($1 \leq i \leq N/2$)
• 与えられるグラフは木である

木から頂点を2つずつ取って距離の総和を最大化、という問題は最近のABCでも類題がある。

一応ネタバレ注意

木の重心を必ず通るような2点を選んでいけばよい。
言い換えると、重心 $c$ を根として、$c$ の相異なる2つの子の部分木から、葉を1個ずつ取ってきてペアにすればよい。
（同じ部分木内の2つをペアにする、ということをしなければよい）

今回は「完全マッチングを保つ」という制約もあるため、どれでも好きな頂点を選ぶわけにはいかない。

1つの方法として、2点を結ぶパスが「マッチングに使われる辺と使われない辺が交互になる」ようなペアを取ると、 ペアを削除しても完全マッチングが保たれる。
この時、他の枝のマッチングはこのパス上の頂点のマッチングには影響しない。

◎==○--○==○--○==○--○==◎
    ○==○--'            `--○==○
              ↓
    ○==○--○==○--○==○
    ○==○--'            `--○==○

ペア $(u,v)$ を「根の相異なる2つの子の部分木から、その間のパスがマッチング使用/不使用辺を交互に使うように選ぶ」という観点で考えると、 ペアの1つ $u$ はその時点で根とマッチングしている子頂点（下記例①を根として②）の部分木から選ぶ必要がある。

    ①
  ⇙↓↘      ⇒:マッチングに使われている辺
②  ③  ⑦    →:それ以外の辺
： ⇙↘ ：
  ④  ⑤
  ：  ：

もう1つ $v$ は、他のどの子の部分木でもよい。

ただし、$u,v$ いずれも、根からその頂点まで辿る時に ①→③→⑤のようにマッチングに使われない辺を2回連続で辿ることはダメ。
「子とマッチングしている頂点」からは必ずマッチングしている頂点（③に対する④）を優先して辿る必要がある。

これが保たれるようにするには、根の各子頂点（②③⑦）の部分木に対し、以下のように使用順を決めるとよい。

• 根の子の部分木内を、根の子からそれぞれオイラーツアーする
• （初期状態で）子とマッチングしている頂点は、マッチングしている子を優先して訪れる
• 帰りがけ順で頂点を記録する

この帰りがけ順が、その部分木内で「マッチングに使われない辺を2回連続で通らない」ように頂点を選ぶ順番の1つの例となる。

木の重心を根と見なし、根とマッチングしている子の部分木を $m$、それ以外の子の部分木を $C=(c_1,c_2,...)$ とする。

$m,c_1,c_2,...$ のそれぞれからオイラーツアーの帰りがけ順で、その中の使用順を決めておく。

以下を $\frac{N}{2}-1$ 回繰り返せばよい。

• $m$ の使用順先頭の頂点と、$C$ のいずれか1つ $c_i$ の使用順先頭の頂点をペアにする
• 選んだ $c_i$ を新たな $m$ にし、$m$ は（まだ頂点数が0でないなら）$C$ に移す
  • マッチング使用辺・不使用辺が入れ替わるので、今度は $c_i$ が、根とマッチングしている子となる

この時、最後まで部分木が2つ以上残るように、部分木サイズが大きい子から使用していく。
$C$ から1つ選ぶ際、頂点数が大きい方から取り出せる優先度付きキューを使うとよい。

最後に、$m$ に1つだけ残った頂点と根をペアとしたものを追加して、答えとなる。

Python3