AtCoder Grand Contest 027
Updated:
Source codes
Solutions
A - Candy Distribution Again
満足するのが「ちょうど $a_i$ 個」配られた場合だけだということに注意。多すぎても少なすぎてもいけない。 sort しておき、基本的には貪欲法で配って $x$ を減らしていく。
- 全員に配れて、 $x > 0$ の場合、答えは $N - 1$ である。
- 全員に配れて、 $x = 0$ の場合、答えは $N$ である。
- 全員に配れなかった場合、配れた人数が答えである。
ポイント
1WA はまぁ仕方ないかな。
B - Garbage Collector
全く答えの方針がわからず。
$DP[i][j][k] = i$ 番目の点以降を、何らかの $j$ のパラメータを使って回収する路線を指定する
みたいな方法でできないかなと。
ペンディング。後でわかった。
ポイント
C - ABland Yard
コンテスト中に思いついた解法
どのような $A, B$ 文字列でも作れるということは、つまり、移動中いかなる時点でも、次に $A$ の点にも $B$ の点にも行ける辺があるということである。このような永久遷移可能な点を求めていくわけだが、そのためには、 $A$ または $B$ のいずれかには遷移できないという点を再帰的に取り除いていけばいい。具体的には以下のようにする。
- まず $0, \dots, N-1$ の各頂点に対し、 $A, B$ のどちらかにいけないような頂点がないか調査する。そのような頂点を queue $Q$ に入れる。
- $Q$ が空でない限り、次の動作を繰りかえす。
- $v \gets Q$ する。 $v$ をグラフから削除する。
- $v$ から出ている辺 $e = (v, w)$を削除する。
- 削除した際、 $w$ が「 $A, B$ のどちらかにいけないような頂点」になっている場合は、それを $Q \gets w$ とする。
- 最後まで行った時点で、生き残っている点があって、 $A, B$ いずれの文字からも始められるならば答えは
Yes, そうでないならNoである。
以上を高速に行う場合は、
$L[i] = s[i]$ が
Aであれば $0$ 、そうでないならば $1$
とし、さらに辺は set<int> S[200010][2] で持っておくべきである。計算量は $O(N + \max(M, N) \log N)$ である。
解説放送の模範解答
定理：次の (1), (2) は同値である。
(1) 任意の文字列が実現可能である。
(2) $AABBAABBAABBAABB\dots$ が実現可能である。
(1) から (2) は自明である。 (2) から (1) を示そう。 (2) の $AABBAABBAABBAABB\dots$ の実現可能ルートを切り開いて両方向への単純な path $AABBAABBAABBAABB\dots$ を作る。任意の文字列 $S$ を十分真ん中の適当な点から始めると、右か左に必ず $A, B$ があるから必ず遷移できる。ゆえに (1) が成立する。
そこで mod $4$ で $0$ 番目の頂点 $A$, $1$ 番目の頂点 $A$, $2$ 番目の頂点 $B$, $3$ 番目の頂点 $B$ を区別して数えることが重要になってくる。そこで 同じ点を $2$ 種類に区別したグラフを作る ことで解決する。つまり $A_i$ の点を $A_{i0}, A_{i1}$ にわけ、 $B_j$ の点を $B_{j2}, B_{j3}$ にわける。仮に $A_i$ と $B_j$ の間に辺があったら、方向付きの辺 $(A_{i1}, B_{j2})$, $(B_{j3}, A_{i0})$ を張る。他も同様。このグラフでループができていれば $AABBAABBAABBAABB\dots$ が作れる。
ポイント
私がこの解法を思いついたのは 無限遷移を数えるためには、停止位置から逆算して止まる点を取り除けば良い である。以下の問題の経験があったからである。
- Mujin Programming Challenge 2018 D - うほょじご この問題は全体の空間が $10^6$ マスしか無いのが簡単な考察からわかるので愚直に無限ループ判定しても良いのだが、解説放送の模範解答のように停止位置から深さ優先探索をして、そこから辿りつかなった点が無限ループを起こしていると考えるとより直接的な解放になる。前者で私はこの問題を解いていたのだが、後者で解く方法を知っていたので、今回は応用が効いた。
解説放送の方は、定理を思いつくのは難しいが、 必要条件を列挙したら十分条件だった のパターンと見ることもできる(難しい)。後半は 同じ点を $n$ 種類に区別したグラフを作る を使う。たくさん類題があるが、例えば類題には以下がある。
- SoundHound Inc. Programming Contest 2018 -Masters Tournament- D - Saving Snuuk スヌークに両替する前と後の世界で頂点を分けて持っておく。うまくできている。
- ACM-ICPC Japan Alumni Group Contest Prelim 2014 一日乗車券 その解説 これもよくできている。 $H \leq 24$ であるから頂点を $25$ 個持っておけば十分である。 DP との組み合わせにもなっている。
D - Modulo Matrix
「相異なる」を無視すれば $a_{ij} = (i + j + 1)m + 1$ でいけるのだがそれ以上がわからず。