−目次
Exawizards Programming Contest 2021(AtCoder Beginner Contest 222)E,G問題メモ
E - Red and Blue Tree
問題
- N 頂点の木、長さ M の数列 A=(A1,...,AM)、整数 K が与えられる
- この木の N−1 本の辺を赤か青に塗るとき、塗り方は 2N−1 通りあるが、次の条件を満たす塗り方の個数を求めよ
- 条件
- 頂点 A1 から出発して A2,A3,...,AM を順番に最短で訪問する
- その際、赤い辺を通過した回数を R、青い辺を通過した回数を B とすると、R−B=K である
- 2≤N≤1000
- 2≤M≤100
解法
道筋の立て方はまぁ自然かなと思う。実装は重め。
- ①実際に M 個の点を順番に訪問して、各辺を使う回数をカウントする
- ② ①の結果を使ってDPをおこなう
- DP[i][j]=i 番目の辺までの色を決めて、確定した R−B の値が j となる塗り方の個数
木なので、どう足掻いても M 頂点を順番に訪問するのに通る経路、ひいては各辺を使う回数は固定である。
全行程で Di 回使う辺を赤に塗れば、最終的な R−B には +Di だけ寄与するし、青に塗れば −Di だけ寄与する。
こうすれば後は、どの辺を+で寄与させ、どの辺をーで寄与させるかのDPになる。
①は、1回1回BFSなりDFSなりすればよい。
使った辺を特定する必要があるので、経路復元を可能にしておく。
たとえば、各頂点に「この頂点に到達するのに使用した辺」を記録しておけば、ゴールから遡りながら復元できる。
②のDPは、DP[0][0]=1、他は 0 で初期化し、各 i,j につき以下のように遷移する。
- DP[i+1][j+Di]+=DP[i][j]
- DP[i+1][j−Di]+=DP[i][j]
これ、計算量を考えるとちょっと不安になる。
1辺あたりのカウントの最大値は M 回だが、j が取り得る範囲としてはその総和、つまり j=−NM~NM の範囲を取り得る。
i=0~N−1 の範囲を動くので、DPの計算量は工夫無しでは O(N2M)、制約上限を代入すると 108 となる。
Pythonなどの遅い言語では、もう少し高速化を試みたい。
- i ごとに、現在 j の取り得る範囲(D1~Di の和)を記録して、その範囲より外は 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 になる。 (上では一例を取りだして説明したが、他の例でも必ずそうなる)
従って、「Di からいくつかを選んでその和が K+S2 になる方法の個数」を数えればよいことになる。
こうすると、遷移は以下のようになるので、
- DP[i+1][j+Di]+=DP[i][j] (赤に塗る場合)
- DP[i+1][j]+=DP[i][j] (青に塗る場合)
DP配列は実装上、i の次元を省略し、1つ前の状態に Di だけシフトしたものを足し込んでいく、という形にできる。
計算量のオーダーは変わらないものの、Pythonでは特にNumpyを使って高速化しやすい形にできる。
G - 222
問題
- 整数 K が与えられる
- 2,22,222,... のように'2'を繰り返した整数を考える
- このような整数の中で最初に K の倍数が表れるのは、何個の'2'が繋がったものか、求めよ
- 存在しない場合、
-1
と答えよ - 1つの入力につき T ケース与えられるので、全てに対して求めよ
- 1≤T≤200
- 1≤K≤108
解法
なんかABC174と似ていたらしい。みんなよく覚えてるな。
ただ、ABC174では1つのケースだけ求められれば良かったので 「割り算の筆算シミュレーション」的な解法が使えたが、最悪 O(K) かかるので今回は無理。
より高速に求める方法を用いる。
まず大まかな場合分けとして、
- K が偶数の時、111…1 が K2 の倍数であればよい(以降、K←K2 として考える)
- K が奇数の時、111…1 が K の倍数であればよい
これで全ての K について同等の条件を調べればよくなった。
ここで、999…9 を 10n−1 という形で表現できることを使うのが、このような問題における典型アプローチっぽい。
従って、以下のように言い換えられる。
- 10n−1 が 9K の倍数
- 10n−1≡0mod9K
- 10n≡1mod9K
これ、考え方はlogと同じであり、modの世界におけるlogは離散対数問題と呼ばれている。
Xn≡YmodM となる最小の n を求めたいとする。
解が無い場合もあるが(場合分けは上記記事参照)、存在する場合は鳩ノ巣原理で 0≤n<M の範囲で必ず見つかる。
従って、平方分割の容量で √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 を愚直に求め、辞書などで 10n から n を逆引きできるようにしておく。
この中に 10n=1 となるものがあれば、それが答え。
無い場合、Y の方をずらす。つまり、mod上で Y を X−14 倍する。
- Xn≡YmodM
- →Xn−14≡Y×X−14modM
この時、mod逆数が存在するかどうかで少しややこしくなるが、 今回は X=10 と M が互いに素でない(M が2や5の倍数)なら不可能であることがわかりやすいので、 最初に場合分けしてしまえば残りは必ず存在する。
1×10−14≡82mod171 となる。
次は、逆引き辞書から 82 を探せばよい。
すると n=4 の時が見つかる。
14 ずらした結果 n=4 の時に見つかったので、n=18 が答えとなる。1018≡1mod171
辞書の内部実装によるが、値の検索が O(1) でできるなら、1つの K につき O(√K) で求められる。