■161F - Division or Subtraction
N = 1+ nk を満たす２以上のもの
N = (nk+1)*k^n
■162F - Select Half
ナップサック
dp[i][j]:=i番目まで見た、j個を条件を満たすように採用した
だとO(n^2)かかる
問題条件より、一つ空けて選ぶこと＋ほぼ半分選ぶなので
上のdpの遷移には無駄が大量にある。
遷移の際に、捨てていい情報か残す情報かどうか判断した上で遷移する。
■163F - path pass i
マージテク
橙diffだけどマージテクをやるだけ。
dfsをして根っこの頂点から順々に
その頂点にぶら下がっている部分木ごとに
同じ色の頂点よりある子頂点の数がわかればいい。
■164F - I hate Matrix Construction
ビットごとに考える。
条件より和が０及び、積が１なら確定するので確定する場所は全部埋める。
確定と確定が相反していても、一旦埋める。
すると未確定ゾーンをかき集めると長方形になる。
これらは縦横ともに、どれか一つが０orどれか一つが１のいずれか。
長方形の縦横がともに２より多きければ式松模様上に塗れば良い。
そうでないときは縦か横のいずれかが１(0のときは残ってないので)
縦が１なら横の成約を優先して埋める。
既に横の成約が満たされていれば縦の制約に従う。
逆も同様。
こうしてすべて埋まった状態で条件を満たしているかを確かめる。
問題があれば-1、問題がなければ次のビットを考える。
■165F - LIS on Tree
LISはセグ木を使えば求まる。
dfsで進んでいくたびにセグ木が更新されるが親に戻る時に更新したものを戻せば問題はない。
