AtCoder Regular Contest 106 F - Figures
メモ
プリュファーコード問題
//下の式は(N-2 )!を掛けるのを忘れている
//上の式は(N-2 )!を掛けるのを忘れている
プリューファーコードより、各次数(ei)が決まっているときの木の場合の数は
(N-2!) / *1というような形になる
上の式は、それにdi 個の穴からei個の穴を選ぶ方法（穴同士が区別されている点に注意）を掛けたものである
あとは、コンビネーションをまとめるように式変形するときれいに解ける
（見えなかった）
AtCoder Beginner Contest 301 F - Anti-DDoS
メモ
以下ではDDoS文字を数える
まず判定問題を考えて問題を簡潔にしたい。
これは排反に数え上げる上でも役立つ。
ある文字列にDDoS文字が含まれていても、その文字列を複数回数えないようにしたい。
こういうものはよく、最初に現れる何かの位置が最小になるように決めるなどの
貪欲的な手法がとられる
今回は文字列SにDDoSが含まれる際に、DDoSのoの部分が一番右になるようなものについて数えることにする
oの位置を順に右から見ていき
oSとなるものの場合の数を求め
また、oより左に同じ大文字が現れる場合の数を求めればいい
公式の解法は、確率的に状態をもちながら行う耳dpだったようだ
ここで重要なのは大文字としてあらわれているものの情報は、今までに何種類現れたかというものだけで充分であるという点
AtCoder Regular Contest 158 A - +3 +5 +7
メモ
問題を言い換えると
X, Y, Zが与えられて
これらに0, 1, 2の順列を足してすべての合計を同じにする操作回数の最小化を求める問題になる
簡単のためにX<=Y<=Zとすると
Z-X, Z-Y, 0
足していって差が上になるようなものを作れるか考える
以後A = Z-X, B = Z-Yとする
A, B, 0
ここで0,1,2を足すことを考えるよりも-1,0,1を足すことを考えた方が
全体の合計が不変になるため見通しが良かった
//
0,1,2 を足す場合は、
A, B, 0(A>=B)で、A <= 2Bなら一回も無駄なく作ることができる
A>2Bなら、(+2,+1,+0)をB回やって
(+2+1, +1+2, +0+0)を必要な回数やればいい
類題
不変量を考えて、-1, +1, 0の操作に帰着する
AtCoder Regular Contest 157 C - YY Square
メモ
グリッド上を通った経路について、スコアがあるものの^2で定まる時
そのスコアの合計を求めろという問題
スコアの計算がそのままでは複雑で、dpで漸化的に扱いにくい。
合計の合計という形にできれば、寄与について考えられる
解法1
n^2 = 1+3+5+ ... + 2n-1
で書けるので
各辺を使ったときに自分の前までに何回yyがあったかによって
その辺の寄与が分かる。
また、自分の前までのyyの回数の合計について
自分の全体での寄与が分かる形なので計算できる
解法2
dp[i][j] を1,1からi,jまでの問題とみなした時の答え
として、漸化的に^2のスコアを求める方法
各dp[i][j]まで持たれているパスの状態について、
sigma(x^2)とした時
次の遷移でsigma((x+c)^2)という形になっているため、
x^0, x^1, x^2をそれぞれ計算しておけば遷移できる。
あるいは、積の和典型で
今までのyyに印1, 印2を押す場合の数を考えるとすると
新しくyyが増えた時に、今までのに(0,1,2)回押していて、あたらしく増えた
yyに何回押すかという風に考えると
x^2というのが自然に複数の物の合計として扱えて遷移できる
AtCoder Regular Contest 156 C - Tree and LCS
メモ
まず、単純な場合を考える
パスの上では与えられた順列を反転することで類似度を1にできることが分かる
同様に木の場合で考えると、ある頂点を根としたときに
その根から分けられる部分木たちSについて
そのS達の各頂点を根を中心として反転するような操作(つまり別の部分木へ移す)をしたくなる。
しかし実際は反転する必要はなく
iの根からの距離をdiとした時に
i, jが同じ部分木に属するなら、i, jが移された位置i2, j2について
di < dj == di2 < dj2 (bool値)
が成り立てば同様に類似度を1にできる
AtCoder Beginner Contest 303 Ex - Constrained Tree Degree
メモ
プリューファー列について調べた
するとSi-1をN回組み合わせてN-2を作る問題になり、
出現回数について重複を除くようにすると
指数型母関数で解ける
AtCoder Beginner Contest 302 G - Sort from 1 to 4
メモ
a(1~4)に動かしたいb(1~4)について有効辺を貼って得られるグラフをGとすると
この問題はＧに含まれる辺を最大個数の閉路に分ける問題になる。
このような考え方は典型で
各iについてこれをjに持っていきたいという問題設計の時に、とりあえずその通りに辺を貼ると考えやすくなることがある
(このようなN頂点N辺の有向グラフをfunctional graphと呼ぶ)
今回は、閉路の長さが短い順にとる貪欲法で解くことができる
ただ証明が難しかった（自分は未証明で解いてしまった）
簡単な証明
まず、a->b, b<-aのような周期2のものは取っていい
理由は一般のfunctional graphにおいてこの問題を解いたとき、
最終的に分けられる閉路xがa->bを含み、yがb->aを含むとすると
x, yからa->b, b->aを取り除いたうえで, x, yをマージでき、閉路の数を更新できることから、a->b, b<-aからなる周期2の閉路を取らない場合は最適解でないから
Gから周期2の閉路を取り除くと、トーナメントグラフになるが
そのグラフにおいて、必ず入次数か出次数が1になる頂点iがある
その場合iを含む閉路は必ず、その辺を通るため
その辺でiとつながってる頂点をjとしたときに、ijをマージしていい
後は同様に考えると貪欲にとっていいことが分かる。
貪欲にとっていいのは4の時の性質で、一般のfuncitonal graphでは成り立たない？
