コンテスト中AC:なし
A,B解説AC

A - Coprime Pair

公式解説

素数の間隔(prime gap)が重要とのことです。

素数の間隔 - Wikipedia

公式解説及び上記のwikiによれば、問題の制約における素数間の極大の間隔(maximum gap)は1500らしいです。

よって、 $L\leq x \leq L+1500$ 及び $R-1500 \leq y \leq R$ を満たす組 $(x,y)$ のうち少なくとも1つは $x,y$ がいずれも素数である組が存在するということでした。

$d=y-x$ とすると、 $R-L-3000\leq d \leq R-L$ の範囲だけ $gcd(x,y)=1$ となる組を調べれば良くなり、全探索可能になるということでした。

提出コード

B - Count 1's

コンテスト中にたどり着いた部分

連続した部分列の0の個数を $S^0$ 、1の個数を $S^1$ 、初期状態における1の個数を $X$ とすると、操作後の1の数を $X+S^0 - S^1$ にできます。

また、 $S=S^0 - S^1$ の最大値を $S_{max}$ とし、その時の連続した部分列の区間を閉区間 $[l,r]$ とします。

区間が空の状態から、+1ずつ伸長して $[l,r]$ にした時、 $S$ も+1ずつしかされないので、 $S=0,1,\cdots ,S_{max}$ にできます。

最小値 $S_{min}$ についても同様です。
従って、 $S$ は、 $S_{min}\leq S \leq S_{max}$ を満たす全ての整数にすることができます。

以上から、 $S_{min}\leq S \leq S_{max}$ に0を含むなら $S_{max} - S_{min} +1$ が答えとなります。
0を含まないなら、空の部分列を選ぶと0にもできるので、 $S_{max} - S_{min} +2$ となります。

コンテスト中わからなかった部分

$S_{min},\ S_{max}$ の求め方がわかりませんでした。
公式解説によれば簡単に求められるとなっていました。

閉区間 $[1,i]$ の部分列に含まれる0の個数を $S^0_i$ 、1の個数を $S^1_i$ とします。

$[i,j]$ に含まれる0の個数は $S^0_i - S^0_{j-1}$ 、1の個数は $S^1_i - S^1_{j-1}$ です。
よって、 $[i,j]$ の $S^0 - S^1$ は以下のように計算できます。
$S^0_i - S^0_{j-1} - (S^1_i - S^1_{j-1}) = S^0_i - S^1_i - (S^0_{j-1} - S^1_{j-1})$

従って、 $i$ を末尾とする連続した部分列の $S^0 - S^1$ が最大となるのは、 $0\leq j \lt i$ を満たす $j$ のうち、 $S^0_j - S^1_{j}$ が最小となるもの選んだ場合です(便宜上、 $S^0_0 - S^1_0= 0$ )。
同様に、 $S^0 - S^1$ が最小となるのは、 $S^0_j - S^1_{j}$ が最大となるもの選んだ場合です。