AtCoder Regular Contest 090
Updated:
Source codes
Solutions
C - Candies
上段を $x_i$ 、下段を $y_i$ とすれば、以下で求まる。
\[ \max_{0 \leq k < N} \left( x_0 + \dots + x_k + y_k + \dots + y_{N-1} \right). \]
ポイント
$O(N^2)$ 解でも良かった。その方が実装簡単だった。
D - People on a Line
$(L, R, C)$ の他に $(R, L, -C)$ を追加すれば、どの頂点から深さ優先探索しても問題なし。
ポイント
大きさが負の逆辺を追加して良い ので、トポロジカルソートは不要だった。座標がマイナスでも良いのはわかっていたが、負の逆辺を追加するのに抵抗があった。
ここで時間を食ってしまったので、成績自体は悪かったようだ。と思ったら意外と下がってなかった。
E - Avoiding Collision
方針
次の順番で問題を解いていく。
- $S$ から $T$ までの最短距離を求める。
- $S$ から $T$ までの最短経路の個数を求める。
- $T$ から各頂点への最短経路の個数を求める。
- 高橋くんと青木くんが出会うペアの個数を求める。
- 答えを求める。
まず 1. は簡単である。ダイクストラ法を使うだけである。ここで、 $S$ から任意の頂点までの最短距離 $D[i]$ が同時に求まる。 2. は恥ずかしいことにミスしたところだから subsection を分ける。
グラフ上の最短経路の個数の求め方
大げさに言えば DP をする。 $S$ から $i$ までの最短経路の個数を $\mathrm{cnt}[i]$ とし、これを全ての $i$ に対して求める。
$S$ から $S$ までの最短経路は $1$ 通りである。他は全て $0$ を入れておく。
遷移の仕方は以下の通りである。頂点 $i$ への最短経路の個数が求まっているとする。各辺 $(i, j, c)$ に対し、まずこの辺がある最短経路に含まれる辺かどうかを判定する。その条件は $D[i] + c = D[j]$ である。この時に $\mathrm{cnt}[j] += \mathrm{cnt}[i]$ とする。
大事なのは、 距離が近いところから確定させていく ことである。距離が遠い頂点を、距離が近い頂点より先に処理すると、後者から前者への経路をカウントしていないまま、前者から伸びている辺を伝っていくことになる。これは間違いである。今回はダイクストラ法を先にやっているので、 $(D[i], i)$ を vector に入れて標準順序でソートして順番に遷移していけば良い。
中学入試でよくやるような工事中の交差点があるグリッドの最短経路の数と基本的には同じであるが、あれは普通は距離が近い順からやらない。下から右へ進む。だから盲点になりやすい。
出会うペアの個数を求める
ここで 4. を解くために 3. へ発想を移動する必要がある。まずどこで出会うかを考察する。最短距離は $L = D[T]$ である。すると、距離 $L/2$ の点(頂点または辺上(内部)の点)で出会うことがわかる。これは 2 通りあって、頂点で出会う場合と、辺上で出会う場合がある。この場合の数をそれぞれ求めたい。
辺上で出会う場合の方が簡単なので、まず考察する。辺 $(i, j, c)$ で、ある経路の組で高橋くんと青木くんが出会うための条件は、 $2D[i] < L$ かつ $L < 2D[j]$ かつ $D[j] - D[i] = c$ である。何通り出会うか？ この辺を使う最短経路の個数 を $t$ とすると $t^2$ 通りである。よって $t$ を求めることに帰着されるが、これは $T$ から頂点 $j$ までの最短経路の個数を $\mathrm{revcnt}[j]$ とすると、 $t = \mathrm{cnt}[i] \mathrm{revcnt}[j]$ である。
頂点 $i$ 上で出会う場合の数は、同様に求まる。条件は当然 $2 D[i] = L$ であり、 $t = \mathrm{cnt}[i] \mathrm{revcnt}[i]$ とし、 $t^2$ 通りである。
ところで 3. 自体は簡単である。 $\mathrm{rev}D[i] = D[T] - D[i]$ とし、 $\mathrm{revcnt}[T] = 1$ を起点とし、先ほどと類比的なことをすれば良い。
残り
「出会わない経路の組の数」は、「出会うか出会わないか関わらない経路の組の数」から「出会う経路の組の数」を引くことによって求まる。前者は $\mathrm{cnt}[T]^2$ である。後者は先ほど求めた。以上で答えが求まった。
最後のところもミスしていて「出会わない経路」を直接求めようとしていた。 「否定語」が含まれる場合の数を数えるときは包除原理を意識 するようにしたい。包除原理はこの問題にしてみれば大げさだが。
ポイント
考察はほぼ完璧だったのに正解に至らなかった。 50 分前に実装を開始し実装は 10 分前に完了していた。しかしミスに気づけなかった。
この問題は 1 つ 1 つのステップは難しくはないと思う。だけども時間内にミスを潰すことができず、とききれなかった。
F - Number of Digits
この問題で扱う区間を以下の 1. - 3. に分ける。
- $r < 10^7$ の区間。
- $l < 10^7 \leq r$ の区間。
- $10^7 \leq l$ の区間。
この問題は $10^7$ から少しはみ出るまで ($3 \times 10^7 + 10$ くらいまで) 馬鹿正直に尺取り法を実行するだけ で、その部分は間に合うという。ゆえに 1., 2. は終わったも同然。 3. のケースだけ真面目に調べればよろしい。 3. のケースは、 3 通りの数字を跨がないことが保証されているから調べるのが難しくはない。
$S$ を $k$ 個の和に分ける($1 \leq k \leq S/8$)。大抵の場合、つまり $S$ が $k$ で割り切れないとき、 $d = S/k$ を並べていって、後半の $S\%k$ 個だけ $d + 1$ を並べるしかない。だからこの場合は位置も定まる。 $1$ 通りである。 $S$ が $k$ で割り切れる時は、場所が定まらないため、 $10^d - 10^{d-1} - S/d + 1$ 通りある。これらを全部足していると間に合わないため、最初に $S/8$ を答えとして持っておき、 $S$ の約数 $k$ を全て調べて、 $10^d - 10^{d-1} - S/d$ を足す方針とする。
ポイント
この問題は解く時間がなかったものの、馬鹿正直に尺取り法を実行するだけでどこまで間に合うのか実験するべきだと思った。 $3 \times 10^7 + 10$ は時間的には大したことがないが、 MLE の危険性があるオーダーであり、ここまで調べられるようになっていると確信できればあとはわずかに考察するだけで終わる。
実装ミス： $2 \times 10^7 + 10$ に最初していて RE を食らった。 $S > 8 \times 9 \times 10^7$ より少し大きいくらいだと RE になる。
Others
C - sample: 4, tle: 2.000, time: 01:22, from_submit: 140:44
D - sample: 5, tle: 2.000, time: 24:01, from_submit: 116:43
E - sample: 4, tle: 2.000, time: 116:43, from_submit: 00:00
F - sample: 5, tle: 2.000, time: 00:00
この日は調子がすぐれなかった。先週言及したカードキャプターさくらは相変わらず面白かった。