A. Consecutive Integers

区間を覆う問題は何度か解いたので記憶していた．図を描けばわかりやすい． 解答例

選ぶ連続した整数を区間と見る．例えば$N=8,K=3$のとき， ooo..... のようになり，'.'の数だけ区間を右にずらせる．'.'の数は$N-K$であるから，答えは初期位置も含めて$N-K+1$．

B. RGB Boxes

解答例

各色について買う箱の個数を決め打ちすることを考える：例えば赤ならそれぞれ$0$個以上$\lfloor N/R \rfloor$個以下^[1]（$G,B$も同様）．これだと$O(N^{3})$であり間に合わないが，2種類だけ決めれば残りに必要な箱の個数は求まる：箱の個数をそれぞれ$r,g,b$とおくと$b=\frac {N-(rR+gG)} {B}$．これが割り切れかつ先の範囲内でなければならない．この方針なら$O(N^2)$であるから間に合う．

ところでeditorialがそうしているように$r,g$の上限は$N$でも，$N$の上限の$3000$でもよい（どうせ$b$が負になるため）．

C. AB Substrings

コーナーケースに引っ掛かっていると思って色々試行錯誤した挙句元々の解法が間違っていた． 解答例

まず各文字列の中のABの個数を数える．次に末尾にAや，先頭にBがあるものを組み合わせてABが作れることに注意する（文字列の中のABとは重ならないので安心）．両方を兼ね備える文字列に注意：パターンBAとおく．そうでなく末尾にA，先頭にBがあるものをそれぞれパターンXA, BXとおく．これらの組み合わせ方を考えたい（どちらでもないパターンはどう組み合わせても意味が無いので以下無視する）．

はじめばXAとBX，およびBAをそれぞれ独立に組み合わせた後で合体させればよいと考えていたが，誤りである：例えばBA=3,XA=2,BX=2のとき，XABX+XABX+BABABAとなって5個であるが，最適なのはXABX+XA+BABABA+BXの6個である．このようにBA...BAの先頭および末尾にあるB,Aを活用してそこにXA, BXを組み合わせたほうが得をする．

以上より：

• BAがあるとき：
  • BA...BAの中にABは$\text{BA}-1$個
  • さらに両側にそれぞれXA, BXを追加できる
    • XA, BXのそれぞれについて，それが1個以上あればABが1個増える（XA, BXも1個減る）．これらは破壊的に更新されたとする．
  • 余ったXA, BX同士を組み合わせてXABX...XABXを作る：ABは$\min \{\text{XA}, \text{BX}\}$個
  • 従って$\text{AB} + \text{BA} - 1 + \min \{\text{XA}, \text{BX}\}$
• BAがないとき：
  • XA, BXの組み合わせのみ．従って$\text{AB} + \min \{\text{XA}, \text{BX}\}$

文字列の中の特定文字列の個数を数える関数が見当たらなかったので適当な実装をした．最初はStr.split結果のlengthから1引いたものとしていたが，JavaScriptなどと異なりこれは特定文字列が先頭や末尾にある場合に空文字列が入らないためズレてしまう^[2]．そこで単純にループによる数え上げで実装した．あるいは検索対象の先頭に適当な文字（例えば本問では小文字は出ない）を入れたり，JavaScript版を再現したりすれば大丈夫．

D. DivRem Number

感触は300点，数学要素も考慮すると簡単目な400点問題な気がする． 解答例

500点問題ということで最初数分は難しく考えすぎてしまったが，素直に$N=pm+q$と表示すればよい：$p=\lfloor \frac {N} {m} \rfloor$，$q=N \bmod m$．これらが等しくなるような$m$を求めたい：$N=pm+p=p(m+1)$．よって$N$の約数$d$が分かれば$m$の候補$m = d - 1$が得られる．あとは元々の条件$\lfloor N/m \rfloor = N \bmod m$を確かめればよい（$0$除算にならないように注意）．

---

1. 一応証明しておく．$N=pR+q\ (0 \le q \lt p)$とおくと$p=\lfloor N/R \rfloor$．このとき$pR \le N = pR+q$ $\lt pR+p = (p+1) R$であるから，$\lfloor N/R \rfloor + 1$個以上は買えない． ↩︎

2. "abxabyab"を"ab"でsplitする場合，JavaScriptでは["","x","y",""]となるが，OCamlでは["x","y"]となる． ↩︎