ACPCVC20200205 復習メモ - tinumu's reminder

色々と考察が出来て嬉しい
AtCoder Virtual Contest
↑リンク

A: Awkward Response

桁数がわかっていれば値 $n$ を $10$ 倍にした時に、必ず $N$ より大きくなるから、数字の大きさを考慮しなくて良くなる。
この時 $n \leq N$ だと辞書順で小さいので "No", $n > N$ だと "Yes" と出るので単調性から二分探索ができる。->答えが小さい試行で見つかる。

桁数は $N$ が10のべき乗じゃなかったら、 $n$ を $1, 10, 100,...$ と $10$ のべき乗にして調べていく。
必ず辞書順は $n$ のほうが小さいので数字が超えた時点で "No" が出る。
逆に"No" がいつまで立っても出ない時は $N$ は $10$ のべき乗である ( $n > N$ になった瞬間に $str(n) > str(N)$ になるのでいつでも"Yes"になってしまう)。
この時は $2, 20, 200...$ と調べると、 $str(n) > str(N)$ を常に満たしているので、 n > N になった時に "Yes" とでる。この時に $1 / 2$ して答えが出る。

他にも桁の値を順に決めていってめちゃくちゃ大きい値で試すという方法もある。
どちらにせよ、想定解が一番きれいだった

B: Mole and Abandoned Mine

辺を取り除くのではなく、1->Nが橋であるような辺のコストを最大化したグラフを作る事を考える。
答えは全ての辺のコスト - 作ったグラフの辺のコストの総和。

いくつかの頂点を一つのグループとして考えて、(1を含むグループ)->(グループ)->...->(グループ)->(Nを含むグループ) を形成するとする。
グループの中の1頂点をターミナルと名付け、その頂点のみ、他のグループへ行けるようにする(これはリストでなければならない)(1とNは必ずターミナルでなければならない)。
このようにすると、ターミナルは1回しか通れないのでターミナル以外の頂点に移動すると、もうNにはいけないので、Nに行く通りが1通りになる(ターミナルだけ通って移動する通りのみになる)。

各グループ内の辺がどのように張られていても、ターミナルだけ指定すれば1通りになってくれるので、張れるだけ張ってしまう。
頂点集合 $T$ に張れる辺のコストの総和は $O(2^N*M)$ で求まる。

最大化する問題を解くには、ターミナル $v$ であるグループ $S$ から、ターミナル $u$ であるグループ $T$ へ遷移するdpを考える。

$dp[bit][u]$ : すでに $bit$ の頂点を使っており、現在ターミナル $u$ にいる時の辺を繋げられる最大値

まだ使っていない頂点の全ての集合と、その中のターミナルをどの頂点にするかを定めて全てに遷移させる。

$chmax(dp[bit|T][v],dp[bit][u]+sum[T]+cost[u][v])$
( $sum[T]$ :集合 $T$ にできるだけ辺を張ったコストの総和, $cost[u][v]$ : $u$ -> $v$ へのコスト)

という漸化式を立てる。
そうすると、 $dp[2^N-1][N]$ が答えになって、計算量は二項係数の形になるので、 $O(3^N*N^2)$ くらいでとける。 $N$ がもう少し外れるらしい。

C:Sports Festival

全部のスポーツを開いてみる。そうした時に、すでに $N$ 以下の解は求められている。仮にこの解を $n$ とする。
あるスポーツを取り除く時、他のスポーツの参加人数は必ず増える。単調増加である。
つまり、現在 $n$ 人集まっているスポーツは取り除かれなければ $n-1$ 以下には出来ない。
そのため、貪欲に取り除く。
このあとは、先ほどと同じ問題を解いていけばいい。
最適解にするためのヤバイ因子はこの処理で取り除かれていくので(単調増加性から、たくさん集まる奴は残っていても仕方がない)、最適解に落ち着いていくというわけである。

単調増加性から、取り除かなかったほうがいいやつがなにもない事が言えるので、単調に最適解に近づいていくという考えで合ってるのかな。良さそう？