実装問題をコンテスト中に通せない病気。
■A - Digit Machine
書いてる通りにやる
■B - Pasta
mapで
■C - Connect 6
開始地点を全探索して４方向に
■D - Sequence Query
セグ木で解く方法しか思いつかなかった。
multisetが想定解らしい
■E - Putting Candies
周期性に注目する。
■F - Skate
必要頂点のみもってbfsというのは一目なのですが実装が面倒
■G - Round Robin
最大流。
試合と選手の頂点を作って辺を貼る
勝ったら辺に流れるようにする。
選手からtへの流量は、単独優勝させたい選手の最大勝利数がnなら
その選手はn、それ以外はn-1として全試合の勝ち負けが決まるかどうか
これはn*(n-1)/2流せるかどうか。
■Ex - Card Deck Score
解説を読むと割と素直
形式的べき級数を考えると求めたいものは
[x^m]ΠΣ(ajx)^iなので(iの範囲などは省略)
式変形を行い、
[x^m]Π(1-(ai*x)^(bi+1))/(1-ai*x)となる。
分子パートはnが小さいので項数が2^nのため愚直に展開しても十分に間に合う。
問題は分母の
Π1/(1-ai*x)の部分。
これはΣci/(1-ai*x)の和の形に分解できる。
ここまでわかれば[x^m]値が直接求められるので答えが求まる。
