A-ソーシャルゲーム(Social Game)
・問題概要
JOI君はソシャゲを始める。
ログインボーナスがA(1<=A<=1000)コイン、7日連続でログインするとB(1<=B<=1000)コインもらえる。
C(1<=C<=10^6)枚のコインが欲しいとき何日ログインすべきか
・解法
・累計のコインがC以上になるまで愚直に探索
・実装
こんな感じ
#include<iostream> #include<algorithm> #include<vector> #include<queue> #include<string> using namespace std; typedef long long Int; int main(){ int a,b,c; cin>>a>>b>>c; int cnt=0; while(c>0){ c-=a; cnt++; if(cnt%7==0) c-=b; } cout<<cnt<<endl; }
B-すごろくと駒(Sugoroku and Pieces)
・問題概要
・すごろくがありスタートとゴールの間に1～2019の番号が振られている
・1個先に駒がいないorゴールに着かないなら毎回指定された駒を1個右へ
・解法
・実際にそれをプログラム上でやってみる
・i番目の駒がどこにあるかの配列と、マスiに駒がいるかどうかのbool型配列を用意して実装
・実装
こんな感じ
#include<iostream> #include<algorithm> #include<vector> #include<queue> #include<string> using namespace std; typedef long long Int; bool used[2020]={0}; int pos[2020]={0}; int main(){ int n; cin>>n; for(int i=1;i<=n;i++){ cin>>pos[i]; used[pos[i]]=1; } int m; cin>>m; for(int i=0;i<m;i++){ int a; cin>>a; if(used[pos[a]+1]==0&&pos[a]+1!=2020){ used[pos[a]]=0; used[pos[a]+1]=1; pos[a]+=1; } } for(int i=1;i<=n;i++) cout<<pos[i]<<endl; }
C-マルバツスタンプ
・問題概要
・JOI君は○スタンプ、×スタンプ、○×スタンプをいくつか持っている
・○×スタンプは○×と×○のどっちの押し方もできる
・JOI君がスタンプを押した残骸をもらうので、JOI君が持っている○×の個数の最大は？
・解法
・要素数分、はじめから見ていく
・i番目!=i+1番目ならそこは○×を使って押せます
・この場合i+1番目は見なくて良いのでi+2番目の探索に移ります
・実装
こんな感じ
#include<iostream> #include<algorithm> #include<vector> #include<queue> #include<string> using namespace std; typedef long long Int; bool used[2020]={0}; int pos[2020]={0}; int main(){ int n; string s; cin>>n; cin>>s; int ans=0; for(int i=0;i<n-1;i++){ if((s[i]=='O'&&s[i+1]=='X')||(s[i]=='X'&&s[i+1]=='O')){ ans++; i++; } } cout<<ans<<endl; }
ここまで10分で埋めました。例年の過去問だと20分くらい書けてるので速いほうですね、嬉しい
D-日本沈没(Japan Sinks)
・問題概要
・日本をn個の区画に分ける。それぞれに高さA[i]がある。
・海面上昇で相対的に日本が沈む。ばいばい。
・だんだん高さが低い部分から海底になっていくが、そのとき連続していない一続きの陸地がc個あるとき島の数をcとする
・日本が完全消滅するまでに島が一番たくさんできるのはいつ？
・解法
・何も考えずに部分点1を見る。愚直にシュミレーションして間に合う。
・具体的には、日本の最高点に波が来るまで波の高さを1ｍずつ試す。
・毎回全体を見渡して島の数を数えていけばO(NAmax)<=4000000回の計算なので間に合う
・部分点2は高さの制約がないも同然
・そこで座標圧縮という技を使う
・具体例をみた方がわかりやすいかも
・→0、1、100、5000兆だけ見ればいい こうすれば5000兆回試さなくて済む
・全部の高さをvectorに入れてソートする、またはpriority_queueを使うなどしてこれを実装すれば7+8＝15点
・5，6の全探索を埋めて、満点解法が生えた
・この場合、5が沈むので島の数は増える
・しかし実際は1～3や7は5が沈んでも関係ない→その隣の状態だけを考えればいい
・海底:0,大陸の左端:1,大陸の右端:2,孤島:3,大陸内部:4とし、その状態がどのように変化するかを考えればO(N^2)くらいでできた
・これをACするのに2時間かけたが、これをACできたのは大きい
・実装
満点解法だけ載せます。割とごちゃごちゃしているのでわかりにくいかも
#include<iostream> #include<algorithm> #include<vector> #include<queue> #include<string> using namespace std; typedef unsigned long long Int; typedef pair<Int,Int> P; Int a[100005]={0}; vector<Int> v; vector<P> island; int main(){ Int n,maxa=0,zcnt=0; cin>>n; for(Int i=0;i<n;i++){ cin>>a[i]; maxa=max(maxa,a[i]); if(a[i]==0) zcnt++; v.push_back(a[i]); island.push_back(P(a[i],i)); } v.push_back(0); sort(v.begin(),v.end()); sort(island.begin(),island.end()); Int p=zcnt; Int ans=0; int info[200005]={0}; Int is=0; for(Int j=0;j<n;j++){ if(a[j]<=0&&is>0){ ans++; is=0; if(j>=1){ if(info[j-1]==1) info[j-1]=3; else info[j-1]=2; } } else { if(is==0&&a[j]<=0) info[j]=0; else if(is==0) info[j]=1; else info[j]=4; is=a[j]; } } if(a[n-1]<=0) info[n-1]=0; else if(a[n-2]<0&&a[n-1]>0) info[n-1]=3; else info[n-1]=2; if(is>0) ans++; Int ans2=ans; for(Int i=0;i<v.size();i++){ Int np=0; np=(lower_bound(island.begin(),island.end(),P(v[i]+(Int)1,(Int)0))-island.begin()); for(int j=p;j<np;j++){ Int pos=island[j].second; if(info[pos]==4){ ans++; if(info[pos-1]==1) info[pos-1]=3; else info[pos-1]=2; if(info[pos+1]==2) info[pos+1]=3; else info[pos+1]=1; } else if(info[pos]==2){ if(info[pos-1]==1) info[pos-1]=3; else info[pos-1]=2; } else if(info[pos]==3){ ans--; info[pos]=0; } else if(info[pos]==1){ if(info[pos+1]==2) info[pos+1]=3; else info[pos+1]=1; } info[pos]=0; } if(ans2<ans) ans2=ans; p=np; } cout<<ans2<<endl; }
E-イルミネーション(Illumination)
・問題概要
・JOI氏は木をN本はやしている。電飾してEn-JOI-ableな冬を過ごしたい。
・まぶしすぎるのは嫌なのでm個の区間[l,r]では1本の木にしか電飾しない
・木ごとに美しさがあるのでそれを最大化したい
・解説(になっていない)
・結論から言うと部分点1しかとれませんでした
・全探索をします
・具体的には･･･すべての場所で電飾のあるなしを試します。計算量はO(2^N)
・10分でこれを書いた以外何も分かりませんでした。終わった後にDPするらしいと言われ納得したけど実装ができない
・実装
bit全探索の書き方が知りたい人向けに一応･･･
ちなみにi>>jはiのビットをjだけシフトさせたと言うことです。例えば57>>2は57＝111001(2)より、2つ右にずらすと001110になります。
#include<iostream> #include<algorithm> #include<vector> #include<queue> #include<string> using namespace std; typedef long long Int; typedef pair<Int,Int> P; Int a[200005]={0}; vector<P> v; int main(){ Int n,m; cin>>n>>m; for(int i=1;i<=n;i++) cin>>a[i]; for(int i=0;i<m;i++){ Int l,r; cin>>l>>r; v.push_back(P(l,r)); } Int ans=0; for(Int i=1;i<(1<<(n+1));i++){ bool f2=true; for(Int j=0;j<m;j++){ Int l=v[j].first,r=v[j].second; bool f=false; for(int k=l;k<=r;k++){ if(((i>>k)&1)==1){ if(!f) f=true; else{ f2=false; break; } } } } Int kans=0; if(f2){ for(int j=1;j<=n;j++) if(((i>>j)&1)==1) kans+=a[j]; ans=max(kans,ans); } } cout<<ans<<endl; }
F-座席(Seats)
・問題概要
>>
・国がN個あり、i番目とi+1番目は隣国
・IOIに各国からAi人が出る
・1列に並べるが、不正対策のため隣国や同国の選手を隣にしないように並べたい
・パターン数のmod10007を求めよ
