Exawizards Programming Contest 2021（AtCoder Beginner Contest 222）E,G問題メモ

Exawizards Programming Contest 2021（AtCoder Beginner Contest 222）

E - Red and Blue Tree

• $N$ 頂点の木、長さ $M$ の数列 $A=(A_1​,...,A_M​)$、整数 $K$ が与えられる
• この木の $N-1$ 本の辺を赤か青に塗るとき、塗り方は $2^{N-1}$ 通りあるが、次の条件を満たす塗り方の個数を求めよ
• 条件
  • 頂点 $A_1$ から出発して $A_2,A_3,...,A_M$ を順番に最短で訪問する
  • その際、赤い辺を通過した回数を $R$、青い辺を通過した回数を $B$ とすると、$R-B=K$ である
• $2 \le N \le 1000$
• $2 \le M \le 100$

道筋の立て方はまぁ自然かなと思う。実装は重め。

• ①実際に $M$ 個の点を順番に訪問して、各辺を使う回数をカウントする
• ② ①の結果を使ってDPをおこなう
  • $DP[i][j]=i$ 番目の辺までの色を決めて、確定した $R-B$ の値が $j$ となる塗り方の個数

木なので、どう足掻いても $M$ 頂点を順番に訪問するのに通る経路、ひいては各辺を使う回数は固定である。
全行程で $D_i$ 回使う辺を赤に塗れば、最終的な $R-B$ には $+D_i$ だけ寄与するし、青に塗れば $-D_i$ だけ寄与する。 こうすれば後は、どの辺を＋で寄与させ、どの辺をーで寄与させるかのDPになる。

①は、1回1回BFSなりDFSなりすればよい。
使った辺を特定する必要があるので、経路復元を可能にしておく。
たとえば、各頂点に「この頂点に到達するのに使用した辺」を記録しておけば、ゴールから遡りながら復元できる。

②のDPは、$DP[0][0]=1$、他は $0$ で初期化し、各 $i,j$ につき以下のように遷移する。

• $DP[i+1][j+D_i] += DP[i][j]$
• $DP[i+1][j-D_i] += DP[i][j]$

これ、計算量を考えるとちょっと不安になる。

1辺あたりのカウントの最大値は $M$ 回だが、$j$ が取り得る範囲としてはその総和、つまり $j=-NM～NM$ の範囲を取り得る。

$i=0～N-1$ の範囲を動くので、DPの計算量は工夫無しでは $O(N^2M)$、制約上限を代入すると $10^8$ となる。

Pythonなどの遅い言語では、もう少し高速化を試みたい。

• $i$ ごとに、現在 $j$ の取り得る範囲（$D_1～D_i$ の和）を記録して、その範囲より外は $0$ に決まっているので飛ばす
  • 約2倍の高速化
• 実はこの更新方法では、$j$ は偶数と奇数のどちらかにしか値が埋まらないので、そちらだけ探索する
  • 約2倍の高速化

また、以下のような方法もある。

■各Diに+か-を割り当てて合計がKになるようにする

（達成できる一例）
 + D1   - D2   - D3   + D4   + ...  + D[N-1]    = K

両辺に S = D1+D2+D3+...+D[N-1] を足す

 + 2*D1 -  0   -  0   + 2*D4 + ...  + 2*D[N-1]  = K + S

2で割る
   D1                 + D4   + ...  + D[N-1]    = (K + S) / 2


つまり、各Diに+か-を割り当てて合計がKになる割り当て方があると、
それの「+を割り振ったもののみの合計」は、必ず (K + S) / 2 になる。
（上では一例を取りだして説明したが、他の例でも必ずそうなる）

従って、「$D_i$ からいくつかを選んでその和が $\dfrac{K+S}{2}$ になる方法の個数」を数えればよいことになる。

こうすると、遷移は以下のようになるので、

• $DP[i+1][j+D_i] += DP[i][j]$ （赤に塗る場合）
• $DP[i+1][j] += DP[i][j]$ （青に塗る場合）

DP配列は実装上、$i$ の次元を省略し、1つ前の状態に $D_i$ だけシフトしたものを足し込んでいく、という形にできる。

計算量のオーダーは変わらないものの、Pythonでは特にNumpyを使って高速化しやすい形にできる。

Python3

G - 222

• 整数 $K$ が与えられる
• $2,22,222,...$ のように'2'を繰り返した整数を考える
• このような整数の中で最初に $K$ の倍数が表れるのは、何個の'2'が繋がったものか、求めよ
• 存在しない場合、-1 と答えよ
• 1つの入力につき $T$ ケース与えられるので、全てに対して求めよ
• $1 \le T \le 200$
• $1 \le K \le 10^8$

なんかABC174と似ていたらしい。みんなよく覚えてるな。

ただ、ABC174では1つのケースだけ求められれば良かったので 「割り算の筆算シミュレーション」的な解法が使えたが、最悪 $O(K)$ かかるので今回は無理。

より高速に求める方法を用いる。

まず大まかな場合分けとして、

• $K$ が偶数の時、111…1 が $\dfrac{K}{2}$ の倍数であればよい（以降、$K←\dfrac{K}{2}$ として考える）
• $K$ が奇数の時、111…1 が $K$ の倍数であればよい

これで全ての $K$ について同等の条件を調べればよくなった。

ここで、999…9 を $10^n-1$ という形で表現できることを使うのが、このような問題における典型アプローチっぽい。
従って、以下のように言い換えられる。

• $10^n-1$ が $9K$ の倍数
• $10^n-1 \equiv 0 \mod{9K}$
• $10^n \equiv 1 \mod{9K}$

これ、考え方はlogと同じであり、modの世界におけるlogは離散対数問題と呼ばれている。

• 離散対数問題 (Discrete Logarithm Problem) を任意 mod で解く - Qiita

$X^n \equiv Y \mod{M}$ となる最小の $n$ を求めたいとする。

解が無い場合もあるが（場合分けは上記記事参照）、存在する場合は鳩ノ巣原理で $0 \le n \lt M$ の範囲で必ず見つかる。

従って、平方分割の容量で $\sqrt{M}$ ずつ枠をずらしながら考える。この手法はBaby-step Giant-stepと呼ばれる。

X = 10   Y = 1   M = 171

n     1   2   3   4   5  ...  14  15  ...  28  29  ...  170
X^n  10 100 145  82 136  ...  73  46  ...  28 109  ...   55

この中に、10^n = 1 となる正整数 n があるはず。

√171 ≒ 14 なので、1～14, 15～28, 29～42, ... ごとに探していく。

まず、$n=1～14$ を愚直に求め、辞書などで $10^n$ から $n$ を逆引きできるようにしておく。

この中に $10^n=1$ となるものがあれば、それが答え。

無い場合、$Y$ の方をずらす。つまり、mod上で $Y$ を $X^{-14}$ 倍する。

• $X^n \equiv Y \mod{M}$
• →$X^{n-14} \equiv Y \times X^{-14} \mod{M}$

$1 \times 10^{-14} \equiv 82 \mod{171}$ となる。
次は、逆引き辞書から $82$ を探せばよい。

すると $n=4$ の時が見つかる。
$14$ ずらした結果 $n=4$ の時に見つかったので、$n=18$ が答えとなる。$10^{18} \equiv 1 \mod{171}$

辞書の内部実装によるが、値の検索が $O(1)$ でできるなら、1つの $K$ につき $O(\sqrt{K})$ で求められる。

Python3