■A - Exponential or Quadratic
右辺はそのまま計算
左辺はオーバーフローするので2^min(60,n)とかで
■B - Pizza
やるだけ
■C - digitnum
1~9
10~99
100~999
に何個含まれるかを計算して適当に
■D - AND and SUM
下から決めていくとやったが、式変形するとbitごとに考えられる
x+y=(x xor y)+2(x and y)なので
x xor yの値がa-2*sで求まる。
これが負なら明らかNG
そうでないときはbitごとに考える。
(xor,and)=(1,1)のみ不可能。それ以外は全て可能
■E - Range Sums
これ区間のxorをどうするのか延々と考えてましたが
区間を辺にして頂点0から頂点nにたどり着けるかどうか
なので辺を貼ってbfsをするか、dsuを行う。
■F - Two Exams
pの出来でソートする
dp[i][j][k]:=i番目まで、j人選んだ、選んでない人らの最小値がk
として採用できるならする(kより今見ている人が小さい)or採用しないで遷移
■G - Cubic?
ハッシュという概念
a,b,a^b,a,b,a^bとすれば長さが３の倍数の区間を選択したときにのみ０になる(a,b,a^bは0じゃないとして)
各素数ごとにpa,pbを割り当てれば累積和と同じ手法になる。なるほどね
uint_fast64_t seed = 202202052100123456;
mt19937_64 engine(seed);
uint_fast64_t = engine();
とすれば乱数を使える
■Ex - Removing People
逆から考える
何もない状態から初めて、取り除かれたものを戻していく。
dp[i][j]:=iとjに人がいて、その間(時計回り)には誰もいない。
その場合状態から間を並べるcostの合計と、その状態にするまでの通り数
とすると遷移ができる
