JOI2018予選 解説

はじめに

第18回情報オリンピック予選のA~Eをどうやって解いたかを書いておきます
コンテスト中の感じは参加記を見てください

A問題 ソーシャルゲーム

概要

自分で調べてください

解法

一日ずつシミュレートします.数式でえいしたらWAだったので

ソースコード

#include<bits/stdc++.h>
using namespace std;
#define FOR(i,n,m) for(int i=(n);i<(m);i++)
#define REP(i,n) FOR(i,0,n)
#define all(vec) vec.begin(),vec.end()
using ll=long long;
using vi=vector<int>;
using vvi=vector<vi>;
using vl=vector<ll>;
using vvl=vector<vl>;
using P=pair<int,int>;
using PP=pair<int,P>;
#define pb push_back
#define fi first
#define se second
const int MOD=1e9+7;
const int INF=1e9;
const ll LINF=1LL<<60;
template<class T>bool chmax(T &a,const T &b){if(a<b){a=b;return true;}return false;}
template<class T>bool chmin(T &a,const T &b){if(a>b){a=b;return true;}return false;}
int main(){
    int a,b,c;
    cin>>a>>b>>c;
    int ans=0;
    while(c>0){
        c-=a;
        if(ans%7==6){
            c-=b;
        }
        ans++;
    }
    cout<<ans<<endl;
    return 0;
}

B問題 すごろくと駒

解法

シミュレーションします.駒の座標をsetで持つと面倒なことを考える必要がなくなる

ソースコード

#include<bits/stdc++.h>
using namespace std;
#define FOR(i,n,m) for(int i=(n);i<(m);i++)
#define REP(i,n) FOR(i,0,n)
#define all(vec) vec.begin(),vec.end()
using ll=long long;
using vi=vector<int>;
using vvi=vector<vi>;
using vl=vector<ll>;
using vvl=vector<vl>;
using P=pair<int,int>;
using PP=pair<int,P>;
#define pb push_back
#define fi first
#define se second
const int MOD=1e9+7;
const int INF=1e9;
const ll LINF=1LL<<60;
template<class T>bool chmax(T &a,const T &b){if(a<b){a=b;return true;}return false;}
template<class T>bool chmin(T &a,const T &b){if(a>b){a=b;return true;}return false;}
int main(){
    int n;
    cin>>n;
    vi a(n);
    set<int> se;
    REP(i,n){
        cin>>a[i];
        se.insert(a[i]);
    }
    int m;
    cin>>m;
    REP(i,m){
        int k;
        cin>>k;
        k--;
        if(a[k]!=2019&&!se.count(a[k]+1)){
            se.erase(a[k]);
            a[k]++;
            se.insert(a[k]);
        }
    }
    REP(i,n){
        cout<<a[i]<<endl;
    }

    return 0;
}

C問題 マルバツスタンプ

解法

前から順番にそれがマルバツだったら答えを1増やす貪欲をします.
一応それでいい証明をしておくと,もしx個目を無視してx+1個目を代わりに使っても良くなることはないです(悪くなることはあります)
なぜなら,xを使うと次はx+2から見ますが代わりにx+1を使うと次はx+3から見ることになり,x+2から見たときのmaxがx+3から見たときのmaxより大きくなることはないからです.
以上より前から貪欲でOKです

ソースコード

#include<bits/stdc++.h>
using namespace std;
#define FOR(i,n,m) for(int i=(n);i<(m);i++)
#define REP(i,n) FOR(i,0,n)
#define all(vec) vec.begin(),vec.end()
using ll=long long;
using vi=vector<int>;
using vvi=vector<vi>;
using vl=vector<ll>;
using vvl=vector<vl>;
using P=pair<int,int>;
using PP=pair<int,P>;
#define pb push_back
#define fi first
#define se second
const int MOD=1e9+7;
const int INF=1e9;
const ll LINF=1LL<<60;
template<class T>bool chmax(T &a,const T &b){if(a<b){a=b;return true;}return false;}
template<class T>bool chmin(T &a,const T &b){if(a>b){a=b;return true;}return false;}
int main(){
    int n;
    cin>>n;
    string st;
    cin>>st;
    int ans=0;
    REP(i,n-1){
        if(st[i]!=st[i+1]){
            ans++;
            i++;
        }
    }
    cout<<ans<<endl;
    return 0;
}

D問題 日本沈没

問題について

Q. いつもJOI王国みたいな感じで固有名詞を出さないのにいきなり日本を沈めるのな~ぜだ

解法

各状態を独立に与えられて島の個数を数えるのは明らかに間に合わないので,少しずつ動かしていって差分を数えていきたいです.
というわけで日本を少しずつ浮上させていきます.
土地が浮かび上がってくるとき,島の状態には次の変化の内1つが起こります

  • 土地の左右に島があるとき,2つがつながる.個数は1つ減る
  • 土地の左のみに島があるとき,島の右端が変化する
  • 土地の右のみに島があるとき,島の左端が変化する
  • 土地の左右に島がないとき,独立した島となる.個数は1つ増える

さて,区間を扱っていきたいんですが,区間の座標をいじったり調べたりするときによくあるパターンとして,右端と左端をそれぞれsetで持つという方法があります.
これをするといろいろな操作がしやすくて,この問題で必要な操作は

  • 左右に島があるか:x-1に右端があるか,x+1に左端があるか
  • 左右を繋げる:右端のx-1と左端のx+1を消す
  • 独立した島を増やす:右端と左端にxを入れる
  • 島の個数を数える:右端(または左端)のsizeを求める

というふうに実現できます.そしてこの問題はこれを知っているとやるだけに落ちます.

ソースコード

#include<bits/stdc++.h>
using namespace std;
#define FOR(i,n,m) for(int i=(n);i<(m);i++)
#define REP(i,n) FOR(i,0,n)
#define all(vec) vec.begin(),vec.end()
using ll=long long;
using vi=vector<int>;
using vvi=vector<vi>;
using vl=vector<ll>;
using vvl=vector<vl>;
using P=pair<int,int>;
using PP=pair<int,P>;
#define pb push_back
#define fi first
#define se second
const int MOD=1e9+7;
const int INF=1e9;
const ll LINF=1LL<<60;
template<class T>bool chmax(T &a,const T &b){if(a<b){a=b;return true;}return false;}
template<class T>bool chmin(T &a,const T &b){if(a>b){a=b;return true;}return false;}
int main(){
    int n;
    cin>>n;
    priority_queue<P> que;
    REP(i,n){
        int x;
        cin>>x;
        if(!x){
            continue;
        }
        que.push({x,i});
    }
    set<int> l;
    set<int> r;
    int ans=0;
    while(que.size()){
        int t=que.top().fi;
        while(que.size()&&que.top().fi==t){
            P p=que.top();que.pop();
            int v=p.se;
            if(r.count(v-1)&&l.count(v+1)){//左右が存在して連結できる場合
                r.erase(v-1);
                l.erase(v+1);
            }else if(r.count(v-1)){//左だけ存在する場合
                r.erase(v-1);
                r.insert(v);
            }else if(l.count(v+1)){//右だけ存在する場合
                l.erase(v+1);
                l.insert(v);
            }else{//左右ともに存在しない場合
                l.insert(v);
                r.insert(v);
            }
        }
        chmax(ans,(int)l.size());
    }
    cout<<ans<<endl;
    return 0;
}

E問題 イルミネーション

解法

まずDPを知っていればO(N^2M)(40点)は瞬殺で,dp_{i}=(iを使ったときの最大値)としてそれ以前に遷移できるかをO(M)で調べればよいです.
これを最終的にO((N+M) log M)とかまで落としたいわけです.
まず,自分と同時に選んでは行けない場所がどこまでかということがもっと早くわかれば良くて,これは区間更新区間minの遅延セグメントツリーを書くとできます.
これを行うと,始点からその直前まではすべて遷移ができるので累積maxをとっておくことで高速に更新できます.
境界取得がO(log M)で,それをO(N)回,また前処理で[tex;O(M log M)]かかるので全体O((N+M) log M)でこの問題が解けました.

ソースコード

#include<bits/stdc++.h>
using namespace std;
#define FOR(i,n,m) for(int i=(n);i<(m);i++)
#define REP(i,n) FOR(i,0,n)
#define all(vec) vec.begin(),vec.end()
using ll=long long;
using vi=vector<int>;
using vvi=vector<vi>;
using vl=vector<ll>;
using vvl=vector<vl>;
using P=pair<int,int>;
using PP=pair<int,P>;
#define pb push_back
#define fi first
#define se second
const int MOD=1e9+7;
const int INF=1e9;
const ll LINF=1LL<<60;
template<class T>bool chmax(T &a,const T &b){if(a<b){a=b;return true;}return false;}
template<class T>bool chmin(T &a,const T &b){if(a>b){a=b;return true;}return false;}
template<typename Monoid,typename OperatorMonoid=Monoid>
struct LazySegTree{
    //0-indexed 閉区間
    using F=function<Monoid(Monoid,Monoid)>;    //要素同士の演算
    using G=function<Monoid(Monoid,OperatorMonoid)>;    //要素と作用素のマージ
    using H=function<OperatorMonoid(OperatorMonoid,OperatorMonoid)>;    //作用素同士のマージ
    using P=function<OperatorMonoid(OperatorMonoid,int)>;   //作用素を下に降ろす

    int size;
    vector<Monoid> data;
    vector<OperatorMonoid> lazy;
    const F f;  //要素同士の演算
    const G g;  //要素と作用素のマージ
    const H h;  //作用素同士のマージ
    const P p;  //作用素を下に降ろす
    const Monoid M1;    //単位元
    const OperatorMonoid OM0;   //作用素の単位元

    LazySegTree(int n,const F f,const G g,const H h,const P p,const Monoid &M1,const OperatorMonoid OM0)
        :f(f),g(g),h(h),p(p),M1(M1),OM0(OM0){
        size=1;
        while(size<n)size<<=1;
        data.assign(size*2,M1);
        lazy.assign(size*2,OM0);
    }

    void set(int k,const Monoid &x){
        //kをxに初期化
        //buildを忘れずに行うこと
        data[k+size-1]=x;
    }
    void build(){
        //構築 O(N)
        for(int k=size-2;k>=0;k--){
            data[k]=f(data[2*k+1],data[2*k+2]);
        }
    }
    void propagate(int k,int len){
        //長さlenのkから下へ伝播
        if(lazy[k]!=OM0){
            if(k<size-1){
                lazy[2*k+1]=h(lazy[2*k+1],lazy[k]);
                lazy[2*k+2]=h(lazy[2*k+2],lazy[k]);
            }
            data[k]=g(data[k],p(lazy[k],len));
            lazy[k]=OM0;
        }
    }

    Monoid update(int a,int b,const OperatorMonoid &x,int k,int l,int r){
        propagate(k,r-l+1);
        if(r<a||b<l){ //範囲外
            return data[k];
        }else if(a<=l&&b>=r){   //内部
            lazy[k]=h(lazy[k],x);
            propagate(k,r-l+1);
            return data[k];
        }else{
            return f(update(a,b,x,2*k+1,l,(l+r)/2),
                    update(a,b,x,2*k+2,(l+r)/2+1,r));
        }
    }
    Monoid update(int a,int b,const OperatorMonoid &x){
        //[a,b]をxに変更
        return update(a,b,x,0,0,size-1);
    }

    Monoid query(int a,int b,int k,int l,int r){
        propagate(k,r-l+1);
        if(r<a||b<l){
            return M1;
        }else if(a<=l&&r<=b){
            return data[k];
        }else{
            return f(query(a,b,2*k+1,l,(l+r)/2),
                    query(a,b,2*k+2,(l+r)/2+1,r));
        }
    }
    Monoid query(int a,int b){
        return query(a,b,0,0,size-1);
    }

    Monoid operator[](const int &k){
        return query(k,k);
    }
    void debug(){
        REP(i,size){
            cerr<<query(i,i)<<" ";
        }cerr<<endl;
    }
};
int main(){
    int n,m;
    cin>>n>>m;
    vl vec(n);
    REP(i,n){
        cin>>vec[i];
    }
    auto f=[](int a,int b){return min(a,b);};
    auto g=[](int a,int b){return min(a,b);};
    auto p=[](int a,int b){return a;};
    LazySegTree<int> ruq(n,f,g,g,p,INT_MAX,INT_MAX);
    REP(i,n){
        ruq.set(i,i-1);
    }
    ruq.build();
    REP(i,m){
        int l,r;
        cin>>l>>r;
        l--;r--;
        ruq.update(l,r,l-1);
    }
    vl dp(vec);
    REP(i,n){
        int k=ruq[i];
        if(k>=0){
            dp[i]+=dp[k];
        }
        if(i){
            chmax(dp[i],dp[i-1]);
        }
    }
    cout<<dp[n-1]<<endl;
    return 0;
}