第13回日本情報オリンピック本選 C
JOI本選の問題
予選の問題はいくつか解いたことがあるが，本選の問題で解けそうなのないかな〜と思い色々探していたら，この問題を見つけた．
結論からいうと定石の解法の組み合わせで特にすごい発想の転換とかはせずに解くことができた．(クソザコなので時間はめちゃくちゃかかったが)
問題
JOI 君は妹の JOI 子ちゃんと JOI 美ちゃんと一緒におやつを食べようとしている．今日のおやつは3人の大好物のバームクーヘンだ．バームクーヘンは下図のような円筒形のお菓子である．3人に分けるために，JOI 君は半径向に刃を3回入れて，これを3つのピースに切り分けなければならない．ただしこのバームクーヘンは本物の木材のように固いので，刃を入れるのは簡単ではない．そのためこのバームクーヘンにはあらかじめN個の切れ込みが入っており，JOI 君は切れ込みのある位置でのみ切ることができる．切れ込みに$1$から$N$まで時計回りに番号をふったとき，$1≦i≦N−1$に対し，$i$番目の切れ込みと$i+1$番目の切れ込みの間の部分の大きさは$A_i$である．また$N$番目の切れ込みと$1$番目の切れ込みの間の部分の大きさは$A_N$である．
図 1: バームクーヘンの例 $N=6,A_1=1,A_2=5,A_3=4,A_4=5,A_5=2,A_6=4$妹思いの JOI 君は，バームクーヘンを3つのピースに切り分けたあと，自分は最も小さいピースを選び，残りの2つのピースを2人の妹にあげることにした．一方で，JOI 君はバームクーヘンが大好物なので，できるだけたくさん食べたいと思っている．最も小さいピースの大きさが最大になるように切ったとき，JOI 君が食べることになるピースの大きさはいくらになるだろうか．
思考
とりあえず最小値の最大値を求める問題なので，
条件$C(x)$:各ピースの大きさがx以上にできる
としたときに，あるところから右側で$C(x)$がtrue，左側でfalse
となるように二分探索すればいいということは想像できる．
問題はこの$C(x)$の部分をどう書くかだと思うが，全探索は間に合わないし，累積和でいけるかな？と思ったがちょっと詰まってしまった．
しかし
ある数列の部分列で総和が〜以上となる区間を求めよ
という問題の常套手段としてしゃくとり法が使えることを思い出すと，
最初の切り込みを入れる位置をN通り試す${\mathcal O}(N)$でいけそうだ．
実装
#include <iostream>
#include <vector>
using namespace std;
int main(){
int N;
cin >> N;
vector<long long> a(2*N);
long long tot = 0 ;
for(int i=0; i< N; i++){
cin >> a[i] , a[i+N] = a[i] , tot +=a[i];
}
long long lb = 0, ub = 1ll<<60 ;
while (ub -lb > 1){
long long mid = lb + (ub - lb)/2;
/*しゃくとり法の実装*/
vector<int> nextcut(N,-1) ; /*nextcut[i]にiで切ったときに総和がmid以上になる次の切り込み位置を収納*/
vector<long long> Size(N,-1) ;
int right = 0;
long long sum = 0;
for(int left = 0; left < N; left++){
while(right < 2*N && sum < mid){
sum += a[right] ;
right++ ;
}
if (sum >= mid){
nextcut[left] = right ;
Size[left] =sum;
}
if (right == left){
right ++ ;
}
else sum -= a[left];
}
bool check = false; /*条件判定部分*/
for(int i=0; i < N; i++){
int second_cut = nextcut[i];
if (second_cut == -1) continue ;
if (Size[i] >= tot) continue ;
second_cut %=N ;
int third_cut = nextcut[second_cut];
if (third_cut == -1) continue;
if (tot - Size[i] -Size[second_cut] >= mid) check = true;
}
if (!check) ub = mid;
else lb = mid;
}
cout << lb << endl;
}
感想
細かいところで色々と間違ってWAを連発してしまった．このレベルの問題を時間内にポンポン解いていくランカー達にはほんと尊敬しかない．
自分にも弟妹がいるので，木材のように硬くて切れ込みが入ったバームクーヘンを分けることがあったらこの通りにしようと思う．