ARC106 C - Solutions (500)
$ m = 0の場合、全ての区間が重ならないように配置することで明らかに構築できる
$ m \ge n - 1の場合、基本的に構築できない
青木君のプログラムでは最低でも$ 1を出力し、その場合に高橋君のプログラムでは$ N-1が最大なので$ N-1-1 = N-2より大きくできない
ただし、$ N=1,M=0の場合はどのように配置しても構築できるので注意
$ m \lt 0の場合、構築できない
高橋君のプログラムだとその点を取らなかったとしても取れるようになる点が高々1つなのでこれより良い方法が無いように見える
それ以外は以下のように構築できる
端から端までを多く区間を作る
m個をその中で他のと重ならないように配置する
残り$ n-m-1個は全て同じサイズで1ずつずらして配置する
青木君のプログラムでは端から端まで覆う1つだけが選ばれる
高橋君のプログラムではm個の重ならないように配置した区間と、$ n-m-1個の内1つが選ばれる
n個の区間を配置するだけなので$ O(N)