AtCoder Beginner Contest 204参加記(~E問題)
初めて三分探索とダイクストラを書いたかもしれない。本当に水色か?
B - Nuts
ある木に対して木の実をいくつ取るかはで計算できるので、すべての木に対してそれを計算すると答えが求まる。
全体の計算量は。
C - Tour
始点と終点を決めたとき、その始点から終点までのパスが存在するかどうか調べる。
事前に、ある頂点を始点としたときに行ける頂点のリストをDFSで計算しておく。これをすべての頂点に対して行う(計算量は)。
このリストを用いることで、始点から終点までのパスが存在するかどうかをで取得することができる。
始点と終点を全探索すると答えが求まる(計算量は)。
全体の計算量はとなる。
D - Cooking
それぞれの料理を2つあるオーブンのどちらで調理するか選択するとの計算量となってしまう。
全ての料理の調理時間の総和がわかるので、1つ目のオーブンで調理する料理の調理時間の総和が分かれば、2つ目のオーブンで調理する料理の調理時間の総和も求められる。
つまり、「1つ目のオーブンの調理時間」として考えられる値が列挙できれば、それに対応する「2つ目のオーブンの調理時間」が求まり、これらの最大値として考えられる値の最小が答えとなる。
「1つ目のオーブンの調理時間」として考えられる値の列挙は、部分和問題とみなすことができ、これはDPで解くことができる。
dp[i+1][t] := i番目までの料理に対して、ちょうどt分使うような調理時間の和の組合せが存在するかどうか
というDPを解く。を満たす整数に対し、dp[n][i]
がtrueなら、1つ目のオーブンをちょうど分、2つ目のオーブンをちょうど分使うような分け方が存在することが言える。
計算量は、。
E - Rush Hour 2
もし辺のコストが固定なら、ダイクストラ法での計算量で解くことができる。
ある頂点上で何分でも待って良いということにすると、コストとして考えられる値のパターンが増えてしまうため、時刻に頂点Aに到達したとき、頂点Bに向かうために何分待つのが最適かを考える。
分待つとする。の下限はである。のとき、の値は常になので、となり、をこれ以上増やす必要が無いことがわかる。よっての上限はである。
この範囲で、関数は区間で凸関数のような振る舞いを見せるので、三分探索することでこの関数の最小値を求めることができる…と考えたが、三分探索しても正しい解が求まるとは限らずWA。実際は、整数に対してとなる場合があり、こういう関数には三分探索を適用することができない。つまりは凸関数ではない。
この関数の最小値は付近にあることが式変形からわかるらしい(公式解説より)。よって、頂点Aに到達する最短時刻がわかれば、その段階での頂点Bまでの最短時間がで求まる。
よって、最適な行動をした場合の辺の最小コストは一意に定まるので、冒頭で話した通りダイクストラ法で解くことができた。
計算量は。
感想
E解きたかった