code-festival-2017-quala.contest.atcoder.jp 距離dが与えられる。マンハッタン距離がdの点同士は異なる色で塗られるように格子点を塗り分けたい。塗り分けを一つ構成せよ。 マンハッタン距離を考えるときは、必ず45度回転を考える。そうすると、x軸またはy…

code-festival-2017-quala.contest.atcoder.jp 要素がアルファベットの行列が与えられる。各行及び各列が回文になるように要素を並び替えたい。可能かどうか判定せよ。 まずすべての要素について、a～zの登場回数をmod4でカウントしておく。 そして行及び列…

agc019.contest.atcoder.jp 格子マップ及びいくつかの頂点が与えられる。格子の辺は100m、与えられた頂点にはN個の噴水があり、半径10mの外周を通ることが可能である。格子点は同一水平線上または同一垂直線上にたかだか1個である。 スタートとゴールが与え…

agc019.contest.atcoder.jp 文字列Aが与えられる。任意の添字i, jを選び、連続部分文字列A[i]..A[j]を反転させる。(i=jならなにもしないのと同値)。この操作を1回だけしたときに得られる文字列は何通りあるか？ 左の文字から順に数えていく。今見ている文字…

agc019.contest.atcoder.jp アイスティーの単価がQ, H, S, D円でそれぞれ0.25l, 0.5l, 1l, 2l買える。在庫はいくらでもある。Nリットルのアイスティーを買いたいとき、必要な金額はいくらか？ 要は2lのものをいくら買うか、ということである。まずリットル単…

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]の砂糖+水が入るとすると、…

時間かけてACした問題は復習も兼ねてブログに書くべきなんだけど、通した時点で力尽きてしまうのなんとかしたいですね。3連休に一気に積みAC？をまとめるか…

arc082.contest.atcoder.jp 順列p[i]が与えられる。何回かp[i] とp[i + 1]をSwapするという操作を行い、すべてのiについてp[i] ≠ i となるようにしたい。操作の最小回数を求めよ。 p[i] = i となるような連続部分列があったとする。この時、この部分列の長さ…

arc082.contest.atcoder.jp 数列a[i]が与えられる。ある数Xを選んで、各a[i]に対して-1, 0, +1のいずれかを加えることで、a[i]=Xとなるiの個数が最大になるようにしたい。最大値を求めよ。 v[n]=(a[i]=nとなるようなiの個数) という配列を作っておきます。す…