kwm_t

kwm_tのメモ

ARC122

■A - Many Formulae
単純なdp
dp[i][j] = {x,y}:=i番目まで見て、最後に使った符号がj(0=+,1=-)
な選び方がx通り、総和がy

■B - Insurance
保険とか言われると問題の意味がさっぱりわからなくなる。
要するにΣmax(x-a,-x)の最小値がわかればいい。
これは、ABC127:F - Absolute Minima

■C - Calculator
こういうの解ける気がしない。
問題見た瞬間に諦めてしまってる。
フィボナッチになることは明らか。
線形性より適当なタイミングで+1の操作を行っても結果が簡単。
後ろから考えれば良い

■D - XOR Game
どうせ解けないと思いながら、適当にやってたら割と惜しいとこまでいってた
後は気合。
上のビットから見ていく。
1.立っている本数が偶数本なら、
そのビットが立っている者同士(寝ているもの同士)組み合われればよい。
それぞれグループ分けして次のビットを見ていく。

2.立っている本数が奇数本なら、そのビットは使うしか無い。
それ以降は、そのビットが立つ組み合わせの中での最小値を探していけば良い。

再帰関数を2つ用意する必要がある。

■E - Increasing LCMs
後ろから貪欲に考える。
集合Sがあったときに、その中の要素xを最後尾に持ってきていい条件はなにかを考える。
オーバーフローに注意。