3匹の猫

みみねこの競プロ精進メモ

AtCoder Beginner Contest 204参加記(~E問題)

初めて三分探索とダイクストラを書いたかもしれない。本当に水色か?
f:id:mmnkblog:20210606225552p:plain

A - Rock-paper-scissors

9通り場合分けすると解ける。計算量はO(1)

ちなみに、\{0, 1, 2\}のうちxでもyでもない値は3-x-yで求められる。
ついでに、\{1, 2, 3\}のうちxでもyでもない値はx\oplus yである。

B - Nuts

ある木に対して木の実をいくつ取るかはO(1)で計算できるので、すべての木に対してそれを計算すると答えが求まる。
全体の計算量はO(N)

C - Tour

始点と終点を決めたとき、その始点から終点までのパスが存在するかどうか調べる。
事前に、ある頂点を始点としたときに行ける頂点のリストをDFSで計算しておく。これをすべての頂点に対して行う(計算量はO(N(N+M)))。
このリストを用いることで、始点から終点までのパスが存在するかどうかをO(1)で取得することができる。
始点と終点を全探索すると答えが求まる(計算量はO(N^2))。
全体の計算量はO(N(N+M) + N^2) = O(N(N+M))となる。

D - Cooking

それぞれの料理を2つあるオーブンのどちらで調理するか選択するとO(N 2^N)の計算量となってしまう。
全ての料理の調理時間の総和がわかるので、1つ目のオーブンで調理する料理の調理時間の総和が分かれば、2つ目のオーブンで調理する料理の調理時間の総和も求められる。
つまり、「1つ目のオーブンの調理時間」として考えられる値が列挙できれば、それに対応する「2つ目のオーブンの調理時間」が求まり、これらの最大値として考えられる値の最小が答えとなる。

「1つ目のオーブンの調理時間」として考えられる値の列挙は、部分和問題とみなすことができ、これはDPで解くことができる。
dp[i+1][t] := i番目までの料理に対して、ちょうどt分使うような調理時間の和の組合せが存在するかどうか
というDPを解く。0\le i \le N\max(T_i)を満たす整数iに対し、dp[n][i]がtrueなら、1つ目のオーブンをちょうどi分、2つ目のオーブンをちょうど\sum_{j=1}^{N} T_j - i分使うような分け方が存在することが言える。
計算量は、O(N^2\max(T_i))

E - Rush Hour 2

もし辺のコストが固定なら、ダイクストラ法でO(N\log M)の計算量で解くことができる。

ある頂点上で何分でも待って良いということにすると、コストとして考えられる値のパターンが増えてしまうため、時刻Tに頂点Aに到達したとき、頂点Bに向かうために何分待つのが最適かを考える。
t分待つとする。tの下限は0である。D\le T+ tのとき、\left \lfloor \dfrac{D}{T+ t+1} \right \rfloorの値は常に0なので、 C + \left \lfloor \dfrac{D}{T+ t+1} \right \rfloor + t = C+tとなり、tをこれ以上増やす必要が無いことがわかる。よってtの上限はD-Tである。
この範囲で、関数f(t) = C + \left \lfloor \dfrac{D}{T+ t+1} \right \rfloor + t区間[0, D-T]で凸関数のような振る舞いを見せるので、三分探索することでこの関数の最小値を求めることができる…と考えたが、三分探索しても正しい解が求まるとは限らずWA。実際は、整数xに対してf(x) = f(x+1)となる場合があり、こういう関数には三分探索を適用することができない。つまりf(t)は凸関数ではない。
この関数の最小値は\sqrt D付近にあることが式変形からわかるらしい(公式解説より)。よって、頂点Aに到達する最短時刻がわかれば、その段階での頂点Bまでの最短時間がO(1)で求まる。

よって、最適な行動をした場合の辺の最小コストは一意に定まるので、冒頭で話した通りダイクストラ法で解くことができた。
計算量はO(N\log M)

感想

E解きたかった