AtCoder Regular Contest 185 A,C,D,E問題メモ

AtCoder Regular Contest 185

A - mod M Game 2

• 正整数 $N, M$ があります。ここで $N \lt M$ が成り立ちます。
• Alice と Bob がゲームをします。$2$ 人は $1, 2, \dots, N$ が書かれたカードを $1$ 枚ずつ、合計 $N$ 枚のカードをそれぞれ持っています。
• ゲームは以下のように進行します。
  • Alice を先攻として $2$ 人が交互に「手札を $1$ 枚選び、場に出す」という操作を繰り返します。
  • カードが場に出た直後に、今まで場に出たカードに書かれている数の総和が $M$ で割り切れる状態になったら、直前にカードを出した人の負け、そうでない人の勝ちとなります。
  • 上の条件を満たすことなく両者が持っているカードを全て出し切った場合は Alice の勝ちとなります。
• 双方が最適に行動した時、Alice と Bob のどちらが勝ちますか？
• $T$ 個のテストケースが与えられるので、それぞれに対して答えを求めてください。

• $1 \leq T \leq 10^5$
• $1 \leq N \lt M \leq 10^9$
• 入力される値は全て整数

論理クイズ的問題。

$N \lt M$ なので、双方とも、手元に2枚以上のカードが残っているときは必ず負けを回避できる。

Bobが勝つためのチャンスは一度きり。
Aliceがラス1を出したときに $M$ の倍数となるように、Bobが仕向けられるかにかかっている。

このとき、場にあるカードの総和は $N(N+1)-(Bobが最後に残したカード)$ で、Bobだけがこの値を操作できる。

$b=N(N+1) \mod{M}$ とすると、$b$ を残すことで、ラス1の値を $M$ の倍数にできる。
$b=0$ または $b \ge N+1$ なら、そもそも初期の手持ちにないのでできず、Aliceの必勝である。

$1 \le b \le N$ なら手持ちにあるのでBobは $b$ を残すと勝つことができる。

残る問題は、Bobがそれまでに負けることが無いか？

Bobの手持ちが3枚以上なら、選択肢が2つ以上あるので負けることはない。
Bobがラス2のカードを出すとき、$b$ を残すように出さなければならず自由度が無い。
Bobが負けることがあるとすれば、このタイミングである。

しかし、Alice,Bob が互いにラスト1枚（それぞれ $a,b$ とする）を持っているとき、 場の総和は $N(N+1)-a-b \equiv -a \mod{M}$ である。

$N \lt M$ より、これは $M$ の倍数になることはないので、Bobがラス2の時に負けることはない。

したがって、$N(N+1) \mod{M}$ が $1～N$ の間ならBobの勝ち、それ以外ならAliceの勝ちと判定できる。

Python3

C - Sum of Three Integers

• 整数列 $A = (A_1, A_2, \dots, A_N)$ および整数 $X$ が与えられます。
• 次の条件を全て満たす整数の組 $(i, j, k)$ を $1$ 組出力してください。
  • $1 \leq i \lt j \lt k \leq N$
  • $A_i + A_j + A_k = X$
• 条件を満たす組が存在しない場合はそのことを報告してください。

• $3 \leq N \leq 10^6$
• $1 \leq X \leq 10^6$
• $1 \leq A_i \leq X$
• 入力される値は全て整数

2数を仮定したらあと1数が存在するかチェックすればよいが、そもそも2数の仮定が $O(N^2)$ なのでできない。

後述の解法をするに当たって、$A$ に同じ値が含まれ、 それを2、3回使うような解があった場合、少し判定がややこしくなる。
そういうのは $O(N)$ で判定できるので最初にしてしまい、 「解があるとしたら3数がバラバラの組である」という状態にしてしまう。

重複を除いた $A$ を $A'$、長さを $M$ とする。

$F(x):=x^{A'_1}+x^{A'_2}+...+x^{A'_M}$ とし、$F^2$ を畳み込みで計算することで 「和が $y$ となる2数が存在するか？」を、任意の $y$ について $O(1)$ で判定できるようになる。

ただし、$F^2$ には同じ2数を重ねて選んだものも含まれているため、それは除いておく。
$i=1,...,M$ について、$F^2$ から $x^{2A'_i}$ を引けばよい。

後は、残り1数 $A'_i$ を固定し、$X-A'_i$ が2数の和として存在すればその2数を $O(M)$ で確認すればよい。

Python3

D - Random Walk on Tree

• 頂点に $0, 1, \dots, N \times M$ の番号がついた $N \times M + 1$ 頂点の木があります。
  • $i$ 本目の辺 $(1 \leq i \leq N \times M)$ は頂点 $i$ と頂点 $\max(i - N, 0)$ を結ぶ辺です。
  • また、頂点 $0$ には色が塗られています。それ以外の頂点は色が塗られていません。
• 高橋君は頂点 $0$ にいます。高橋君は色が塗られていない頂点が存在する間、次の操作を行います。
  • 自身がいる頂点に隣接する頂点の中から一様ランダムに頂点を $1$ つ選んで、その頂点に移動する。(全ての選択は独立である。) そして、今いる頂点に色が塗られていなければ色を塗る。
• 操作を行う回数の期待値を $\text{mod }998244353$ で求めてください。

• $1 \leq N \leq 2 \times 10^5$
• $1 \leq M \leq 2 \times 10^5$
• $N, M$ は整数

こんなグラフである。

0---1--5--9   ^
 |--2--6--10  |N
 |--3--7--11  |
 `--4--8--12  v
   <---M--->

頂点 $0$ から、長さ $M$ の $N$ 本の枝が伸びている。
どの枝に入ったとしても、最奥の頂点まで到達しなければあまり意味が無い。
最奥の頂点が塗られないまま0に戻ったら、結局、最奥を塗るために再度その枝に入らないといけない。

期待値を、移動の過程を「枝の1つに入ってから出るまで」で区切って計算しようと思うと、なかなか難しい。
その枝の最奥まで到達した場合・しなかった場合で確率・期待値を分けて計算したいが、あまり上手くできない。

「枝に入ってから出るまで」ではなく、「どれかの最奥に着くまで」で移動を区切って考えるとスムーズである。

• ①頂点 $0,1,...,M$ からなる一直線のグラフで $0$ からランダムウォークする。
  • 負の数や $M+1$ 以上にはならず、端の $0,M$ ではそれぞれ必ず $+1,-1$ に移動するとする。
  • このグラフで $M$ に至ることは、元のグラフでどれかの枝の最奥に至ったことに相当する。$M$ に至ったら②に進む。
• ②どの枝の最奥に至ったかは等確率なので、$N$ 面ダイスを振って後から枝を決めると考える。
  • その枝が未探索だったら未探索枝が1減る
• ③未探索枝が0になったら終了
• ④未探索枝が1以上なら、$M$ から $0$ までランダムウォークで戻る。①に戻る。

①で $0→M$ に至る回数期待値と、④で $M→0$ に至る回数期待値は等しい。$E$ とする。

$E$ は、直線グラフで「頂点 $i$ からスタートして最奥に至るまでの回数期待値を $E(i)$」として、$E(0)$ を求めれば良い。

M=3
0---1---2---3

• $E(3)=0$
• $E(2)=1+\frac{E(1)+E(3)}{2}$
• $E(1)=1+\frac{E(0)+E(2)}{2}$
• $E(0)=1+E(1)$

$E(M)$ はゴールなので $0$ となる。$E(0)$ は必ず1に移行するので少し遷移が異なる。

この $E(0)$ は結果的に $M^2$ になるが、それを知らなくても $O(M)$ かけて計算してもよい。
$E(M)=0$ から順に代入していくことで、$E(0)$ を求めることができる。

また、②③の部分は $N$ 個を揃えるコンプガチャと見ることができる。1回引くのにコストが往復分で $2E$ かかる。

コンプガチャを引く回数期待値は、$F=\frac{N}{N}+\frac{N}{N-1}+...+\frac{N}{1}$ となる。

• コンプガチャに必要な回数の期待値の計算 | 高校数学の美しい物語

ただし、この問題では最後の頂点をコンプした後は0に戻らなくてよいため、その1回分は減算できる。

答えは、$2FE-E$ となる。

Python3

E - Adjacent GCD

• 正整数列 $B = (B_1, B_2, \dots, B_k)$ の スコア を $\displaystyle \sum_{i=1}^{k-1} \gcd(B_i, B_{i+1})$ として定義します。
• 長さ $N$ の正整数列 $A = (A_1, A_2, \dots, A_N)$ が与えられるので、$m = 1, 2, \dots, N$ に対して次の問題を解いてください。
  • 列 $(A_1, A_2, \dots, A_m)$ の空でない部分列は $2^m - 1$ 通りありますが、それらのスコアの総和を $998244353$ で割った余りを求めてください。ただし、$2$ つの部分列が列として同じでも、取り出す位置が異なるならば区別するものとします。

• $1 \leq N \leq 5 \times 10^5$
• $1 \leq A_i \leq 10^5$
• 入力される値は全て整数

$A$ の制約 $10^5$ 以下で最多の約数を持つものは、83160 の 128 個である。

大まかなイメージとして、$i=1,2,...,N$ の順に、$A_i$ の約数1つ1つについて 「自分より左に、この約数を持つ数は何個ありましたか？」を参照＆メモしていく、という解法が考えられる。
$N$ 以下の整数の中での約数の個数の最大値を $d(N)$ として、 $O(d(A_{\max})N) \sim 6 \times 10^7$ の計算量はちょっと不安を感じるが、定数倍が軽ければPyPyでも間に合いそう。

だが、たとえば2数のGCDが 6 の場合、単に約数毎に個数をメモするだけの方法では 1,2,3,6 の4回で重複して数えられてしまう。

これを解決するには、オイラーのトーシェント関数が使える。

• オイラーのφ関数

任意の $n$ について、「$n$ の全ての約数 $d$ に対して $\phi(d)$ を合計すると、$n$ になる」という性質を持っている。
これを使うことで、約数ごとに個数をカウントして合計を取って正しく求まるようになる。

           約数毎の個数カウント
 d  φ(d)  A:  6  9  8   12
 1    1        1  1  1   ←  3個×φ(1)  = 3
 2    1        1     1   ←  2個×φ(2)  = 2
 3    2        1  1      ←  2個×φ(3)  = 4
 4    2              1   ←  1個×φ(4)  = 2
 6    2        1         ←  1個×φ(6)  = 2
 8    4              1
 9    6           1
12    4                  ←  0個×φ(12) = 0
                                         ~~~~~ 合計 13  ←約数ごとのφの合計が、
                                                        ↙ペア毎にGCDを計算した合計と
GCD(6,12)=6, GCD(9,12)=3, GCD(8,12)=4      →  合計 13    一致する

また、この問題で求めるべきは、全ペアのGCDの総和ではなく、「全ての部分列の【隣接GCDの総和】の総和」なので、 たとえば $A=(1,2,3,4,5,6)$ に対して $GCD(3,5)$ は、 それより外側にある $1,2,6$ をそれぞれ部分列に含むか含まないかの $2^3$ 通りで加算される。

よって、それを織り込みながらカウントする必要がある。

• $S_m:=A$ の先頭 $m$ 要素からなる数列に対するスコア
• $C_{m,d}:=A$ の先頭 $m$ 要素からなる数列の部分列のうち、末尾の要素の約数に $d$ が含まれるものの個数（$m$ の次元は実装上は省略し、逐次更新）

• $S_m$ を求めたい。
  • $S_{m-1}$ に含まれるペアは、$S_m$ にも全て含まれる。加算回数は $A_m$ を部分列に含むか否かで、全てのペアで2倍になる。
  • $A_m$ を部分列の末尾に追加することで生じる新たなペアのスコアは、$A_m$ の約数 $d$ ごとに $C_{m-1,d} \phi(d)$ を合計することで求まる。
• $\displaystyle S_m = 2S_{m-1} + \sum_{d|A_m}C_{m-1,d}\phi(d)$ となる。
• $A_m$ の各約数 $d$ に対して、寄与を $C_{m,d}$ に加算する。
  • $A_m$ が末尾となるような部分列は $2^{m-1}$ 個あるため、$C_{m,d}=C_{m-1,d}+2^{m-1}$ となる。

これを、$m=1,2,...$ の順に求めていくことで、全ての $m$ に対する $S_m$ が求まる。

Python3