Codeforces Round #566 (Div. 2)
ばちょ
A. Filling Shapes
問題：L字のピースを3*nの枠に綺麗にはめる。何通りのハメ方があるか
誤読して何ピース使うかかと思いました。
そもそもピースに対する記述少なすぎてなんだかって感じでした。サンプルも雑だし
B. Plus from Picture
問題：w*hのグリッドに*と.がある。あるマスの*を中心に4方向に１マス以上連結な*があって、他のマスは.であるようなマスはあるか
考察：
愚直に調べるだけです。
各行の*の数に着目すると、2つ以上あるマスは1行のみです。
列も合わせて考えると中心が1つに定まります。
あとは愚直に4方向みて、*が1つ以上あることを確認します。
そして関係ない箇所は*になっていないかを調べればよいです。
めちゃめちゃ実装大変でした。
端っこになるときとか、考えるコーナーケースが多くて辛かったです。
3ペナ1時間くらいだったんですけど、何とか通せてよかった。
C. Beautiful Lyrics
問題：n個の文字列が与えられる。詩をできる限り多く作り出力せよ
詩：2*2で4つの文字列で構成される。s0s1s2s3とすると、s0とs2、s1とs3の母音の数が一致する。またs1とs3の最後の母音が一致しなければならない。
考察：
愚直にやるだけです。
はじめ、母音の数と最後の母音で分類して、できるだけs1s3の候補を作ります。
上で余ったものは、母音の数だけの分類に回します。
こちらはs0s2になるのでできるだけ候補とします。
上で振り分けたものをk個、下で振り分けたものをl個とすると
k<=lでk個
k>lでl＋(k-l)/2個
の詩を作ることができます。
感想：
実装に20分くらいかけて1ペナ踏んだんですけど、まあまあかなと思います。
ただBで沼りすぎて辛かったって感じでした。
1:05で3完したあと、DかEを通せれば実力通りって感じでしたが、Eは考察できずDはバグが消せませんでした。かなしい。
D. Complete Mirror
問題：n頂点の木が与えられる。ある根を選び根付き木とする。depthが同じ頂点で子の数が同じような根の選び方を求めよ
考察：
根から見て同じ深さでは同じ数の枝が出ています。
葉の深さはそろっていなければなりません。なぜなら揃っていないとき、どこかで子の数に差ができます。
逆に葉から考えます。葉から1つ辿ったときの集合は枝の数が同じになります
したがって順次辿っていけばよいです。
辿る際に今きた枝を削除すれば、新しい頂点は葉になります
ここで根が葉になる可能性があります。
よって1つだけ上のアルゴリズムに含まないです。
これは、まず葉から分岐がない最短の先祖にいきます。
この次に辿るとき、根になりうるパスのみ条件を満たしません。
もし2以上ある場合はＮＯです。
実装してないけどたぶんとおる
E. Product Oriented Recurrence
問題：f(x)=c^(2x-3)*f(x-1)*f(x-2)*f(x-3)でf(1).f(2),f(3),cが与えられる。f(n)を求めよ
解説：
g(x)=c^x*f(x)とすると
g(x)=g(x-1)*g(x-2)*g(x-3)となる
g1、g2、g3が何回かけられるかを整理すると
g1：１，１，２，４，７…みたいに足し算で表せる
これは行列で遷移がかけるので行列累乗でlogNで計算できる。
解説と自分の解法を組み合わせた感じです
解説のやり方は英語力なさすぎてよくわからなかったです。
※実装して通せたので追記
行列累乗で指数を求めます。
ここで注意することが、普通の掛け算だと%modでよいですが、累乗の場合%mod-1になります。
オイラーの小定理よりx^(mod-1)=1 (mod mod)なので、法がズレることになります。
それはそうなんですけど指数部分をmodトルのは初めてだったので引っかかってしまいました。
それ以外は特に難しい実装はなく、ただ3*3の行列の掛け算をすればよいです。
この問題は、行列累乗に帰着するところと算数するところがネックって感じですね。
精進しても解ける気しないです。
類題があったら思い出せるようにしましょう。
