F - Sandglass 容量Xで一秒間に1砂がおちる砂時計がある。時刻集合r[i]が与えられて、各時刻に砂時計をひっくり返すことがスケジュールされている。時刻0で砂時計の上半分をAという。 このとき、q個のクエリ「初期のAにある砂の量がaのとき、時刻tのAの砂の…

E - ConvexScore 点集合が与えられる。部分集合Sが凸包の頂点をなすとき、そのSのスコアをexp(2, (Sの内部と境界にある点の数) - |S|) と定義する。この点のすべてのSについてそのスコアの和を求めよ。 スコアの意味をよく考えてみると、点集合全体の部分集…

E - Bichrome Tree 頂点数Nの木とN個の数列X[i]が与えられる。各頂点に対し、ある非負整数を割り当て、かつ白または黒に塗り分けるとき、次の条件をみたすようにしたい。 条件：頂点i を根とするサブグラフについて、頂点i と同じ色の配下(i自身も含む)のノ…

D - Restoring Road Network 隣接行列形式でN都市間の距離が与えられる。この隣接行列で表された距離が最短距離となるようなN都市間の経路グラフは構成できるか？できるならば、経路の長さの和が最短であるようなものの経路の和を求めよ。 隣接行列に対してW…

C - Sugar Water A, B, C, D, E, Fが与えられる。空のビーカーに次の操作のいずれかを何回でも行える。 100A[g]の水追加 100B[g]の水追加 C[g]の砂糖追加 D[g]の砂糖追加 現在水100[g]当たりE[g]砂糖が溶け、ビーカーには最大F[g]の砂糖+水が入るとすると、…