tqk's diary

競プロとか

第18回日本情報オリンピック 予選に参加しました

結果

  • 100-100-100-100-100-6で合計506点を取りました。去年の予選通過のボーダーが340だったらしいので、多分本選行けると思います

感想

  • 競プロを初めてもうすぐ半年というところで、これだけの点数を取ることができてうれしいです
  • 全体的に、過去問よりかなり簡単に感じました。
  • 体感難易度はJOI難易度で2-2-2-6-5-?というところ(解けない問題の難易度は分からないので)
  • 不得意なグラフが出なかったおかげでここまで取れた気がします
  • 解いた順番は、A(10分)->B(7分)->C(7分)->E部分点(70点)(17分)->D(1時間10分)->F部分点(6点)(14分)->E(20分) です
  • Dの発想が難しい

  • 以下、可読性0のクソコードを貼ります

A問題

  • 1日ごとにaコイン、7日ごとにbコインもらえるとき、何日目にcコイン以上になるかという問題です

  • 最初は割り算をして出そうと思いましたが、頭が悪いので2WAしてキレてループまわしました()

int main(){
    lint a,b,c;cin>>a>>b>>c;
    lint cur=0,ans=0;
    while(cur<c){
        ++ans;
        cur+=a;
        if(ans%7==0)cur+=b;
    }cout<<ans;
}

B問題

JOI 君はすごろくを持っている.このすごろくは 2019 個のマスが横一列に並んだ形をしている.これらのマスには,左端のスタートマスから右端のゴールマスへと順に 1 から 2019 までの番号がついている.

現在このすごろくの上には,N 個の駒が置かれている.これらの駒には,スタートに近い順に 1 から N までの番号がついている.駒 i (1≦i≦N) は,マス Xi に置かれている.すべての駒は異なるマスに置かれている.

JOI 君はこれから M 回の操作を行う.j 回目 (1≦j≦M) の操作では,駒 Aj を 1 マス先へ進める.ただし,移動元のマスがゴールマスであった場合,もしくは移動先のマスに別の駒が置かれている場合,駒 Aj は進まず,位置は変わらない.

すべての操作が終了した時点で,各駒が置かれているマスを求めよ.

という問題です。

int main(){
    lint n;cin>>n;
    bool ma[10000]={};
    vector<lint> x(n);
    rep(i,n){
        cin>>x[i];--x[i];
        ma[x[i]]=1;
    }
    lint m;cin>>m;
    vector<lint> a(m);
    rep(i,m){
        cin>>a[i];--a[i];
        if(ma[x[a[i]]+1]||x[a[i]]==2018)continue;
        ma[x[a[i]]]=0;
        ++x[a[i]];
        ma[x[a[i]]]=1;
    }for(auto i:x)cout<<i+1<<endl;
}

C問題

JOI 君はマルスタンプ,バツスタンプ,マルバツスタンプの3種類のスタンプをそれぞれ 0 個以上持っている.これらはマルやバツのマークを紙に印字することができるスタンプである.

マルスタンプを使うとマルが 1 つ印字され,バツスタンプを使うとバツが 1 つ印字される.マルバツスタンプを使うとマルとバツが横一列に 1 つずつ印字され,スタンプの向きを変えることで,マルの右にバツが来るようにも,バツの右にマルが来るようにも印字できる.

JOI 君は,持っているスタンプをそれぞれちょうど 1 回ずつ適当な順番で使い,紙に横一列にマルとバツを印字した.印字されたマルとバツの列は文字列 S で表される.S は O と X から構成された長さ N の文字列であり,Si= O ならば JOI 君が印字したマークのうち左から i 番目のものがマルであることを表し,Si= X ならばそれがバツであることを表す (1≦i≦N).

あなたは,JOI 君が持っているスタンプの個数は分からないが,JOI 君が印字したマルとバツの列は知っている.印字されたマルとバツの列から,JOI 君が持っているマルバツスタンプの個数としてあり得るもののうち最大値を求めよ.

という問題です。

  • 次の文字と違うかどうかだけを見たので、'O'とか'X'とかと比較しなくてもかけました
int main(){
    lint n;cin>>n; string s;cin>>s;
    lint ans=0,i=0;
    while(i<n-1){
        if(s[i]!=s[i+1]){
            ++ans;
            i+=2;
        } else ++i;
    }cout<<ans;
}

D問題

日本列島は細長い列島である.日本列島は平行な境界線により N 個の区画に分けられている.区画には端から順に 1 から N の番号が付けられている.区画 i (1≦i≦N) の高さは Ai である.

日本列島は海に囲まれており,海面の高さは場所によらず一定である.高さが海面の高さより高い区画を陸地と呼ぶ.

陸地が連続している部分のことを島と呼ぶ.より正確に書くと以下の通りである.整数 l, r (1≦l≦r≦N) について,日本列島のうち区画 l,区画 l+1,…,区画 r からなる部分を領域 [l,r] という.以下の条件を満たす領域 [l,r] を島という:

  • 区画 l,区画 l+1,…,区画 r はすべて陸地である.

  • l>1 ならば区画 l−1 は陸地ではない.

  • r<N ならば区画 r+1 は陸地ではない.

海面の上昇により,日本列島は少しずつ沈没している.現在の海面の高さは 0 であるが,これは時間が経つにつれて徐々に上がり,ついには日本全体が海になってしまう.

JOI 君は,海面の高さが上昇すると,日本の島の数が増減することに気付いた.現在から,日本に陸地がなくなるまでの間 (現在も含む) における,島の数の最大値を求めたい.

という問題です。

  • 発想が難しかったです。
  • 座標圧縮とかわかりません
  • 海面を上げて行って、区画が沈むときだけ見て、もし沈む区画の右と左が両方沈んでいたなら--(島の数)、両方沈んでいないなら++(島の数)
  • をしました
  • 10WAだしました
f:id:tako0608:20181209193834p:plainf:id:tako0608:20181209194037p:plain
int dead[100010]={1};
int main(){
    setc;
 
    lint n;cin>>n;dead[n+1]=1;
    vector<P> a(n);
    bool least=0;
    rep(i,n){
        cin>>a[i].first;
        if(a[i].first)least=1;
        a[i].second=i+1;
    }
 
    sort(all(a));
    lint ans=least,cur=1;
 
    
    rep(i,n){
        dead[a[i].second]=1;
        if(!dead[a[i].second-1]&&!dead[a[i].second+1])++cur;
        else if(dead[a[i].second-1]&&dead[a[i].second+1])--cur;
        if(i==n-1||a[i].first-a[i+1].first)ans=max(ans,cur);
    }cout<<ans;
}

E問題

JOI 氏は,自宅の敷地に N 本の木を所有している.これらの木は一列に並んでおり,順に 1 から N までの整数で番号が付けられている.

この冬,JOI 氏はいくつかの木を選んで,イルミネーションを飾り付けることにした.イルミネーションには美しさと呼ばれる値が定まっている.木 i にイルミネーションを飾り付ける場合の美しさは Ai である.

JOI 氏は,あまりに近い 2 つの木の両方にイルミネーションを飾り付けてしまうと,眩しすぎる場合があることに気がついた.具体的には,j=1,2,…,M に対して,木 Lj, Lj+1, …, Rj のうち 2 つ以上にイルミネーションを飾り付けるべきではないということが判明した.

この条件に従ってイルミネーションを飾り付けるときの,美しさの合計の最大値を求めよ.

という問題です。

  • Dよりは簡単だと思います...
  • 全てのiについて、木iを選ぶとき、その木より左にあり選べる木のうち、一番右にあるものがどこにあるか という情報が必要です
  • その前処理をO(NM)で求め、単純なDPをする(70点)までは簡単にわかります。Dに時間を使う前に70点を取っておいたのはいい判断でした

  • 前処理をO(N)に高速化するところが少し難しいです。

  • 自分はpairでl,rを受け取り、lについてソートして、左から決めていったらO(N)になりました
lint dp[200020]={};
int main(){
    lint n,m;cin>>n>>m;
    vector<lint> a(n);rep(i,n)cin>>a[i];
    vector<P> sec(m);
    vector<lint> leftest(n);rep(i,n)leftest[i]=i;
    rep(i,m){
        cin>>sec[i].first>>sec[i].second;--sec[i].first;
    }vsort(sec);lint last=0,pos=0;
    rep(i,m){//前処理
        last=max(last,sec[i].second);
        for(pos=max(pos,sec[i].first);pos<last;++pos)leftest[pos]=sec[i].first;
    }
    rep(i,n){//dp
        dp[i+1]=max(dp[i],dp[leftest[i]]+a[i]);
    }cout<<dp[n];
}
  • 始めに出した70点解法:
lint dp[200020]={};
int main(){
    lint n,m;cin>>n>>m;
    vector<lint> a(n);rep(i,n)cin>>a[i];
    vector<P> sec(m);
    vector<lint> leftest(n);rep(i,n)leftest[i]=i;
    rep(i,m){
        cin>>sec[i].first>>sec[i].second;--sec[i].first;
        repi(j,sec[i].first,sec[i].second){//前処理(70点)
            leftest[j]=min(leftest[j],sec[i].first);
        }
    }sort(all(sec));lint last=0,pos=0;
    rep(i,n){//dp
        dp[i+1]=max(dp[i],dp[leftest[i]]+a[i]);
    }cout<<dp[n];
}

F問題

2XXX 年,世界の国は直線状に並んでいた.N 個の国があり,1,2,…,N の番号が付けられている.i=1,2,…,N−1 に対し,国 i と国 i+1 が互いに隣国である.

この年の国際情報オリンピックでは,国 i からは Ai 人の選手が参加する.国際情報オリンピックの技術委員のあなたは,競技での座席表を作成する担当である.競技会場が細長いため,一列に並んだ A1+A2+…+AN 個の座席に選手たちを割り当てることになった.不正防止のため,同じ国の選手や隣国の選手を隣り合う席に割り当ててはならない.

選手たちを座席に割り当てる方法は何通りあるだろうか.この数は非常に大きくなる可能性があるので,それを 10007 で割った余りを求めたい.

という問題です。

  • 全探索O(N!)で6点を取りました
  • 2つ以上離れている人同士を辺でつなげば巡回セールスマン問題になって20点解法ができそう...?と思いましたが、20点解法の制約だと(頂点が30個あるので)bitdpできなさそう(?)でしたし、まずbitdpができないので無理でした

6点解法:

int main(){
    lint n;cin>>n;
    if(n>5)return 0;
    vector<lint> a(n),p;
    rep(i,n){
        cin>>a[i];
        rep(j,a[i])p.push_back((i<<1)+j);
    }lint ans=0;
    bool ok;lint l=siz(p);
    do{
        ok=1;
        rep(i,l-1){
            if(abs((p[i]>>1)-(p[i+1]>>1))<2){ ok=0; break;}
        }
        ans+=ok;
    } while(next_permutation(all(p)));
    cout<<ans;
}

最後に

  • これから勉強などで時間が無くなると思いますが、せっかく本戦に行ける(かもしれない)ので競プロのための時間も作りたいと思います