AtCoder Regular Contest 078
Updated:
【ARC078/ABC067】
— AtCoder (@atcoder) 2017年7月15日
コンテストは終了いたしました。ご参加ありがとうございました。
解説PDF：https://t.co/AkcVYWCygb
解説放送：https://t.co/oN9bJN6HEx
Source codes
Solutions
C - Splitting Pile
総和を求めておき，上から順に足してやるだけ．
ポイント
「上からとる」のを見逃していた． 300 点の問題だから易しいはずと思うべき．
D - Fennec VS. Snuke
頂点 $0$ と頂点 $N-1$ の間の唯一のパスを互いに埋めて行くのが最善である． まずそのパスを DFS で求める．あとは境界部分で分断してまた DFS するだけ．
ポイント
木構造は任意の $2$ 頂点の間のパスがただ $1$ 通りに決まる．
E - Awkward Response
解説放送に準拠する．
まず $N = 1, 10, \dots, 10^9$ を考察から除外するために，$n = 10^9$ で聞く．すると $N = 10^9$ は Y である．それ以外は $n > N$ が確定するので， $\mathop{str}(n) > \mathop{str}(N)$ かどうかを聞いていることになる．これは $N = 1, 10, \dots, 10^8$ のみ成立するので Y ，残りは N となる．
続いて， $N$ の桁数を決定する． $n = 10^8, 10^7, \dots$ を順に聞く．この時点で $\mathop{str}(n) \leq \mathop{str}(N)$ が確定しているので， $10^i$ の時点で初めて Y が返ってくれば， $n \leq N$ ，すなわち $10^i < N < 10^{i+1}$ が決定する．
$10^i < N < 10^{i+1}$ が決まったとする．ここから二分探索をする． $10^i < m < 10^{i+1}$ なる $m$ に対して， $n = 10m$ を聞く．すると $n > N$ が成立しているので， Y であるための必要十分条件は $\mathop{str}(n) > \mathop{str}(N)$ である．ところが $n$ は $N$ より $1$ 桁だけ大きく，さらに末尾の数字が $0$ であるので，これは $m \geq N$ と同値である．だから二分探索が可能である．
ポイント
$64$ 回の Y/N で $10^9$ 個の整数を見分けるのだから，必ず $2^k$ の効果的な質問をすることになる．現実的な実装では，二分探索をする必要があるのはほぼ間違いない．解説放送では非常に綺麗な解答が示されたが，桁について二分探索する方法でも解答にはたどり着く．
辞書順で比べる場合は，なんとかして桁を先に決める のがポイントとなるように思う．今回の候補の $N$ を辞書順に並べると， $1, 10, \dots, 10^8, 10^9, 10^8 + 1, 10^8 + 2, \dots$ となるので， $10^i$ は使いやすい．ここから気づくのが自然な発想か．仮に $N = 1, 10, \dots, 10^9$ を除外していないと， $10^i$ で $10^i < N < 10^{i+1}$ が決まらない．
リアクティブ問題では，テストを自分で書ける場合は書いた方がよろしい．今回私はテストを書く決断をしたことで， AC に至ることができた．
F - Mole and Abandoned Mine
$S \subset N = \{ 0, \dots, N-1 \}$ ， $i \in S$ として， $\mathop{dp}[S][i]$ を「$S$ の頂点だけ考えた時に， $0$ から $i$ までの経路がただ $1$ 通りのみ存在するための最小コスト」とする．答えは $\mathop{dp}[N][N]$ である． $\mathop{dp}[ \{ 0 \}][0] = 0$ が初期状態である．
$\mathop{dp}[S][i]$ に頂点を付け加えることにする．遷移の仕方は以下の $2$ 通りある．
- $j \in N \setminus S$ が辺$(i, j)$を持つ場合，$\mathop{dp}[S \cup \{ j\} ][j]$ に遷移できる．つまり $i$ から $j$ へ橋を伸ばす ．この場合，遷移コストは「 $j$ と $S$ の間の辺のコストの合計から， $(i, j)$ のコストを引いたもの」である．
- $T \subset N \setminus S$ に対し， $\mathop{dp}[S \cup T][i]$ に遷移できる．つまり $i$ に $T$ をぶら下げる ．この場合，遷移コストは「 $S \setminus \{ i \}$ と $T$ の間の辺のコストの合計」である．
実装方法
$N \leq 15$ で，DFS するわけでもないので，辺は二次元配列 $\mathop{edge}[i][j]$で持っておくほうがよかろう．
まず遷移コストの処理を浮かせるために，事前に下処理をする．その下処理とは， $S \subset N$ に対し $\mathop{setcost}[S] = $ ($S$ の頂点を結ぶ辺の合計コスト) を求めておくことである．これは $O(2^N N^2)$ でできる．すると，各遷移のコストは $O(1)$ で求まる：
- 「 $j$ と $S$ の間の辺のコストの合計から， $(i, j)$ のコストを引いたもの」は $\mathop{setcost}(S \cup \{ j \}) - \mathop{setcost}(S) - \mathop{edge}[i][j]$ と計算される．
- 「 $S \setminus \{ i \}$ と $T$ の間の辺のコストの合計」は $\mathop{setcost}[(S \setminus \{ i \}) \cup T] - \mathop{setcost}[S \setminus \{ i \}] - \mathop{setcost}[T]$ と計算される．
ループの回し方の概要は以下の通り。
for (auto x = 1; x < (1 << N); ++x) {
for (auto i = 0; i < N; ++i) {
// $i \in x$ を保証し，遷移可能か．
for (auto j = 0; j < N; ++j) {
// $j \not \in x$ かつ $(i, j)$ が存在するか．
// 1. の処理
}
int z = (((1 << N)-1)^x) & ((1 << N)-1); // $N \setminus x$
int y = z; // $y \subset z$ 以下の while 文で部分集合列挙．
do {
// 2. の処理
y = (y - 1) & z;
} while (y != z);
}
}
$N$ の power sets に対し，部分集合を列挙して全探索するところは $O(3^N)$ である．上記の 1. は $O(2^N N^2)$ であり， 2. は $O(3^N N)$ である．
ポイント
今の私では，自力では無理無理． $N \leq 15$ から， bitDP を思いつくのが初手．まずそこができなかった．考察時間はせいぜい数分だし当然だが．
部分集合を列挙するところはプログラミングコンテストチャレンジブックを読んで理解した．