コンテスト中AC:なし
A,B解説AC
A - Coprime Pair
素数の間隔(prime gap)が重要とのことです。
公式解説及び上記のwikiによれば、問題の制約における素数間の極大の間隔(maximum gap)は1500らしいです。
よって、及び
を満たす組
のうち少なくとも1つは
がいずれも素数である組が存在するということでした。
とすると、
の範囲だけ
となる組を調べれば良くなり、全探索可能になるということでした。
B - Count 1's
- コンテスト中にたどり着いた部分
連続した部分列の0の個数を、1の個数を
、初期状態における1の個数を
とすると、操作後の1の数を
にできます。
また、の最大値を
とし、その時の連続した部分列の区間を閉区間
とします。
区間が空の状態から、+1ずつ伸長してにした時、
も+1ずつしかされないので、
にできます。
最小値についても同様です。
従って、は、
を満たす全ての整数にすることができます。
以上から、に0を含むなら
が答えとなります。
0を含まないなら、空の部分列を選ぶと0にもできるので、となります。
- コンテスト中わからなかった部分
の求め方がわかりませんでした。
公式解説によれば簡単に求められるとなっていました。
閉区間の部分列に含まれる0の個数を
、1の個数を
とします。
に含まれる0の個数は
、1の個数は
です。
よって、の
は以下のように計算できます。
従って、を末尾とする連続した部分列の
が最大となるのは、
を満たす
のうち、
が最小となるもの選んだ場合です(便宜上、
)。
同様に、が最小となるのは、
が最大となるもの選んだ場合です。
よって、について、
を順次計算し、最大値と最小値を管理しておくことで、
で各
を末尾とした時の連続した部分列の
の最大・最小を求められます。
以上から、を
で求められます。