AtCoder Regular Contest 148 B,C,D問題メモ

AtCoder Regular Contest 148

B - dp

• 'd' と 'p' のみからなる文字列 $S$ が与えられる
• 以下の手順で得られる文字列を「$T$ を180度回転させた文字列」とする
  • $T$ を逆順にし、'd' を 'p' に、'p' を 'd' に置き換える
• 1回だけ、$S$ の好きな部分文字列を180度回転させたものに置き換えることができる（しなくてもいい）
• 作れる辞書順最小の文字列を答えよ
• $1 \le |S| \le 5000$

なるべく先頭から続く'd'を多くするのが正義。

「最初に出てきた'p'」の位置を、回転させる区間の左端 $L$ に設定して問題ない。

dddppdppppd
   L

• 区間の右端を'p'にして回転させることで、$L$ からさらに1個以上の 'd' を続けさせることができる
• 最初の'p'より右に設定したら、先頭の'd'の個数は初期のまま変わらないので、↑より必ず少なくなる
• 最初の'p'より左に設定しても、追加で続けさせることのできる個数は変わらないので、単にせっかくの先頭の'd'を削るだけで意味が無い

区間の右端 $R$ は、以下の2通りが考えられる。

• 1. 'p'が最も連続する箇所の、右端の'p'（複数ある可能性あり）
• 2. 最初に出てきた'p'のカタマリの、右端の'p'

ddd ppp d pppp d pp dd pppp d
    L 2      1            1

2.が見落としがち？だが、こいつだけは「区間全てを'd'にする」ことができるので、その後に続く'd'を含めることができ、最適となる場合がある。

ddd pp dddddddddddddddddddddddddddddddd pppp d pppp d
    ~~
    ここだけをひっくり返すのがいい

可能性のある箇所を全て試しても、その箇所が $O(|S|)$、1回の判定で $O(|S|)$ なので、$O(|S|^2)$ で通る。

Python3

C - Lights Out on Tree

• 頂点 $1$ を根とした、$N$ 頂点の木が与えられる
• 各頂点には1枚ずつコインが置かれている
• 以下の操作を好きなだけ行える
  • 好きな頂点 $v$ を選び、$v$ を根とする部分木のコインの裏表を全てひっくり返す
• $Q$ 個のクエリに答えよ
  • 頂点集合 $S=\{v_1,v_2,...\}$ が与えられる
  • コインの初期状態として、$S$ に含まれる頂点は表、他は裏から始める
  • 全てのコインを裏にするために必要な最小操作回数を求める
• $2 \le N \le 2 \times 10^5$
• $1 \le Q \le 2 \times 10^5$
• ($Q$ 回のクエリにおける $|S|$ の和) $\le 2 \times 10^5$

簡単な場合として木でなく直線だった時を考える。操作は以下のようになる。

• 操作: 好きな箇所を選び、以降のコインの裏表をひっくり返す

このような操作は、隣り合う箇所との差分（同じか異なるか。XORと捉えてもよい）に注目すると「そこと1つ前の差分の状態のみを変更し、他は変えない」といえる。

    1 2 3 4 5 6 7
(1) 1 0 0 0 1 1 0    0:表 1:裏
      ^     ^   ^

従って操作回数は「表と裏が隣接する部分」の個数に一致する。
今回、最終的には全て裏にしないといけないが、 頂点 $1$ の親には必ず裏である頂点 $0$ が隠れていると考えると上手く表現できる。

木に戻しても似たようなことが言えて、1回の操作は 「自身と親との差分の状態のみを変更する」ので、答えはそのような箇所の個数と一致する。

上記を踏まえると、以下のようなアルゴリズムが考えられる。

• $S$ に含まれる頂点 $v$ につき、
  • $v$ の隣接頂点 $u$ につき、
    • $u$ が $S$ に含まれていなければ答えに $1$ 計上する

正しい答えは求まるが、これだとTLEとなる。

もし $v$ がめっちゃ多くの頂点と隣接するハブ頂点で、$Q$ 回のクエリでそればかり指定されると、 調べる $u$ の個数が $O(NQ)$ となってしまうからである。

高速化する。

ハブ頂点をたとえば「隣接頂点が $\sqrt{N}$ 個以上の頂点」として分類する。

さらに、各頂点の隣接リストも「ハブ頂点」「ハブ頂点以外」の2つに分類しておく。

木におけるハブ頂点の個数は少ないので、隣接する「ハブ頂点」はどの頂点も高が知れている。
隣接する「ハブ頂点以外」が、ハブ頂点は多い状態となっている。

• $S$ に含まれる頂点 $v$ につき、
  • $v$ がハブ頂点なら
    • $v$ に隣接する「ハブ頂点」$u$ につき、
      • $u$ が $S$ に含まれていなければ答えに $1$ 計上する（従来通り）
    • $v$ に隣接する「ハブ頂点以外」は、とりあえず全て答えに足しておく
  • $v$ がハブ頂点以外なら
    • $v$ に隣接する「ハブ頂点」$u$ につき、
      • $u$ が $S$ に含まれていなければ答えに $1$ 計上する（従来通り）
      • $u$ が $S$ に含まれていれば、$u$ を処理したときに余分に加算されているので、答えから $1$ 引く
    • $v$ に隣接する「ハブ頂点以外」$u$ につき、
      • $u$ が $S$ に含まれていなければ答えに $1$ 計上する（従来通り）

こうすると、1回のクエリで辿る上限が $O(|S|\sqrt{N}))$ となり、クエリ全体の $|S|$ の総和を $M$ として $O(M \sqrt{N})$ となる。

（後から考えると、親だけ別に管理して「隣接頂点はとりあえず全て足す」「親も $S$ に含まれたら双方で足しすぎなので2引く」でよかったね）

Python3

D - mod M Game

• 黒板に $2N$ 個の整数 $A_1,...,A_{2N}$ がある。また、整数 $M$ がある
• 先攻と後攻でゲームをする
• ルール
  • 黒板の数が全て無くなるまで、「残っている中から数を $1$ 個選び、消す」ことを繰り返す
  • 終了時点で、「先攻が消した数の和」と「後攻が消した数の和」それぞれの $M$ で割ったあまりを計算する
  • 両者が一致していれば後攻の勝ち、それ以外は先攻の勝ち
• どちらが必勝か答えよ
• $1 \le N \le 2 \times 10^5$
• $2 \le M \le 10^9$
• $0 \le A_i \lt M$

残った数が2つになった時、先攻がどちらを取っても負けてしまうのは、どのような状況だろうか？

これまでの和を $a,b$、残っている数を $c,d$ とする。

$a+c \equiv b+d \mod{M}$ かつ $a+d \equiv b+c \mod{M}$ が同時に成り立つ。

整理すると、$2c \equiv 2d \mod{M}$ となる。このような状況に後攻は持ち込みたい。

$2c \equiv 2d \mod{M}$ となる $(c,d)$ を考える。

$2c,2d$ は $2M$ 未満なので、$c \neq d$ の場合、$2c+M=2d$ である（大小関係がどちらというのはあるが）。

$M$ が奇数なら偶奇が合わないので明らかに矛盾しており、結局、$c=d$ の場合しか無いことがわかる。

従ってそれまでの和 $a,b \mod{M}$ も同じである必要があり、1つ少ない状態に帰着できる。

再帰的に考えると、後攻は「全ての数が偶数個ずつある場合のみ、先攻と同じ数を取り続けることで勝てる」ことがわかる。

$c \neq d$ の場合でも $2c \equiv 2d \mod{M}$ に解があり得る。
$M=6$ のとき、$(0,3),(1,4),(2,5)$ という、$(i, i+\frac{M}{2})$ という組が $(c,d)$ になりえる。

このような組が残っていた場合、それまでの和 $a,b$ も ちょうど $\frac{M}{2}$ だけ離れていた場合に、両者の和 $\mod{M}$ が同じとなる。
大小関係はどちらでもよい。

つまり、$\frac{M}{2}$ だけ離れた組が $(0,3,1,4)$ のように偶数個あれば、「0なら3、1なら4」のように先攻が選んだペアの片割れを選び続ければ、後攻が勝てると言うことになる。

もちろん、同じ数（$c=d$）がある場合はそれで打ち消してもいい。

$\frac{M}{2}$ だけ離れている2数をペアとして、ペア毎に考えればよい。

• ペア $(A_i, B_i)$ がそれぞれ $p,q$ 個あったとする
• $p,q$ がともに偶数なら、ペアの中だけで完結して先攻と後攻の和に差を生じさせないことができる
• $p,q$ の偶奇が違うと、後攻は先攻と同じペアを選び続けることができない
  • このようなペアが1つでもあると、他の条件に優先して先攻勝利
• $p,q$ がともに奇数なら、その中だけでは $\frac{M}{2}$ の差が生じることになる
  • このようなペアの個数が偶数個なら、後攻勝利

個数カウントして、上記の通りに調べればよい。

数は偶数個あるので、どちらかが余るようなペアは偶数個存在するはずである。

この余る数を上手く組み合わせることで、和が同じになって後攻が勝ってしまわないか？
結論から言うと、それはない。

• ペアでない数同士が2つ余ると、先攻がどちらを取るかで和を必ず異ならせることができる。

よって、

• 先攻は余る数 $x$ をとりあえず取る
• 後攻が選んできた数にペアが残っていたらペアを取り、先攻操作後に両者の和が $x$ だけ異なった状態を維持する
• 後攻が余る（ペアのない）数 $y$ を選んできたら、また余る数を適当に取る
• そのようにしていく内に、余る数が残り2個という状態になる
• 先攻は、現状の両者の差と、残る数を考慮し、和が同じにならない方を選ぶことができる

よって先攻必勝である。

Python3