700点3問
C - Sequence Growing Easy
問題：すべて0の数列XのX(i+1)=Xi+1にする操作を好きなだけできる。数列Aiを実現する最小操作回数を求めよ
考察：
逆順に見ます。
操作：Ai+1==A(i+1)のとき、A(i+1)を好きな要素に変える。
全て0にしたい。
もしA(i+1)>=Ai+2のとき実現不可能です。
順にAi以前の要素を多くしたとしても、最後は0,2などとなり、0を増やすことはできないので不可能です。
よって増加する場合は+1の必要があります。
また、A0==0の必要があります。
Ai>=A(i+1)であるときを考えます。
このときAiをA(i+1)-1に置き換える必要があります。これが1以上のときは操作を2回必要とすることがわかります。なぜならA(i+1)-1にしたあと0にする操作が必要だからです。
このことを踏まえると、A(i+1)回操作が加わることになります。
以上を実装すればよいです。
E - Connected?
問題：x方向[0,r]、y方向[0,c]の範囲の長方形の周上含む内部に２ｎ個の点がある。2*iと2*i+1個目の点を曲線で結ぶ。長方形の外に曲線がでないように、またｎ本の曲線が交わらないように結ぶことはできるか。
考察：
まず、両方が周上にある場合だけを考えればよいです。
周上と隙間がある場合そこを通って結ぶことが可能です。
1周して順に何番目の頂点かを並べます。このときｘｙｘｙの並びになっていたら不可能です。
同じ組が隣接していれば必ず結ぶことができます。その後その頂点対は考えなくてよいです。
前から要素を追加していき、1つ前の要素と一致すればpopします。
最後に残った要素が2より大きい場合NOです。
vectorで簡単に実装可能です。
E - guruguru
問題：明るさは１，２、…m、１と循環で1ずつ変えられる。またお気に入りの値xに1回で変えられる。a1からanまで順に明るさを変えたいとき、操作回数を最小化するxを決め、操作回数を求めよ
考察：
まず後者の操作を無視して考えます。
この時各操作で
a[i] => a[i+1]
a[i] => a[i+1] + m
の2通りが考えられます。
x=a[i] + 2のとき2回かかる操作が1回になるので1回得します。
この要領で考えるとあるxベクトルを考え、a[i] => a[i+1]について
区間[a[i]+2,a[i+1]] に 1，2、…を足すというクエリを処理します。
このxの最大値分、操作を削減することができます。
このクエリ処理問題に帰着できました。
これはイベント処理のように解くことができます。
はじめにクエリを始点の昇順に並べておきます。
そして1~2mまで見ていくとき、いま所持するクエリの数と、いまある効用の大きさを持ちます。また、各クエリの(終点、長さ)を終点の昇順で持ちます。
以下のアルゴリズムを実行します。
1：始点と一致するようなクエリ分、所持数を増やす。
2：所持してるクエリの数、効用を増やす。
3：終点に達しているなら、効用から長さを引く
各ステップでx[i%m]に効用を足せばよいです。
以上でO*1で解くことができました。
実装かなりキツめでしたが、通せてうれしかったです。
*1:M+N)log(N
