Atcoder Beginner Contest #116 ~ #129のCD問題をすべて解いた。 また、#126 ~ #129についてはEF問題が追加されているので、すべて解いた。 F問題は、解説PDF、解説Youtube、解説ブログを参考にした。
ABC #126 F - XOR Matching
https://atcoder.jp/contests/abc126/submissions/5909511
M=3とすると、長さ2^(M+1)の数列は、{0,0,1,1,2,2,3,3,4,4,5,5,6,6,7,7}のような要素をもつ。
このとき、{<0,1,...,7からKを除いた昇順の数列> K <7,6,...,0>からKを除いた降順の数列 K}とすれば良い。
K以外の要素について：間にはKだけが残ることになるので、条件を満すKについて：間には<7,6,...,0>からKを除いた降順の数列が残る。XORをとるとKになるので条件を満たす。
ABC #127 F - Absolute Minima
https://atcoder.jp/contests/abc127/submissions/5930963
中央値が最小値となる性質を利用する。中央値が２つあるときには、左側を採用する。
中央値は、小さいほうと大きいほうをそれぞれ優先度付きキューで管理すると便利。
解説動画では、同一のaを二度入れてキュー間で交換するテクニックを使っていたが、
ナイーブに一度だけ入れる方法でも問題ない。
キューが片方に偏らないように、整理する必要がある。
更新クエリのとき、aが最小値を取る区間のなかに含まれていれば、最小値の更新はない。
一方、含まれていなければ、最小値を取る区間のなかで、最も近い点との差分を、最小値に追加する。
ABC #128 F - Frog Jump
https://atcoder.jp/contests/abc128/submissions/5921198
A、Bをそのまま扱うのではなく、C=A-B と k=何度戻りが発生するか という変数に置き換えて考える。
Cを固定すると、kが増えるにつれて、蓮を多く踏めるようになる。
同一の蓮を二度以上通るかどうかは、単純にsetで管理した。
ABC #129 F - Takahashi’s Basics in Education and Learning
https://atcoder.jp/contests/abc129/submissions/5945816
難しかった。まず、等差数列の各要素が何桁なのかによって、分割する。たとえば、A=3、B=4であれば、3,7と11,15,19に分けて考える。分割後は、sum_i=0^(l-1) (A+Bi)*10^k^(l-i-1)を求めることになる。
A sum_i=0^(l-1) 10^k^iとB sum_i=0^(l-1) i*10^k^(l-i-1)にわけて、計算する。
どちらも漸化式に変換して解く（コード中のf,gに対応）。
解説動画を見るのがおすすめ。
