New Year Contest 2015 ひとこと解法集

rng_58 @rng_58_old

A: やるだけ

rng_58 @rng_58_old

B: 上から greedy (なるべく軽いものを選ぶ)

rng_58 @rng_58_old

C: a に操作してできる文字列は a または a + (a 以外の一文字) + (0 文字以上の任意の文字列) であることを利用して DP

rng_58 @rng_58_old

D: 初期状態を文字 x として一次式 x+c と -x+c への距離を求める

rng_58 @rng_58_old

E: 寝ながら DP すると O(N^3)、次数和が 2(N-2) 以外のものを無視すると O(n^2)、次数 2 の頂点を取り除いて縮約すると O(N)

rng_58 @rng_58_old

F: M を増やしていくと x の属するグループが代わるタイミングが O(sqrt(x)) 回なのでそういうものを全部試す

rng_58 @rng_58_old

G: 4N 頂点の適切なグラフを作って最短路を求めて各ロボットが動き出す時間を求める

rng_58 @rng_58_old

H: 二分探索 -> 45 度回転 -> union find で xmax, xmin, ymax, ymin の頂点を含む辺のみをはる

rng_58 @rng_58_old

I: 一文字ずつ追加していって、(P の位置、Q の位置) として考えられる集合をもって DP (そういうものは O(N^2) しかない)

rng_58 @rng_58_old

J: まず原点からスタートしてちょうど n 歩歩いて初めて原点に戻ってくる、という経路の数を各 n に対して求めて適切な係数をかけて足す

rng_58 @rng_58_old

K: 奇数のときは二等辺三角形全部、偶数のときは奇数のときを少しいじる

rng_58 @rng_58_old

L: 互助法みたいなことをする

rng_58 @rng_58_old

M: (2^n + n)^n + (2^n + n)^(n-1) + ... 通りくらいに場合わけしてそれぞれ数える

rng_58 @rng_58_old

適当な解説を書きました、もう少し詳しい解説は後で書くのでリクエストのある問題を clarification タブから送ってください