問題リンク Area Separation 解法 直線を1本引くたびに面がいくつ増えたかを数えていきます。 直線を1本引いたら増える面の数は 境界線上でない場所で登場する交点の数 + 1 です。交点の数というのはユニークな交点の事を指し、複数の直線と同じ場所で重なっ…

問題リンク Ben Toh 解法 DPです。 dp[ n ]: n日間に得られる弁当の個数の期待値 の表を埋めて解きます。 n日間の期間があり、初日から連続してk日間弁当を獲得できている場合を考えます、またこの状態になる確率をp、次の弁当獲得確率をwinとします。ここで…

問題リンク Roads on Towns 解法 実は、答えとなるような道の結び方は、トタタとツテテの少なくとも一方が目的の街同士を直接結んだ形となります。よって、トタタを直接結んで、ツテテの頂点に対してダイクストラし、その逆も同様にやれば解が求まります。 …

問題リンク Elevator 解法 シミュレーションのようなDPのような解き方です。 エレベータの動かし方は、「荷物が存在する最上階の荷物を1つ下のフロアに最適に運ぶ」というのを繰り返せば答えとなります（解説の記憶が残っていました）。よって、ある解の荷物…