第9回日本情報オリンピック 本選 「つらら」 AOJ0551 (Icicles)

実装力も大事だけど効率のよい正しいアルゴリズムを設計する力もめっちゃくちゃ大事だと思った。

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> P;
typedef pair<int,P> PP;
int n,l,ans,d[100004];
int main(){
    scanf("%d%d",&n,&l);
    priority_queue<P,vector<P>,greater<P> > que;
    for(int i = 1;i <= n;i++){
        scanf("%d",&d[i]);
    }
 
    for(int i = 1;i <= n;i++){
        if(d[i] > d[i-1] && d[i] > d[i+1]){
            que.push(P(l-d[i],i));
        }
    }
    while(que.size()){
        P q = que.top(); que.pop();
        int ban = q.second;
        ans = q.first;
        d[ban] = 0;
        for(int i = ban-1;i <=ban+1;i++){
            if(d[i] == 0)continue;
            for(int j = -1;j <= 1;j++){
                if(j == 0)continue;
                if(d[i] < d[i+j])goto out;
            }
            que.push(P(ans+l-d[i],i));
            out:
            ;
        }
    }
 
    printf("%d\n",ans);
    return 0;
}