naoya_t@hatenablog

いわゆるチラシノウラであります

AtCoder Regular Contest 059

agwたんが埋めてたAtCoder過去問

800点問題を一発AC出来て気持ちよかった

C - いっしょ / Be Together (300点)

http://arc059.contest.atcoder.jp/tasks/arc059_a

  • 100≦x≦100 の範囲でやってみて一番いいやつを

→AC

D - アンバランス / Unbalanced (400点)

http://arc059.contest.atcoder.jp/tasks/arc059_b
文字種ごとにカウント&accumulateして…45度傾けて…始点を全探索して長さ2以上を試す…
あれ
aa みたいな連続を見つけたらその時点でそれを返せばいいし
連続していないやつ(a..a)が過半数まで盛り返すにはどこかで連続するか、axaya みたいに1つおきに挟んでいくしか勝ち目がない
ていうか
「隣り or 1つ向こうに同じ文字があればそれを返す。なければ無い」
っていう事か
→AC

E - キャンディーとN人の子供 / Children and Candies (800点)

http://arc059.contest.atcoder.jp/tasks/arc059_c
式を整理して計算量を減らそう。

C=3のとき、配り方は (0,3) (1,2) (2,1) (3,0) がある

A = [1 1], B = [2 2] のとき

(1^0 * 1^3) + (1^1 * 1^2) + (1^2 * 1^1) + (1^3 * 1^0)
+ (1^0 * 2^3) + (1^1 * 2^2) + (1^2 * 2^1) + (1^3 * 2^0)
+ (2^0 * 2^3) + (2^1 * 2^2) + (2^2 * 2^1) + (2^3 * 2^0)
+ (2^0 * 2^3) + (2^1 * 2^2) + (2^2 * 2^1) + (2^3 * 2^0)

= 

(1^0 * 1^3) + (1^0 * 2^3) + (2^0 * 1^3) + (2^0 * 2^3)
+ (1^1 * 1^2) + (1^1 * 2^2) + (2^1 * 1^2) + (2^1 * 2^2)
+ (1^2 * 1^1) + (1^2 * 2^1) + (2^2 * 1^1) + (2^2 * 2^1)
+ (1^3 * 1^0) + (1^3 * 2^0) + (2^3 * 1^0) + (2^3 * 2^0)

=

(1^0 + 2^0) * (1^3 + 2^3)
+ (1^1 + 2^1) * (1^2 + 2^2)
+ (1^2 + 2^2) * (1^1 + 2^1)
+ (1^3 + 2^3) * (1^0 + 2^0)

要するに

(Ai^0 + .... + Bi^0) * (Aj^3 + ... + Bj^3)
+ (Ai^1 + .... + Bi^1) * (Aj^2 + ... + Bj^2)
+ (Ai^2 + .... + Bi^2) * (Aj^1 + ... + Bj^1)
+ (Ai^3 + .... + Bi^3) * (Aj^0 + ... + Bj^0)

g(i, k) = (Ai^k + (Ai+1)^k + .... + (Bi-1)^k + Bi^k と置けば

= g(i,0)*g(j,3) + g(i,1)*g(j,2) + g(i,2)*g(j,1) + g(i,3)*g(j,0)

h(x, k) = 1^k + 2^k + ... + (x-1)^k + x^k と置けば

g(Ai, Bi, k) = h(Bi, k) - h(Ai-1, k)

h() は高々NC通りで、これを全部前もって計算しておくのはO(NC^2)で可能&参照はO(1)
なのでg()もO(1)


いまこれ2人(i,j)だけど
1人なら g(i,C) = (Ai^C + ... + Bi^C) で
3人なら... g(i,0)g(j,0)g(k,3) + ... + g(i,3)g(j,0)g(k,0) みたいな
組み合わせの数だけの加算で済む

とはいえ
(400+400+1)C400 通りを全列挙してとかは無理というか無駄

DPで行きましょ

例えば C=3 とすると

(0,0,3)
(0,1,2) (1,0,2)
(0,2,1) (1,1,1) (2,0,1)
(0,3,0) (1,2,0) (2,1,0) (3,0,0)

の10通りで

dp(〜j, c) = i〜jにc個配る場合、とすると

dp(〜i, 0) = g(i,0)
dp(〜i, 1) = g(i,1)
dp(〜i, 2) = g(i,2)
dp(〜i, 3) = g(i,3)

dp(〜j, 0) = dp(〜i,0)g(j,0)
// = g(i,0)g(j,0)
dp(〜j, 1) = dp(〜i,0)g(j,1) + dp(〜i,1)g(j,0)
// = g(i,0)g(j,1) + g(i,1)g(j,0)
dp(〜j, 2) = dp(〜i,0)g(j,2) + dp(〜i,1)g(j,1) + dp(〜i,2)g(j,0)
// = g(i,0)g(j,2) + g(i,1)g(j,1) + g(i,2)g(j,0)
dp(〜j, 3) = dp(〜i,0)g(j,3) + dp(〜i,1)g(j,2) + dp(〜i,2)g(j,1) + dp(〜i,3)g(j,0)
// = g(i,0)g(j,3) + g(i,1)g(j,2) + g(i,2)g(j,1) + g(i,3)g(j,0)

dp(〜k, 0) = dp(〜j,0)g(k,0)
// = g(i,0)g(j,0)g(k,0)
dp(〜k, 1) = dp(〜j,0)g(k,1) + dp(〜j,1)g(k,0)
= g(i,0)g(j,0) * g(k,1) + (g(i,0)g(j,1) + g(i,1)g(j,0))*g(k,0)
= g(i,0)g(j,0)g(k,1) + g(i,0)g(j,1)g(k,0) + g(i,1)g(j,0)g(k,0)
dp(〜k, 2) = dp(〜j,0)g(k,2) + dp(〜j,1)g(k,1) + dp(〜j,2)g(k,0)
= g(i,0)g(j,0) * g(k,2) + (g(i,0)g(j,1) + g(i,1)g(j,0))*g(k,1) + (g(i,0)g(j,2) + g(i,1)g(j,1) + g(i,2)g(j,0))*g(k,0)
= g(i,0)g(j,0)g(k,2) + g(i,0)g(j,1)g(k,1) + g(i,0)g(j,1)g(k,1) + g(i,0)g(j,2)g(k,0) + g(i,1)g(j,1)g(k,0) + g(i,2)g(j,0)g(k,0)
dp(〜k, 3) = dp(〜j,0)g(k,3) + dp(〜j,1)g(k,2) + dp(〜j,2)g(k,1) + dp(〜j,3)g(k,0)
= g(i,0)g(j,0) * g(k,3) + (g(i,0)g(j,1) + g(i,1)g(j,0))*g(k,2) + (g(i,0)g(j,2) + g(i,1)g(j,1) + g(i,2)g(j,0))*g(k,1) + (g(i,0)g(j,3) + g(i,1)g(j,2) + g(i,2)g(j,1) + g(i,3)g(j,0))*g(k,0)
= g(i,0)g(j,0)g(k,3) + g(i,0)g(j,1)g(k,2) + g(i,1)g(j,0)g(k,2) + g(i,0)g(j,2)g(k,1) + g(i,1)g(j,1)g(k,1) + g(i,2)g(j,0)g(k,1) + g(i,0)g(j,3)g(k,0) + g(i,1)g(j,2)g(k,0) + g(i,2)g(j,1)g(k,0) + g(i,3)g(j,0)g(k,0)

これはO(NC^2)のDP

で、欲しいのはdp(〜k,3)の値

→AC
実装にちょいと手こずったけど、一発で決まって嬉しい。
→苦手ポイント:二次元dpでどっちの変数がどっちに対応してるのか、みたいなのが混乱してくる。うまく名前をつけるべき。