精進メモ 2021/04/19~ - ツバサの備忘録

競プロ典型 90 問
yukicoder contest 292
ABC199

競プロ典型 90 問

問題
day1 ~ 19まで解くつもりでした。
day5の課題3だけ~~解けていません~~解説ACしました。難しいですね…

yukicoder contest 292

yukicoder contest 292 - yukicoder

No.1487 ぺんぎんさんかっけー

こういうのは半分！って思ってサンプルが合わなくて泣いていました。
サンプルが何倍になっているかを確認すると、4分の1になっています。面積の場合は二乗をかけなければなりませんでした。
厳密には証明していないので次も解けるかと言われると…

No.1488 Max Score of the Tree

それぞれの辺が答えに何回分寄与するかは、木DPをすることで求められます。
あとは、重さが辺の長さ、価値が長さ×寄与する回数、としたナップサックを計算すれば良いです。実装はそこまで軽くありませんが、結構好きな問題でした。

No.1489 Repeat Cumulative Sum

最終問より難しいと感じました。それぞれの数列の要素が足される回数を求めればよいです。考察を進めると、
$\displaystyle \sum_{i = 0}^{R}\sum_{j = 0}^{M} \ _{i + j}C_{i} + 1$
を求めればいいことがわかります。
数え上げPDFを見ると、
$_{R + M + 2}C_{R +1}$
と変形できることがわかるので、 $R$ を動かしながら値を求めていけばいいことがわかります。 $R$ が増えても、増える前の値を利用すれば $O(1)$ で更新ができるので、十分間に合います。

No.1490 スライムと爆弾

爆弾はいもす法を用いて長方形の範囲にダメージをメモします。
あとは、このメモの二次元累積和をとり、スライムのいる範囲それぞれについてダメージの総和を計算できれば良いです。実装頑張る系問題でした。

ABC199

Tasks - AtCoder Beginner Contest 199（Sponsored by Panasonic）

D - RGB Coloring 2

この問題好きです。
まず、連結成分ごとに考えて、最後に積を取ればいいことがわかるので、連結成分1つに対する答えがわかれば良いです。
しかし、何も考えないと、 $O(3^{N})$ が計算量にかかわってくるように見えます。
しかし、連結成分の頂点の一つの色を決めると、既に決まった頂点の隣から色を決めていくことにすれば、残りの頂点は全て(少なくとも)2通り以下になります。なので、 $O(2^{N})$ に計算量が落ちました。
全体で $O(M2^{N})$ です。