競技プログラミングで見かけた実装（C++）
Competitive Advent Calenderにもテンプレ考察ということでありましたが、今まで競プロをやってきて面白いと思った実装、自分が実際に使っている実装を書いていこうと思います。
#define
定番。どの程度まで使うかはその人次第。
#define rep(i,n) for(int i=0;i<n;i++) #define REP(i,a,n) for(int i=a;i<n;i++) #define all(a) (a).begin(),(a).end() #define pb push_back #define mp make_pair #define mt make_tuple #define eps 1e-15
といいながら自分は基本はこれは使いません。push_backとかはエディタが補完してくれるので楽なんです。
rep系は発展形も多くて便利です。
因みに定数は#define派とconst派に別れるようです。自分はconst派なんですが。
typedef
型名長い→省略。
typedef long long ll; typedef long double ld; typedef vector<int> vi; typedef vector<vi> vvi; typedef map<int,int> mii; typedef pair<int,int> pii; typedef tuple<int,int,int> ti3;
自分はダイクストラやDPの時に長めの型の変数をよく使うので先程のと合わせて便利です。priority_queueをpqと省略してもいいのかもしれませんが、自分は変数名としてpqを用いているのでそれはしていません。
#include <bits/stdc++.h>
気になった人は
libstdc++: stdc++.h Source File
へ。内容通り1行で全部インクルード出来ます。結構コンパイルが重くなるので注意。
地味に便利なやつ
const int inf=1<<30; const int INF=INT_MAX; const int dx[]={1,0,-1,0},dy[]={0,1,0,-1}; const int d[]={0,1,0,-1,0}//int nx=x+d[i],ny=y+d[i+1]と使用。
INT_MAXは普通にそのまま使っています。というより書いたのはINT_MAXなんでみんな使わないんだろう…と思ったからです。
foreach
C++11以降の実装です。
vector<int> a(N,12345); for(int i=0;i<a.size();i++) cout<<a[i]<<endl;
が
vector<int> a(N); for(int i:a) cout<<i<<endl;
と書けます。自分も最近知ったのですが、かなり便利で、わざわざiteratorを用いていたところを
map<int,int> a; //中身を適当に入れる for(auto i:a) cout<<i.first<<" "<<i.second<<endl;
とループが扱えます。
余談ですが、C++11でChronoという時間計測のプログラムが入っているようです。今までtimeでは1秒単位、clockはCPU依存でまともに計測が出来なかったので助かった…
というついでにかなり雑にC++11の機能を見てみたのですが、beginとendはメンバ関数よりbegin(a)と使うことが推奨されているらしいです…
iteratorのnextとprevも使ったことは無いけれどもランダムイテレータで無いため困ったことは何度もあるので便利そう。
AOJ1020:Cleaning Robot
ようやくACした…
問題概要
掃除ロボットが3×3のグリッドの中を動く。電池を1消費して上下左右に等確率で選び、その方向へ進む。しかし、行き先がグリッドの外だったり、指定されたグリッド（1マス）だった場合は、移動せずに電池のみを消費する。
このように移動した時、与えられた始点から出たロボットが与えられた終点に電池が切れると同時に到着する確率を求める問題。
Cleaning Robot | Aizu Online Judge
解き方
電池は移動とともに減っていく。逆に電池が増えることは無いので、
dp[i][j]:i回移動した時、マスjにいる確率
とおいてあげて（残り電池残量をiとする方法もあり。）
dp[0][始点]=1
dp[i+1][（移動先）]=Σdp[i][（移動元）]
としてあげれば解ける。
#include <bits/stdc++.h> using namespace std; int dp[20][3][3]; const int dx[]={1,-1,0,0}; const int dy[]={0,0,1,-1}; int main(){ while(true){ int n; cin>>n; if(n==0) return 0; char s,t,b; cin>>s>>t>>b; int sx,sy,tx,ty,bx,by; for(int i=0;i<3;i++){ for(int j=0;j<3;j++){ int num=3*i+j; if(num==s-'A'){ sy=i; sx=j; } if(num==t-'A'){ ty=i; tx=j; } if(num==b-'A'){ by=i; bx=j; } } } for(int i=0;i<20;i++) for(int j=0;j<3;j++) for(int k=0;k<3;k++) dp[i][j][k]=0; dp[0][sy][sx]=1; for(int i=0;i<n;i++){ for(int y=0;y<3;y++){ for(int x=0;x<3;x++){ if(dp[i][y][x]==0) continue; for(int l=0;l<4;l++){ int ny=y+dy[l]; int nx=x+dx[l]; if(ny<0||3<=ny||nx<0||3<=nx){ dp[i+1][y][x]+=dp[i][y][x]; } else if(bx==nx&&by==ny){ dp[i+1][y][x]+=dp[i][y][x]; } else{ dp[i+1][ny][nx]+=dp[i][y][x]; } } } } } printf("%.15lf\n",(double)dp[n][ty][tx]/pow(4,n)); } }
感想
自分は最初グリッドを3×3の配列で表さずに1列9要素の配列で再現してみました。その方が実装が楽なんですが、何故かWA。
memsetを避けてみたり、doubleをlong doubleに変えてみたり。intで数え上げて最後に4^nで割って見てもダメ。ということで諦めて実装しなおしました。
しかし、なんでダメだったのだろう…
問題自体はかなり簡単だったにもかかわらず、理由の分からないWAに苦しめられました。AOJさん、vol.10とかでもテストケース公開してくれませんかね…
AOJ1026:Hedro's Hexahedron
N✕N✕2の直方体の容器の中に容積2Nの液体を入れる。N✕Nの平面に垂直な軸で容器を１回転させた時、液体に触れる面積はいくつか求める問題。ただし、タイル状で考え、少しでもそのタイルにかすればその1タイルは液体に触れたとする。
Hedro's Hexahedron | Aizu Online Judge
底面は間違いなく液体に触れる。でも、側面は…分かるんだけど描いてみたかったので描きました。
綺麗な包絡線が出来てますね…反比例のグラフのようです。
面積Nで左端からの幅をw、高さをhとおけばN=wh/2が成立するので当然ですが。
取り敢えず、今回は左下の1/4の部分のみを考えて、後に裏面も考慮して８倍してあげればいいでしょう。
N≦10^12より左端から数えていって時間内に間に合うようにするには、N≦w^2の範囲のみ数えて、それを2倍、被ったところを引いてあげます。O(√N)。
#include <bits/stdc++.h> using namespace std; typedef long long ll; int main(){ while(true){ ll n; cin>>n; if(n==0) return 0; ll ans=8*n;// 底面積 ll ans2=n/2; ll w=1; for(;w*w<n/2;w++){ ans2+=(n+2*w-1)/(2*w); } ans2=2*ans2-w*w; if(n&1) ans2++; ll s=ans+ans2*8; cout<<s<<endl; } }
考察ゲーでした。ちなみにifのところは一番外側の一周がNが奇数の時に重複するためそれを避けるものです。と思ったけど、Nって偶数なんだ…要りません。かなり考えさせられたのになぁ…
実質２周目までは絶対全部使います。それを使っても良かったな…とか、今高２で数Ⅲ終えたばかりなので積分と挟み撃ち使って何か出来そうだな…とか思ったりしていました。
AOJ1028:ICPC: Ideal Coin Payment and Change
太郎くんがP円の物を買う。持っている1円〜500円までの硬貨の枚数が与えられた時、支払う枚数＋お釣りの枚数の最小値を求める問題。お釣りは返す枚数が一番少なくなるように返される。
支払う枚数とお釣りの枚数を別々に求める。お釣りの方は貪欲に支払われるので簡単。問題は支払うときの方。
dp[i][j]:i種類目までの硬貨でj円を払う最小の硬貨の枚数
と定義してあげて、（vは硬貨の価値）
dp[i+1][j]=min(dp[i][j-k✕v[i] | 0≦k≦N[i]かつj-k✕v[i]≧0)
である。しかし、これだとN≦1000より間に合わない。ここで、蟻本にも載っている「スライド最小値」を用いる。
b[j]=dp[i][j✕v[i]+a]-j と定義すると、（0≦a＜v[i]）
dp[i+1][j✕v[i]+a]=min(b[k] | j-N[i]≦k≦j) +j
と表すことが出来る。このminの部分にdequeを用いることで間に合う。
#include <bits/stdc++.h> using namespace std; const int kou[]={1,5,10,50,100,500}; int dp[7][700000]; int main(){ while(true){ int p; cin>>p; if(p==0) return 0; vector<int> n(6); for(int i=0;i<6;i++){ cin>>n[i]; } for(int i=0;i<7;i++){ dp[i][0]=0; for(int j=1;j<700000;j++) dp[i][j]=1<<25; } int end=0; for(int i=0;i<6;i++){ end+=n[i]*kou[i]; for(int a=0;a<kou[i];a++){ deque<pair<int,int>> dq;//値、インデックス for(int j=0;j*kou[i]+a<=end;j++){ int val=dp[i][j*kou[i]+a]-j; while(!dq.empty()&&dq.back().first>=val) dq.pop_back(); dq.push_back(make_pair(val,j)); dp[i+1][j*kou[i]+a]=dq.front().first+j; while(!dq.empty()&&j-dq.front().second>=n[i]) dq.pop_front(); } } } int ans=INT_MAX; for(int i=p;i<=end;i++){ int tmp=dp[6][i],v=i-p; int tmp2=0; for(int j=5;j>=0;j--){ tmp2+=v/kou[j]; v%=kou[j]; } ans=min(ans,tmp+tmp2); } cout<<ans<<endl; } }
しばらくはこんな感じでAOJを解き進めつつ、TopCoderやCodeforcesに出て行きたいかな、と思います。
JOI2015参加記
さて、本日JOI予選の結果がメールで送られてきました。
6問に手を出し（全てアルゴリズムは分かった）、うち６問目は実装にバグが残って実行も出来ずに時間切れでした。ということで５完。
…と思ってました。13日の22:00までは。
一応と思って解答が公開されるのを待って全てダウンロード、diffを使って確かめてみると、問題3と5につまらないミスがあったことが発覚。死亡しました。
ということで340点。ボーダーは360点らしく、ギリギリアウトです。
ここで、「問題6を無理に満点解法狙うんじゃなくて、ケース1に特化した解法で書いておけば良かった…」と後悔してももう遅い。1年の努力をしょうもないミスで水の泡に変えてしまった自分でした。
しっかし、1番気に食わないのはボーダーが360ということは問題4がO(N^2)解法でも問題3まで全部合っていれば本戦に行けてしまうということですね…
しかし、終わったことは仕方ない。自分の実装力と運が不足していた。
