AGC 022 C - Remainder Game

• 問題

問題概要

N要素の整数列{a_i}を以下の作業を繰り返して{b_i}に一致させる.
- いくつかの要素を選び, a_i をa_i % k に変化させる. その際いくつ選んだかに関わらず コスト2^kを払う
必要な最小コストはいくらか.
1 <= a_i, b_i, N <= 50

解法

a_i から a_i % k にコスト2^kの有向辺があるグラフを考える.
すると, いくつかの辺を選び,全てのiについて a_i -> b_i のパスが通るようなグラフを構築する最小コストを求める問題に帰着される.
全ての a_i -> b_i について最短路を求め, そこで使っている最大の辺を考える(このコストを2^kとする)
1 + 2 + .. + 2^k-1 = 2^k - 1 < 2^k から,他の最短路に用いる辺の全てのコストの総和よりも大きいので,
この辺を使わずに a_i -> b_i のパスを通すことが最適であることは有り得ない.
(自明だが,もしそのようなパスが存在するならばそれが最短路として出されている)
つまりこの辺はグラフの構築に必ず必要であることがわかる.
同様にして上から(辺のコストが高い順に)その辺が必要かどうかを見ていけばいい.
具体的には必要な辺を記録しておいて,その次の手順に進むときにはその辺をコスト0の辺として追加し再び最短路問題を解いていく.
最短路はWarshall-Floydで解けるためO(50³), それを辺のコストの数だけ繰り返すためO(50⁴)となる.

メモ

最短コスト求めてor取ればいけるのでは,と思ったがいけなかった(全ての最短路を構築するのは最適とは限らない)
自分の直感にこだわりすぎて解けなかったのでもっと考察力上げねば..

コード