Beta Round #61-E: Petya and Post

問題概要

N(<10^5)個の郵便局が環状にならんでいる。a[i]はi番目の郵便局で補給できるガソリンの量、d[i]はi番目からi+1番目の郵便局に行くのに必要なガソリンの量。aの和とdの和は等しい。ガソリンが0の状態から1周回って戻ってくるにはどこから出発すればよいか全て求める問題。時計回りも反時計回りも考慮する。

解法

時計回りと反時計回りは別々に考える。とりあえず時計回りだけ考えよう。c[i]を、0からスタートしてiにたどり着くのにどれだけ燃料が余るか(正負を込めて)、とする。このとき、cの最小値をアテインするようなiをスタート地点として選べる。反時計回りもまったく同様にできる。

感想

最小値の個数探すだけでよかったのに頭の中で整理できてなかったから最初は無駄にRMQとか使ってしまった。結局RMQを使った方のコードは思いついてからテストをパスするまで1時間45分位かかった。整理した後も書き直すのに15分くらいかかったから実装の遅さがいよいよ深刻なものになりつつある。

#include <stdio.h>

#define MAX_N 100009

int as[MAX_N], ds[MAX_N], ccs[MAX_N], cs[MAX_N];
int oks[MAX_N];
int N;

void solve(){
    int i, min = 1<<30;
    for(i=0;i<N;i++){
        cs[(i+1)%N] = (cs[i] + as[i] - ds[i]);
        if(min > cs[(i+1)%N]) min = cs[(i+1)%N];
    }
    for(i=0;i<N;i++)if(min==cs[i])oks[i] = 1;
    min = 1<<30;
    for(i=N-1;i>=0;i--){
        ccs[i] = (ccs[(i+1)%N] + as[(i+1)%N] - ds[i]);
        if(min > ccs[i]) min = ccs[i];
    }
    for(i=0;i<N;i++)if(min==ccs[i])oks[i] = 1;
}

int main(){
    int i,k=0;
    scanf("%d",&N);
    for(i=0;i<N;i++)scanf("%d",as+i);
    for(i=0;i<N;i++)scanf("%d",ds+i);
    solve();
    for(i=0;i<N;i++)if(oks[i])k++;
    printf("%d\n",k);
    for(i=0;i<N;i++)if(oks[i]){
        printf("%d%c",i+1,--k?' ':'\n');
    }
    return 0;
}