精進メモ 2021/06/07~ - ツバサの備忘録

競プロ典型 90 問

060 - Chimera（★5）

右からと左からでLISを求めていけばいいです。
LIS(典型) + 左右からみる(典型)で割と好きです。

061 - Deck（★2）

vectorを二本持ちました。
添え字に脳みそをやられて時間がかかりましたがなんとかノーペナです。

062 - Paint All（★6）

$i$ から $A_{i}$ 、 $B_{i}$ に辺をはると、BFSで解くことができます。
$i = A_{i},i = B_{i}$ となっている頂点群を始点とすればいいです。

063 - Monochromatic Subgrid（★4）

選ぶ行をビット全探索します。チェックやカウントは愚直でいいです。

063 - Monochromatic Subgrid（★4）

階差を取って差分更新です。

ARC122

Dが間に合わなくて悔しいです。Eも見ておくべきでした。

A - Many Formulae

ある値について正負を決めた時、右と左のパターン数をかけてあげればよいです。パターン数はDPで計算できます。

B - Insurance

$x = A_{i} / 2$ を全探索すればいいです。
中途半端な $x$ についてはどちらかに寄せると値が小さくなります。

C - Calculator

操作3,4を繰り返すと出現する値はフィボナッチになります。
途中で操作1,2を割り込ませて、その操作に対する寄与をうまく考えればいいです。

D - XOR Game

大きいビットから貪欲に、再帰的に決めていけばいいです。
一番上のビットが0,1それぞれ偶数であった場合、それぞれのグループの同士で組み合わせにしたときの最大値が答えです。
そうでない場合、0のものと1のものをペアにしたものの最小値が答えです。
この後は、2つのグループを持ちながら再帰的に解きます。
このパートも、ほぼ似たようなことをすればいいです。