2017-05-05から1日間の記事一覧

Expected diameter of a tree | Codeforces #411

コメントつきコード // 頂点の数、辺の数、連結成分のID、最も遠い点までの距離、連結成分の直径 int N, M, Q, cmp[100001], far[100001], nc, dia[100001]; // グラフ、連結成分ごとに最も遠い点までの距離をすべてもってソートしたもの vi G[100001], F[10…

Find Amir | Codeforces #411

2番目の入力例n=10を考えてみよう。 とりあえず、(i+j) mod (n+1) = 0 となるような辺(i, j)はコスト0なので全部張ろう。 1-10 2-9 3-8 4-7 5-6 あとはコスト1以上の辺を貼るしかない。 実はすべてコスト1の辺で繋げられる。 10+2≡1 9+3≡1 8+4≡1 7+5≡1 よっ…

Minimum number of steps | Codeforces #411 (Div. 1)

abのような形が残らないので、操作していくと最終的に bbb....baa...a のような形になる。 とりあえず実験してみる。 ab →bba bはaを飛び越えるときに1個から2個になった。 abに対する操作は1回。 aab →a<ab> →abba →<ab>ba →bbaba →bb<ab>a →bbbbaa aを2個飛び越えるこ</ab></ab></ab>…

Ice cream coloring | Codeforces #411 (Div. 1)

コメント付きコード // 頂点の数、色の数、頂点vに含まれるアイスの数 int N, M, S[300001]; // グラフ, 頂点vに含まれるアイス vi G[300001], C[300001]; // 解, 色iを使ったかどうか int X[300001], use[300001]; int main(){ scanf("%d%d", &N, &M); rep(…