JOI2013-2014予選
今年も去年みたいに問４まで解いたら見直ししたりしてまったり過ごそうと思ってたけど、5問目がDijkstraだったのでやってみた（結果的に違ってそうで怖い…）
1.去年より読みやすくて親切。（1:04）
#include<iostream>
using namespace std;
#define rep2(x,from,to) for(int (x)=(from);(x)<(to);(x)++)
#define rep(x,to) rep2(x,0,to)
int main()
{
int a[5];
rep(i,5)
{
cin>>a[i];
if(a[i]<40)a[i]=40;
}
int ans=0;
rep(i,5)
{
ans+=a[i];
}
cout<<ans/5<<endl;
return 0;
}
2.いろいろ考えてバグるのが怖かったし気の赴くままにやった。(1:10)
#include<iostream>
using namespace std;
#define rep2(x,from,to) for(int (x)=(from);(x)<(to);(x)++)
#define rep(x,to) rep2(x,0,to)
int main()
{
int n,m;
cin>>n>>m;
int a[1000];
rep(i,n)
{
cin>>a[i];
}
int b[1000];
rep(i,m)
{
cin>>b[i];
}
int hyo[1000];
rep(i,1000)hyo[i]=0;
rep(i,m)
{
rep(j,n)
{
if(b[i]>=a[j])
{
hyo[j]++;
break;
}
}
}
int ans=0;
int ans_hyo=hyo[0];
rep(i,n)
{
if(ans_hyo<hyo[i])
{
ans=i;
ans_hyo=hyo[i];
}
}
cout<<ans+1<<endl;
return 0;
}
お菓子食べた。
3.最初問題文が曖昧で怖かったけど、どうせ問３だから同じ道を二回通る
ときも重複して数えていいだろと思って書く。ここらへんで見てた吉本新喜劇が終わった。(1:20)
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
using namespace std;
#define rep2(x,from,to) for(int (x)=(from);(x)<(to);(x)++)
#define rep(x,to) rep2(x,0,to)
int main()
{
int w,h,n;
cin>>w>>h>>n;
int ww[1000];
int hh[1000];
rep(i,n)
{
cin>>ww[i]>>hh[i];
}
int sx,sy,ex,ey;
int ans=0;
rep(i,n-1)
{
if(ww[i]<=ww[i+1])
{
sx=ww[i];
sy=hh[i];
ex=ww[i+1];
ey=hh[i+1];
}
else
{
sx=ww[i+1];
sy=hh[i+1];
ex=ww[i];
ey=hh[i];
}
int del_x;
int del_y;
del_x=(ex-sx);
del_y=(ey-sy);
if(sy<=ey)
{
ans+=(min(del_x,del_y)+abs(del_x-del_y));
}
else
{
ans+=(abs(del_x)+abs(del_y));
}
}
cout<<ans<<endl;
return 0;
}
チョコ食べた。順調でうれしい。
4.bitDPっぽい。（けどbit操作よく分かんないから4重dpでやった。）
JOIはメモ化再帰でやると楽な問題が多い感じがしてたからメモ化した。
dp[J君が来るかどうか][O君が来るかどうか][I君(ry][何日目か]でもつ。
最初鍵を誰が持つかとかいろいろ考えてたけど結局のところそんなことどうでもいい
ことに気付く。その後再帰内のcontinueをbreakと間違ってることに気付かず焦る。
ただ時が流れるなか茂蔵を見て落ち着く。（1:40）
再開してバグに気付き、exampleが通る。とりあえずボーダーは
切り抜けそうだなと思い落ち着く。(2:40)
#include<iostream>
#include<cstdio>
#include<string>
using namespace std;
#define rep2(x,from,to) for(int (x)=(from);(x)<(to);(x)++)
#define rep(x,to) rep2(x,0,to)
int dp[2][2][2][1000];
int N;
string str;
int saiki(int af,int bf,int cf,int n)
{
if(dp[af][bf][cf][n]!=-1)
{
return dp[af][bf][cf][n];
}
int ans=0;
if(n==N-1)//最後の日
{
ans=1;
}
else
{
rep(a,2)//次の日Jが参加するかどうか
{
rep(b,2)//O
{
rep(c,2)//I
{
if(str[n+1]=='J')if(a==0)continue;
if(str[n+1]=='O')if(b==0)continue;
if(str[n+1]=='I')if(c==0)continue;
if(a*af+b*bf+c*cf==0)continue;
ans+=saiki(a,b,c,n+1);
}
}
}
}
ans%=10007;
dp[af][bf][cf][n]=ans;
return ans;
}
int main()
{
rep(i,2)rep(j,2)rep(k,2)rep(r,1000)dp[i][j][k][r]=-1;
cin>>N;
cin>>str;
int anss=0;
int sa=1;
int sb=0;
int sc=0;
if(str[0]=='J')sa=1;
if(str[0]=='O')sb=1;
if(str[0]=='I')sc=1;
rep(a,2)
{
rep(b,2)
{
rep(c,2)
{
if(sa<=a&&sb<=b&&sc<=c)
{
anss+=saiki(a,b,c,0);
}
}
}
}
cout<<anss%10007<<endl;
return 0;
}
見直しphase突入。
5.ほんとはやらないつもりだったけど、Dijkstraの香りが漂ってきたから解く。
町iからタクシーで直行できる町にも辺をはってDijkstraする。
だいくすとらーなれてないし、JOI予選ならpriority_queue使うまでもないかな
と思ったのでO(N^2)でやる。
#include<iostream>
#include<cstdio>
#include<vector>
#include<string>
#include<set>
#include<stdlib.h>
using namespace std;
#define rep2(x,from,to) for(int (x)=(from);(x)<(to);(x)++)
#define rep(x,to) rep2(x,0,to)
#define INF 1000000000
int C[5000];
int R[5000];
int n,k;
vector<int> TO[5000];
set<int> next_to[5000];
int flag[5000];
void saiki(int s,int now,int n)
{
int size=TO[now].size();
if(n!=R[s])
rep(i,size)
{
if(flag[TO[now][i]]==0)
{
flag[TO[now][i]]=1;
next_to[s].insert(TO[now][i]);
saiki(s,TO[now][i],n+1);
}
}
}
int main()
{
cin>>n>>k;
int a,b;
rep(i,n)
{
cin>>C[i]>>R[i];
}
rep(i,k)
{
cin>>a>>b;
a--;
b--;
TO[a].push_back(b);
TO[b].push_back(a);
}
rep(i,n)
{
rep(j,5000)flag[j]=0;
flag[i]=1;
saiki(i,i,0);
}
int d[5000];
int used[5000];
rep(i,n) used[i]=0;
rep(i,n) d[i]=INF;
d[0]=0;
set<int>::iterator itt;
while(1)
{
int v=-1;
for(int u=0;u<n;u++)
{
if(used[u]==0&&(v==-1||d[u]<d[v]))v=u;
}
if(v==-1)break;
used[v]=1;
int n_size=next_to[v].size();
itt=next_to[v].begin();
rep(i,n_size)
{
d[*itt]=min(d[*itt],d[v]+C[v]);
itt++;
}
}
cout<<d[n-1]<<endl;
return 0;
}
どうやら5問目は2つのテストデータで間違っているらしいがどこで間違ったのかが
まだ分からない…
一応460点はありそうやし本選行けたらいいなーと思いました。（小並感
このブログ始めてまだまだhatenablogの使い方もよく分からないし、ソースの綺麗な書き方も分からないし、情弱だし、他にも……というところがあって、いろいろ精進しないとなと思う。
