A. Doremy’s Paint
区間の大きさを $1$ 広げることはスコアを減らさないので，常に $(1,n)$ で最大値を達成できます．
B. Doremy’s Perfect Math Class
最大公約数 $g$ が作れることは有名です．最大値を $x$ とすると $x, x-g, x-2g, \ldots$ もこの順に作れます．
C. Doremy’s City Construction
以下種類数が $2$ 以上であるとします．
各頂点の次数の理論値を考えます．同じ種類の点とひとつでも結ぶとそれ以上結べなくなります．そうでないとき，「大きい方とだけすべて結ぶ」「小さい方とだけすべて結ぶ」のうち多い方が理論値です．種類数 $2$ 以上だとこのパターンで損することはないので，これを理論値パターンということにします．
各頂点から理論値パターンで辺をとることを考えると，矛盾せずグラフを作れることが示せます．
D. Doremy’s Pegging Game
$n$ 点残っているときにまだゲーム終了していないパターンが数えられます．全体から半平面に収まるパターンを引けばよいです．半平面の始点を固定すると簡単です．
するとちょうど $n$ 回で終わるパターンなども数えられます．
E. Doremy’s Number Line
ある地点が色 $c$ で塗れるなら，それより左の任意の地点も色 $c$ で塗る手段が存在します．よって色 $1$ で塗れる最大整数を求めればよいです．
色 $1$ は最後に使うとしてよいです．他の色だけを使ったときに塗れる最大整数を求めればよいです．
基本的には $a$ の昇順に処理すればよいですが，$a$ を降順に使って解くできるパターンとしては，「いままでに $a_i$ より大きなものを選んでいるとき，$a_i+b_i$ できる」というものがあります．
F. Doremy’s Experimental Tree
$g(i,j)=f(i,i)+f(j,j)-2f(i,j)$ を考えます．$i,j$ が隣接しているとき，これは辺重みの $N$ 倍です．
この値はパスの延長で増加する量なので，昇順に見ていって「まだ連結されてないなら辺で結ぶ」「すでに同じ連結成分なら何もしない」とすれば，辺でないものをスキップできます．
G3. Doremy’s Perfect DS Class (Hard Version)
$k=2$ であるようなクエリを主に活用します．
「$2$ で割った余りが同じ」という関係でグラフを作ると， $N/2$ 個程度のマッチングと，孤立点が $1$ 個または $2$ 個，という状態になります．孤立点の場所を特定します．
$[0,i), [i,N)$ の $2$ グループに分けてクエリすることで，左グループ内・右グループ内の辺の個数が分かります．よってグループ間の辺の個数が分かり，各グループ内にある孤立点の個数が分かります．
両方に孤立点がある場合に $1, N$ を区別するのは $k=N$ であるクエリを $1$ 回使います．
これで二分探索していきます．クエリ回数が $21$ 回になると思いますが，最後の $1$ 回を工夫すればよいです．
H. Doremy’s Paint 2
答を $K$ 個ずつ求めることにすれば，次ができればよいです：
- ペイント操作がちょうど $2K$ 個与えられる．このうち連続 $K$ 個に対する答えを求めよ．
これが $O(K\log K)$ 時間で求められれば全体 $O(M\log M)$ 時間になります．
適当な座圧により，列の長さも $O(K)$ としてよいです．
ペイント操作を左 $K$ 個，右 $K$ 個に分けて，「左 $i$ 個 + 右 $K-i$ 個」の場合の答を求めると考えます．
左側の操作は $i$ を増やしていって，素直に答を更新していきます．操作が先頭に追加されていくところがややこしいですが，初手に $[l,r]$ が加わるというのは，「l<=ANS[i]<=r となる i に対して ANS[i]:=l と更新」となるので，二分探索と区間代入でできます．
右側の操作については，普通に計算していって，各操作でどの色が残っているか（消えていくか）を求めておきます．色というのは左側操作とマージすることを踏まえて言い換えると，「初期状態でどのインデックスにあった色が残るか」を求めるということです．
右から $K-i$ 個選操作するという状況を $i$ を増やしながら見ることもできて，シミュレーションして各段階で消えた色を戻していく処理になります．
$i$ を増やしながら答えを求めます．右側で最終的に生き残るインデックスについて，左側から決まる色の種類数を数えればよいです．種類数を数えるには，直前の色と違うところの個数を数えればよいです．注目するインデックスの候補を増やしたり，区間定数代入をしたりしながらこれを適切に差分更新していけばよいです．
