AtCoder Grand Contest 052 A,B,C,E問題メモ

AtCoder Grand Contest 052

A - Long Common Subsequence

• '0'と'1'からなる文字列 $s_1,s_2,s_3$ が与えられる
• $s_1,s_2,s_3$ は'0','1'をそれぞれ $N$ 個ずつ含む長さ $2N$ の文字列である
• 以下の条件を満たす、長さ $2N+1$ の文字列 $t$ を出力せよ
• 条件
  • $t$ は、$s_1+s_1,s_2+s_2,s_3+s_3$ のいずれの（連続するとは限らない）部分列でもある
• テストケースは $T$ 個与えられる
• $1 \le T \le 10^5$
• $1 \le N \le 10^5$
• 全てのテストケースにおける $N$ の総和 $\le 10^5$

あまりにも答え一発なので折りたたむ

|------s------|------s------|
 01101...10111 01101...10111
 |--------||-| |-------||
   N個の0   ^  N-k個の1 ^
          k個の1        1個の0

Python3

今回は配点の傾斜的に1完勝負となり得るので未証明で出すのはちょっと怖かったけど、まぁ通った（よくない）。

B - Tree Edges XOR

• $N$ 頂点の木が与えられる。$N$ は 奇数 である
• 各辺には非負整数値が設定されていて、初期値は $w_i^1$、目標値は $w_i^2$
• 以下の操作を好きなだけ行える
• 操作
  • 好きな辺を1本選ぶ。$(u,v)$ を結ぶ辺を選んだとする
  • その辺の現在の値を $w$ とする
  • 頂点 $u,v$ を端点に持つ、選んだ1本以外の全ての辺について、辺の値を「現在の値 XOR $w$」に置き換える
• 全ての辺の値を目標値にできるか判定せよ
• $1 \le N \le 10^5$
• $0 \le w_i^1,w_i^2 \lt 2^{30}$

○--○==,        ,==○      ～～: 操作する辺
    ○==ｕ～～～ｖ==○      ====: 操作によって値が変わる辺
○--○=='        `==○--○

最初、$N$ で奇数である意味が全くわからないので不安になるが、最後に結びついたときは感動する。

根を決めて、葉に近い辺から確定させていくのか？とか考えるが、 ある辺を目標値にできるような操作を確定したところで結局「他の辺のためにその辺自身は操作すべきかどうか」を確定できない。
また、XOR問題でよくある性質「操作の順番は関係ない」はこの問題では成り立たず、しっかり操作順が関係するので、操作した場合としない場合を親に波及させるのも上手くいかない。

ふと、「辺の値」って考えづらいので「頂点に対する値」に言い直していい感じにならないか考えてみる。

「辺の値＝辺が結ぶ2頂点の値のXOR」と定義すると、適当な頂点（たとえば頂点1）の値を $0$ と仮定して、そこからつながる頂点の値を矛盾しないように次々一意に決めていける。

頂点番号   １        ２        ３        ４
  辺の値       1100      0010      0111
頂点の値  0000------1100------1110------1001

そして、この定義の中で操作がどのように言い換えられるか考えると、

頂点番号   １        ２        ３        ４
  辺の値       1100      0010      0111          ２－３に対する操作
頂点の値  0000------1100------1110------1001

                          ↓

  辺の値       1110      0010      0101
頂点の値  0000------1110------1100------1001

操作対象の辺の両端の頂点（1100, 1110）に、それぞれ現在の辺の値（0010）をXORする操作に相当する。
結果的に「辺が結ぶ2頂点の値を入れ替える」操作と言い換えられることがわかる。

木で、頂点に値が設定されていて「辺でつながった2頂点の値swapを好きなだけ繰り返す」という操作では、好きな頂点に好きなように値を並べ替えられる。

従って、辺の初期値 $w_i^1$ から構成した頂点の値の多重集合を上手く並べ替えることで、目標値 $w_i^2$ が満たされる状態にしたい。

初期値 $w_i^1$ から構成した頂点の値の多重集合を $F$ とする。
また、目標値 $w_i^2$ からも同様に頂点の値の多重集合 $G$ を構成する。

$F$ や $G$ は、最初に頂点1で仮定した初期値によって様々に変化するが、逆に言うとそれにしか依存しない。

最初に頂点1に仮定する値を $i$ としたときの $G$ を $G_i$ とする。
$i=0$ から $i=X$ に置き換えると、できあがる $G_X$ は、$G_0$ の全ての値に $X$ をxorしたものになる。

$X$ の値によらず $G_X$ は全て「目標値 $w_i^2$ が満たされる状態」として条件を満たすし、それ以外は満たさない。

$F_0=G_X$（多重集合として一致する）ような $X$ を見つけたいのだが、ここでやっと $N$ が奇数であることが生きる。

多重集合 $F$ の全ての要素のXORを $f(F)$ と表現することにする。

$F_0=G_X$ なら、当然 $f(F_0)=f(G_X)$ となる。
また、$G_X$ の長さは $N$、つまり奇数なので、$f(G_X)$ は $f(G_0)$ に奇数回 $X$ がXORされた値となり、2つのXOR $f(G_0) \oplus f(G_X)$ はちょうど $X$ となるはずである。

したがって、$f(F_0)=f(G_X)$ となりうる $X$ があるとしたら、$X=f(F_0) \oplus f(G_0)$ しかないことがわかる。

あとは実際に $G_X$ を作り、$F_0$ と多重集合として一致するかどうか確認すればよい。

Python3

二乗の木DPとかの方面に迷走して大分時間を食ったが、まぁギリギリで通せたのはよかった。

C - Nondivisible Prefix Sums

• 正整数 $N$ と素数 $P$ が与えられる
• 長さ $N$ で、各項が $1～(P-1)$ の数列 $A$ は $(P-1)^N$ 通りあるが、以下の条件を満たすものの個数を $\mod{998244353}$ で求めよ
• 条件
  • 接頭辞の和 $A_1, A_1+A_2, A_1+A_2+A_3, ...,$ のいずれも $P$ で割りきれない数列を「よい数列」とよぶ
  • 並べ替えることによって、よい数列にすることが可能である
• $1 \le N \le 5000$
• $2 \le P \le 10^8$

ぱっと見で、「好きに並べ替えてさえ、よい数列にできない」方がレアそうなので、こちらを数えて、全体から引くことにする。

捉えどころが無いが、愚直に調べるコードを書くと（$N,P$ が1桁くらいならなんとかなる）、以下の2つが該当しそうなことがわかる。

• 全体の和が $P$ の倍数
• 同じ数がほとんどを占める
  • でも他の数の組み合わせによって、最頻値の個数が同じでもセーフだったりアウトだったりする

どういう順番で並べようと、全体が $P$ の倍数なら避けようがない。よってそのような数列を数える。

「最後の1個手前までを任意に並べたら残り1個は $P$ の倍数にならないような数を選べばいいから $(P-1)^{N-1} \times (P-2)$ かな？」と思ったら、 実は「最後の1個手前がちょうど $P$ の倍数だった場合、最後は何を選んでもよい」ので、微妙にずれる。

DP的に考えると、以下のようになる。

P = 5                                        遷移
数列長さ           0    1    2    3    4      Pの倍数 →: x 0
-------------------------------------------   Pの倍数 ↘: x (P-1)
和がPの倍数        1    0    4   12   52      P以外   →: x (P-2)
和がPの倍数以外    0    4   12   52  204      P以外   ↗: x 1

これの $N$ 番目の項は、漸化式を解くなり OEISに聞く なりすれば、$\dfrac{(P-1)^N + (-1)^N(P-1)}{P}$ であることがわかる。

重要な性質として、$P$ と互いに素な数 $x$ について、$x,2x,3x,...,(P-1)x \mod{P}$ の $P-1$ 個の数は必ず $1～P-1$ の数のいずれかとダブらずに1対1対応する。

同じ数 $x$ がたくさんある時を考える。
上記の性質より、途中まで並べた時の和の $\mod{P}$ が何であったとしても、そこから $x$ を並べ続けると $P-1$ 回以内には $P$ の倍数は必ず現れてしまう。

つまり、接頭辞の和が $P$ の倍数とならない範囲で $x$ をなるべく多く消費しつつ前から並べても、 最終的に置けるものが $x$ しか残らず、残った $x$ を並べると $P$ の倍数が現れてしまう時、「よい数列」が作れないことになる。

さて、また同様の性質として、$1～(P-1)$ の中で $x$ 以外の数は、$\mod{P}$ 上で「$-(P-2)x, -(P-3)x, ..., -2x, -x$」のいずれかに1対1対応する。

$x$ を $P$ の倍数とならないギリギリの $P-1$ 個まで並べた後、例えば $-3x$ に相当する数を置けば、$x$ は $3$ 個相殺され、さらにあと $3$ 個置けるようになる。

P=5, x=2
                 和modP
2 2 2 2             3    次に2を置いたらPの倍数となる。
2 2 2 2 4           2    -3x ≡ 4 mod 5 なので、4を置いたら、和は3個前の状態に戻る
2 2 2 2 4 2 2 2     3    さらにあと2を3個置ける（次に置いたらPの倍数となる）

2 2 2 2 3           1    -x ≡ 3 mod 5 なので、3を置いたら、和は1個前の状態にしか戻らない
2 2 2 2 3 2         3    あと2を1個置くだけで、再びギリギリになる

不可能な場合というのは、このように $x$ を他の数で相殺しても、なお $x$ が $P$ 個以上余ってしまう状態といえる。
（逆に、$x$ が $P$ 個以上余らなければ、上記のようにすれば必ず $P$ の倍数を避けられる）

「相殺した結果、$x$ が $P$ 個以上余るか」によって、「並べ替えて、よい数列とできるか」が判定可能であることがわかった。

この性質は $x$ によらず同じだし、$x$ ごとに具体的な $-x,-2x,...$ が何に相当するかを知らなくても、 1個ずつあるということさえわかっていれば、まとめて計算できる。

前から順に数列の要素を決めていきつつ、以下のDPを行う。

• $DP[i][j]=$ $i$ 番目の要素まで決め、そこまでで $x$ が $j$ 個余っているとき（負もある）の数列のパターン数

最終的に、$DP[N][P以上]$ が、よい数列を作れないものとなる。
$j$ は減らす時は一気に減らせても増やすのは1ずつしか出来ず、最終的に $P$ 以上となるものだけが重要なので、 $j$ の範囲は $P-N～N$ を考え、この範囲外に遷移するものは捨ててよい。

遷移は、以下のようになる。

• $x$ を置く場合: $DP[i][j] += DP[i-1][j-1]$
• それ以外を置く場合: $DP[i][j] += DP[i-1][j+1]+DP[i-1][j+2]+...+DP[i-1][j+P-2]$

連続した累積和なので、尺取的に枠をずらしながら計算していくと、$i$ ごとに $O(N)$、全体 $O(N^2)$ で遷移できる。

最終的に、$DP[N][P以上]$ の和が、よい数列を作れないものとなる……が、$j$ が $P$ の倍数のものは1つめの条件（総和が $P$ の倍数）と重複しているので除く。

Python3

E - 3 Letters

• ある文字列 $s$ がどの連続する2文字も異なるとき、「$s$ はよい文字列」とする
• 'A','B','C' からなる長さ $N$ の2つの「よい」文字列 $S,T$ が与えられる
• 以下の操作を繰り返して、$S$ を $T$ にしたい
• 操作
  • $S$ の好きな1文字を、'A','B','C' のうちの好きな文字に変える
  • ただし操作後も、文字列 $S$ は「よい」文字列である状態を保つこと
• 最小の操作回数を求めよ
• $1 \le N \le 5 \times 10^5$

もっと効率のよい方法はありそうだが、自分が解いた方針について。

ABC文字列を使った問題でよくあるのは、ABCを0,1,2に変換したり、その上でXORや差分を取ったりして、不変量を探したり操作の言い換えを行うこと。

今回は、$S$ を以下のような数列 $S_d$ に変換すると、操作が言い換えられる。

• $S$ の両端には便宜的に 'A' が置かれていて、これは変えられないとする
• $S[i]$ が'A'で $S[i+1]$ が'B'など、位置的に次の文字が辞書順的に次の文字なら、$S_d[i]=0$
• $S[i]$ が'A'で $S[i+1]$ が'C'など、位置的に次の文字が辞書順的に次の文字でないなら、$S_d[i]=1$
  • ただし便宜的に'C'の辞書順の次は'A'で、ループしているとする
• 次の文字が同じとき、$S_d[i]=2$（基本的に両端のみに発生する）

S     B C B C B A C A
           ↓
    A B C B C B A C A A
Sd   0 0 1 0 1 1 1 0 2

この時、操作により $S_d$ がどのようになるかというと、

    A B C B C B A C A A
     0 0 1 0 1 1 1 0 2
            v
    A B C B A B A C A A
     0 0 1 1 0 1 1 0 2

端っこ以外では、値が $1$ だけ隣り合う箇所に移動する操作となる。

端っこでも、大体は同様のことが発生する。

    A C A B C B A C A A
     1 0 0 0 1 1 1 0 2
      v             v
    A B A B C B A C B A
     0 1 1 0 1 1 1 1 1   swapではなく、あくまで
                   ~~~   値が1ずつ隣り合う箇所に移動する操作

特定の状況のみ例外的なことが発生するが、、、

    A B C B C B A B A A
     0 0 1 0 1 1 0 1 2
      v             v
    A A C B C B A B C A
     2 1 1 0 1 1 1 0 0

端が '0 0' なら '2 1' に、'2 1'なら '0 0' に変化する。（左端の場合。右端は'2'と'1'が逆になる）

ただ、これも「端だけは負の数や3以上の数も許される」とすれば、他と同様「値が1だけ隣り合う箇所に移動する操作」として一貫した法則と見なせる。
この時、初期値と $\mod{3}$ が同じでなければならない。

    A B C B C B A B A A
     3 0 1 0 1 1 0 1 -1
      v             v
    A A C B C B A B C A
     2 1 1 0 1 1 1 0 0

まとめると、

• よい文字列 $S$ は、両端のみ $-1$ 以下や $2$ 以上も許されるが、両端以外では'0','1'からなる数列 $S_d$ に変換される
  • 両端以外が同じで、両端も $\mod{3}$ が同じ $S_d$ 同士は、同じ文字列を表す
• $S$ に対する操作は、$S_d$ に対しては値を $1$ ずつ隣り合う箇所に移動させる操作となる
• 両端以外の数は、操作の途中で $-1$ 以下や $2$ 以上にしてはならない
  • 隣り合う2文字が同じになってしまうことを意味する
  • ただ、端から順に処理していけば問題ないので、特に考えなくてよい

この上で、文字列 $S$ を $T$ にすることを考える。

まず、$S_d,T_d$ に変換する。

$S_d$ の値を1ずつ移動させて、$T_d$ に一致させればよい。

この時、$S_d$ と $T_d$ の総和が異なる場合がある。
$S_d$ の両端の数を±3で調整して総和を $T_d$ に揃えたい。

調整の方法は、左右にどれだけ割り振るかで複数考えられる（総和が同じであっても、左を $-3$ して右を $+3$ するのがよい場合などもある）。
割り振り方を決めると、あとは単に端から対応させるのが最適なので、操作回数は $O(N)$ で求められる。$S_d[i]$ の1と $T_d[j]$ の1を対応させる場合、操作回数は $|i-j|$。

S   A B C B C B A B A A
T   A A B C A B C A B A

Sd   0 0 1 0 1 1 0 1 2    総和がSdの方が3多い
Td   2 0 0 0 0 0 0 0 1

Sd   0 0 1 0 1 1 0 1 -1   調整する
                     ~~
Sd   0 0 1 0 1 1 0 1 -1   調整方法を1つ決めると、
Td   2 0 0 0 0 0 0 0 1    Sdを1ずつ動かしてTdに一致させる最小手数が確定する
      ←←         →
      ←←←← →→→     この調整の仕方では10手

Sd   3 0 1 0 1 1 0 1 -4   調整方法は複数考えられる。
Td   2 0 0 0 0 0 0 0 1    この調整の仕方では22手

調整のために左端に加算した値を $x$ とすると、あまり極端に小さかったり大きかったりしても移動距離が伸びるだけなので、 「$f(x)=$ その調整方法の最小操作回数」のグラフは下に凸なグラフとなっているはずである。
（小さいケースで試した結果だが、本当はこれもちゃんと証明すべき）

$x$ を三分探索すれば、$O(N \log{N})$ で答えが求められる。

Python3

公式解説の方法。

差分では無く、$S$ の各文字をそれぞれ1つの数に対応させた数列 $S_c$ に変換する。
隣り合う数は異なることを利用して「ウォーク」として考える。
つまり、次の文字が辞書順で進む関係なら+1、戻る関係なら-1する（'A'と'C'はループでつながっているとする）。

S   C A B C A B A C B C B A
Sc  2 3 4 5 6 7 6 5 4 5 4 3
            ／＼
          ／    ＼
        ／        ＼／＼
      ／                ＼
    ／

ただし $A=0,B=1,C=2$ と対応づけるとして、各 $Sc$ の $\mod{3}$ が $S$ と等しくなるようにする。
これは、最初の数を揃えれば、後は自動的に揃う。
こうすると、$S_c$ から $S$ を一意に復元できる。全体を±3ずつ平行移動させたものは同じ $S$ を表す。

両端以外の箇所に対する操作は、「山をへこませる」「谷を盛り上げる」操作となる。
つまり、左右に隣り合う数字が同じ箇所を選び、+2または-2する操作となる。

           v
 C A B C A C A C B C B A
 2 3 4 5 6 5 6 5 4 5 4 3
          
        ／＼／＼
      ／        ＼／＼
    ／                ＼
  ／

両端も同様だが、これは左または右の制約がないので、いつでも好きなときに+2または-2できる。

 v                     v
 B A B C A C A C B C B C
 4 3 4 5 6 5 6 5 4 5 4 5
          
        ／＼／＼
      ／        ＼／＼／
  ＼／

さて、$S_c$ と $T_c$ を決めたとき、$S_c$ に操作して $T_c$ に一致させるための最小手数を考えたい。

操作は常に±2でしか行えないので、$S_c[i]$ と $T_c[i]$ の偶奇は一致するように最初の値を決める必要がある。
ウォークなので、$S_c[0]$ と $T_c[0]$ の偶奇を一致させれば、後は自動的に揃う。

その上で、要素ごとの差分 $\displaystyle \sum_{i=1}^{N}\frac{|S_c[i]-T_c[i]|}{2}$ 回の操作は、必ず必要になる。

これ以上かかることがあるとすれば、「本来は操作しなくてよかったり値を減らしたい箇所だが、他の要素を矛盾無く処理するため、一旦は値を増やす必要がある」みたいなことが発生する場合となる。

Sc  2 3 4 5 6 7 6 5 4 5 4 3
Tc  0 1 0 1 2 3 4 5 6 7 6 5
                  ^ 例えばここは±2する必要はないが、
                    他の箇所をそろえるために、一旦操作して戻すような必要性が生じるか？

しかし、そのようなことは発生しない。
「値を減らしたい箇所のうち、最大値の $S_c[i]$ を減らす」「増やしたい箇所のうち、最小値の $S_c[i]$ を増やす」ことを繰り返すと、 回り道となる操作は必要なく、$S_c$ を $T_c$ に一致させられる。

よって、下限となる $\displaystyle \sum_{i=1}^{N}\frac{|S_c[i]-T_c[i]|}{2}$ が実現可能で、これが最小手数となる。

最後に、どのように $S_c$ の値を決めれば $\displaystyle \sum_{i=1}^{N}\frac{|S_c[i]-T_c[i]|}{2}$ を最小化できるか？だが、 $S_c[i]-T_c[i]$ が正になるものと負になるものをなるべく均等にした時が最小となる。

$S_c$ は全体の平行移動でしか調整できないので、たとえば全体を+6すると、$S_c[i]-T_c[i]$ は一律6増える。
この時、その絶対値 $|S_c[i]-T_c[i]|$ は、元が正なら1個あたり6増え、負なら6減る。（正負の境界をまたぐときが微妙に異なるが、まぁ大まかに）
正の個数が負の個数より多ければ $S_c$ は減らした方が得だし、負が多ければ増やした方が得で、それが均衡するところが最小となる。

一度 $S_c[i]-T_c[i]$ を計算し、その中の中央値が0になるようにオフセットを決め、その上で改めて $|S_c[i]+offset-T_c[i]|$ を求めればよい。
ただし、オフセットは6の倍数でしか決められないので、小さめに決めたものと大きめに決めたものを2通り試す。

計算量は、中央値を求めるときのソートのみ $O(N \log{N})$ かかるが、他は $O(N)$ となり、解法1より少ない定数倍で求められる。

Python3