Aizu Online Judge in C++ #Volume21 - 2104 : Country Road

Aizu Online Judge（AOJ）の過去問から、その提出コードの解答例です。

・問題 "Country Road"
https://onlinejudge.u-aizu.ac.jp/problems/2104
・カントリーロード
僕が作成、提出したコードは、以下のとおりです。

・Aizu Online Judge in C++ #Volume21 - 2104 : Country Road

/*
Aizu Online Judge in C++ #Volume21 - 2104 : Country Road
 https://onlinejudge.u-aizu.ac.jp/problems/2104
 提出コードの解答例
 https://neguse-atama.hatenablog.com
*/
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
int main(void){
    ll t,n,k,x[100010];
    cin>>t;
    while(t--){
        cin>>n>>k;
        vector<ll> v;
        for(ll i=0;i<n;i++){
            cin>>x[i];
        }
        for(ll i=1;i<n;i++){
            v.push_back(x[i]-x[i-1]);
        }
        sort(v.rbegin(),v.rend());
        ll sum=0,p;
        for(ll i=0;i<k-1;i++){
            if(i>=v.size()){
                break;
            }
            sum+=v[i];
        }
        p=x[n-1]-x[0]-sum;
        if(p<0){
            p=0;
        }
        cout<<p<<endl;
    }
    return 0;
}

設問の出典は、プログラミング問題のオンライン採点システム「Aizu Online Judge（AOJ）」です。
http://judge.u-aizu.ac.jp/onlinejudge/

paizaラーニング: C++による「ソートメニュー応用編」問題集: 区間のソート

paizaラーニングのレベルアップ問題集「ソートメニュー応用編」からの出典です。
paiza.jp
C++による「ソートメニュー応用編」問題集: 区間のソートと、それらの提出コードの解答例です。

僕が作成、提出したコードは、以下のとおりです。

・STEP: 1 ソートの基本

paiza.jp

/*
paizaラーニング: C++による「ソートメニュー応用編」問題集: 区間のソート
STEP: 1 ソートの基本
https://paiza.jp/works/mondai/sort_advanced/sort_advanced__problems_simple_step0
提出コードの解答例
https://neguse-atama.hatenablog.com
*/
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
int main(void){
    ll n;
    cin>>n;
    vector<ll> a(n),v(n);
    for(ll i=0;i<n;i++){
        cin>>a[i];
        v[i]=a[i];
    }
    sort(v.begin(),v.end());
    if(a==v){
        cout<<"Yes\n";
    }else{
        cout<<"No\n";
    }
    return 0;
}

・STEP: 2 最大最小

paiza.jp

/*
paizaラーニング: C++による「ソートメニュー応用編」問題集: 区間のソート
STEP: 2 最大最小
https://paiza.jp/works/mondai/sort_advanced/sort_advanced__problems_simple_step1
提出コードの解答例
https://neguse-atama.hatenablog.com
*/
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
int main(void){
    ll n;
    cin>>n;
    ll MAX=-10000,MIN=10000;
    for(ll i=0;i<n;i++){
        ll a;
        cin>>a;
        MAX=max(MAX,a);
        MIN=min(MIN,a);
    }
    cout<<MAX<<" "<<MIN<<endl;
    return 0;
}

・STEP: 3 Top - k (easy)

paiza.jp

/*
paizaラーニング: C++による「ソートメニュー応用編」問題集: 区間のソート
STEP: 3 Top - k (easy)
https://paiza.jp/works/mondai/sort_advanced/sort_advanced__problems_simple_step2
提出コードの解答例
https://neguse-atama.hatenablog.com
*/
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
int main(void){
    ll n,k;
    cin>>n>>k;
    vector<ll> a(n);
    for(ll i=0;i<n;i++){
        cin>>a[i];
    }
    sort(a.rbegin(),a.rend());
    cout<<a[k-1]<<endl;
    return 0;
}

・STEP: 4 重複削除

paiza.jp

/*
paizaラーニング: C++による「ソートメニュー応用編」問題集: 区間のソート
STEP: 4 重複削除
https://paiza.jp/works/mondai/sort_advanced/sort_advanced__problems_simple_step3
提出コードの解答例
https://neguse-atama.hatenablog.com
*/
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
int main(void){
    ll n;
    cin>>n;
    vector<ll> a;
    for(ll i=0;i<n;i++){
        ll A;cin>>A;
        a.push_back(A);
    }
    sort(a.begin(),a.end());
    a.erase(unique(a.begin(),a.end()),a.end());
    for(ll i=0;i<a.size();i++){
        cout<<a[i]<<(i==a.size()-1 ? "\n" : " ");
    }
    return 0;
}

・FINAL問題: 区間のソート

paiza.jp

/*
paizaラーニング: C++による「ソートメニュー応用編」問題集: 区間のソート
FINAL問題: 区間のソート
https://paiza.jp/works/mondai/sort_advanced/sort_advanced__problems_simple_boss
提出コードの解答例
https://neguse-atama.hatenablog.com
*/
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
int main(void){
    ll n,l,r;
    cin>>n>>l>>r;
    l--;
    r--;
    vector<ll> a(n);
    for(ll i=0;i<n;i++){
        cin>>a[i];
    }
    sort(a.begin()+l,a.begin()+r);
    for(ll i=0;i<n;i++){
        cout<<a[i]<<(i==n-1 ? "\n" : " ");
    }
    return 0;
}

paizaラーニングのレベルアップ問題集については、ユーザー同士で解答を教え合ったり、コードを公開したりするのは自由としています。
また授業や研修、教材などにも利用できるそうです。

Aizu Online Judge in C++ #Volume26 : 2601 - Evacuation Route

Aizu Online Judge（AOJ）の過去問から、その提出コードの解答例です。

・問題 "Evacuation Route"
https://onlinejudge.u-aizu.ac.jp/problems/2601
・避難経路
僕が作成、提出したコードは、以下のとおりです。

・Aizu Online Judge in C++ #Volume26 - 2601 : Evacuation Route

/*
Aizu Online Judge in C++ #Volume26 - 2601 : Evacuation Route
 https://onlinejudge.u-aizu.ac.jp/problems/2601
 提出コードの解答例
 https://neguse-atama.hatenablog.com
*/
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const ll N=1<<17;
ll w,a[N],l[N],r[N];
int main(void){
    cin>>w;
    for(ll i=0;i<w;i++){
        cin>>a[i];
    }
    l[0]=(a[0]==0 ? 1e9 : 0);
    for(ll i=1;i<w;i++){
        l[i]=(a[i]==0 ? 1e9 : (a[i]<0 ? min(-a[i],max(l[i-1]-1,0LL)) : max(l[i-1]-1,0LL)));
    }
    r[w-1]=(a[w-1]==0 ? 1e9 : 0);
    for(ll i=w-1;i--;){
        r[i]=(a[i]==0 ? 1e9 : (a[i]<0 ? min(-a[i],max(r[i+1]-1,0LL)) : max(r[i+1]-1,0LL)));
    }
    ll ans=0;
    for(ll i=0;i<w;i++){
        if(a[i]>0){
            ans+=min(a[i],max(l[i],r[i]));
        }
    }
    cout<<ans<<endl;
    return 0;
}

設問の出典は、プログラミング問題のオンライン採点システム「Aizu Online Judge（AOJ）」です。
http://judge.u-aizu.ac.jp/onlinejudge/