ABC307 D~F (Julia)

前半の続きです。

D問題

文字列が与えられるので、(と)を内側から対にして消していき、残った文字列を答えましょう。
文字列が「正しい括弧列」とは限りません。

前から順番に(と)を対応づけるのは、スタックでできる。
対応づけた後はその部分文字列を消去すれば良いのだが、((((()))))などで無駄が多く、愚直にやると$O(N^2)$でTLEになる。どうするか。

例えば2文字目に(、それと対応する)が5文字目とすると、2~5文字目をスキップするような仕組みがよい。
l文字目に(、それと対応する)がr文字目とすると、l~r文字目をスキップすればよい。
配列ptrを準備して、対応のある対に対してはptr[l] = r、それ以外は0になるようにし、左から見ていくことで、$O(N)$で解くことができました。
…実は本番では回答をCharの配列ではなくStringとして扱ったため、1回TLEをいただきました…。

d_solve.jl

function solve(n,s)
	stack = Int[]
	ptr = zeros(Int,n)
	for i in 1:n
		c = s[i]
		if c == '('
			push!(stack,i)
		elseif c == ')' && !isempty(stack)
			j = pop!(stack)
			ptr[j] = i
		end
	end
	s2 = Char[]
	i = 0
	while i < n
		i += 1
		if ptr[i] == 0
			push!(s2,s[i])
		else
			i = ptr[i]
		end
	end
	join(s2)
end

E問題

円環の何が面倒って、一周して戻ってきた時に帳尻を合わせないといけないところ。
人Nに渡せる数字は人1に渡した数字に依存するので、人1に渡した数字を持ち回らなければならない？それは嫌。
今回はラッキーなことに、「人iはAiが嫌いです」みたいな制約がないので、「人1は数字0を持っている」としても一般性を失わない！
ただし、最後に通り数をM倍する必要はある。
あとはDP。

e_solve.jl

function solve(n,m)
    # 人1から人iまで数を渡した時点で…
    # 人iが数字0を持つ通り数
	dp0 = zeros(Int,n)
    # 人iが数字0以外を持つ通り数
	dp1 = zeros(Int,n)
    # 人1については手動で設定
	dp0[1] = 1
	for i in 2:n
        # 人iが数字0を持つのは、人i-1が数字0以外を持つ通り数(dp1[i-1]) × 人iが数字0を持つ通り数(1)
		dp0[i] = dp1[i-1]
        # 人iが数字0以外を持つのは…
        #   人i-1が数字0を持つ通り数　　(dp0[i-1]) × 人iが数字0以外を持つ通り数　　　　　　(m-1)
        # + 人i-1が数字0以外を持つ通り数(dp1[i-1]) × 人iが数字0と前の人の数以外を持つ通り数(m-2)
		dp1[i] = (dp0[i-1]*(m-1)+dp1[i-1]*(m-2)) % MOD
	end
    # 人nが数字0を持つと条件を満たさないので、dp1[n]が答え。
    # 以上は人1が数字0を持つ場合の答えであるが、人1が数字0以外を持つ場合も同様。
    # 0,1,...m-1の整数の個数はmなのでm倍すれば最終的な答えになる。
	dp1[n]*m % MOD
end

F問題

基本的にダイクストラなのはすぐに分かる。愚直解法も分かる。
その日に進める距離まで進んで感染させる。進める距離以内の部屋がなくなったらその日は終わり。
翌日は感染者を起点として改めてダイクストラ。その日に進める距離まで進む。その繰り返し。
しかし、それで済むのならF問題ではない。うまくいかない極端なケースを考える。

例えば、感染者からの未感染者までの距離が全て100であり、そのような辺が10万あるとする。
進める距離が10である日が10万日続いた場合、ダイクストラのPriority Queueに格納する作業が$O(10^{10})$になり間に合わない。10万日経てば、ゆうに寿命もくるが。

同じ辺について「Priority Queueに格納するが、1日で進める距離を越えているために使用されない」が繰り返されるというのが無駄なところ。
その日に使われない辺はPriority Queueに格納されない、言い換えると実際に使用される日に初めて呼び出される仕組みが必要。

その日に使われるかどうかはPriority Queueにプッシュする前に分かる。使われない辺は別のPriority Queueにプッシュしておき、新しい1日が始まる時に感染者からの距離が近い方から見ていって、向こうの頂点にすでに到達していれば捨て、いなければその日用のPriority Queueにプッシュすれば良い。
(https://atcoder.jp/contests/abc307/submissions/42940592)

JuliaのDataStructures.jlは性能が良すぎて書き換え可能、キー重複付加なので、無考えに突っ込みにくい。
代わりにBinaryMinHeapを使用する。けんちょん本にもある方法。

f_solve.jl

function solve(n,m,uvw,k,a,d,x)
    # 重み付き隣接リストを作成
	to = [Tuple{Int,Int}[] for _ in 1:n]
	for (u,v,w) in uvw
		push!(to[u],(v,w))
		push!(to[v],(u,w))
	end
    # その日に使う用のPQ。(その日の起点からの距離、頂点番号)を格納。
	h0 = BinaryMinHeap{Tuple{Int,Int}}()
    # 後日に使う用のPQ。(感染者からの距離、頂点番号)を格納。
	h1 = BinaryMinHeap{Tuple{Int,Int}}()
    # 回答を格納する配列
	xs = fill(-1,n)
    # 最初から感染している人の処理
	for p in a
		xs[p] = 0
        # 最初から感染している人の隣の人の処理
		for (q,w) in to[p]
            # 1日目に進める距離内ならh0に格納
			if w ≤ x[1]
				push!(h0,(w,q))
            # 1日目に進めない距離ならh1に格納
			else
				push!(h1,(w,q))
			end
		end
	end
    # 日々の処理
	for (i,xi) in enumerate(x)
		while !isempty(h1)
			wp,p = top(h1)
			wp ≤ xi || break
            # その日に進める距離xi以下の頂点をh1から引き出す
			wp,p = pop!(h1)
			# 引き出した頂点をその日に使うようのh0に格納する
			push!(h0,(wp,p))
		end
        # この時点でh0に格納されている頂点はxi以下であることが保障される
		while !isempty(h0)
			wp,p = pop!(h0)
            # 他の頂点経由ですでにpが処理されていればスキップ
			xs[p] == -1 || continue
            # pさんはi日目に感染となりました。
			xs[p] = i
			for (q,w) in to[p]
                # 他の頂点経由ですでにqが処理されていればスキップ
				xs[q] == -1 || continue
                # wqはその日の起点からのqの距離
				wq = wp + w
                # wqがその日に進める距離内ならh0にプッシュ。必ずその日に処理される。
				if wq ≤ xi
					push!(h0,(wq,q))
                # wqがその日に進めない距離ならh1にp(感染者)からの距離とともにプッシュ。
				else
					push!(h1,(w,q))
				end
			end
		end
	end
	xs
end