2017-04-13

AOJ 2371 TransferTrain

AOJ

概要

電車で目的地まで行くための最短経路を求めるというよくある感じの問題。

$N$ 本の路線がありそれぞれの路線は $a_i$ 個の駅からなる。一つの路線について駅 $s_1,\ldots,s_{a_i}$ とそれらの間の所要時間 $t_1,\ldots,t_{a_i - 1}$ が与えられる。電車は両方向にあるのでどちら向きに移動しても良い。

また、同じ駅が複数回現れる (異なる路線はもちろん、同じ路線でもありうる)とき、その駅は乗り換え駅で、時間 $T$ で乗り換えることができる。

このとき今いる駅から目的駅までの最短時間と乗り換え回数を求めよ。最短経路が複数あるときは乗り換え回数が最小のものを求めよ。

制約: $1 \leq N \leq 5\times 10^4,\ \sum_{i=1}^{N}a_i \leq 10^5$

解法

Dijkstra.

普通に路線ごとに $s_1 \overset{(t_1,0)}\longleftrightarrow s_2 \overset{(t_2,0)}\longleftrightarrow \cdots$ と辺を張る。辺のコストは(かかる時間、乗り換え回数)を表している。

乗り換えのために同じ駅同士でコスト $T$ の辺を張ると辺の数が大きくなりすぎるので次のように工夫する。駅名 $s$ に対して一つ頂点 $S$ を作っておき、駅 $s$ が現れるごとに $s \overset{(T,1)}\longrightarrow S$ と $S \overset{(0,0)}\longrightarrow s$ のように辺を張る。

後は普通にDijkstraする。スタートとゴールが $a,b$ のとき上に対応するのは $A,B$ になる。また、乗り換えを一回余分に数えている ( $b \overset{(T,1)}\longrightarrow B$ の部分) のでそれを引いたものが答え。

2017-04-04

AOJ 2707 Jail

AOJ

概要

問題文

自然数列 $0,1,2,\ldots$ に対して以下の操作を $N-1$ 回行ったときの先頭の数字を答えよ。

先頭から $0,k,2k,\ldots$ 番目の数字を削除する。

制約: $1 \leq N \leq 10^5, 2 \leq k \leq 10^5$

解法

下のように、ある数字が削除される前は先頭から何番目だったか逆から構成していくと分かりやすい。

削除前	0	1	2	…	k-1	k	k+1	k+2	…
削除後		0	1	…	k-2		k-1	k	…

これを見ると $K-1$ 個おきに削除前の数字と対応が付いているのがわかる。削除後の $x$ 番目の数字は削除前だと $K * \lfloor \frac{x}{K-1} \rfloor + x \bmod (K-1) + 1$ 番目となることがわかるのでこれを $N-1$ 回繰り返し計算すれば良い。