ABC 235
Table of Contents
D - Multiply and Rotate
- 操作1: $x$ を $a$ 倍する
- 操作2: $x$ を文字列とみなして, 末尾の数字を先頭に移動させる とする.
DFS or BFS を使って, 1 からスタートして N になるまでの操作回数の最小値を求める. $N$ からスタートして $1$ にする方でも可.
DFS の計算量の正確な見積もり方はわからないが, $\log_2(10^6) = 19.93...$ であるので, 7桁の数を $a$ で割れる回数は高々20回程度で 操作2をしたところでそんなにパターン数は多くなさそうに思えるが, 本当にそうなのか微妙なところ. 際どいテストケース持ってこられたときに TLE にならないか自信がない.
E - MST + 1
クエリを先読みする問題. 元々のグラフの辺と, クエリによる辺を合わせて最小全域木を作ることを考える. 作っている際にクエリ由来の辺を使ったほうが得なときは, そのクエリを Yes, そうでない場合は No を出力する. プリム法だとグラフの構築が必要になるので, クラスカル法で解くほうが楽そう.