読者です 読者をやめる 読者になる 読者になる

New Year Contest 2015

rng_58さんのコンテスト。まだあんまり解けてないけど面白かった。
とりあえずコンテスト中に通った分だけ

A : 愚直にやればよい(vectorは比較出来るらしい)

#include <bits/stdc++.h>
using namespace std;
#define pb push_back

int n;
vector<int> a,b;

int main(){
    cin>>n;
    while(n){
	a.pb(n&1);
	n/=2;
    }
    b=a;
    reverse(b.begin(),b.end());
    if(a==b) cout<<"Yes\n";
    else cout<<"No\n";
    return 0;
}

B : sortしてgreedyに拾っていく

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i=0;i<n;++i)

int n,ret;
ll a[1010],s;

int main(){
    cin>>n;
    rep(i,n) cin>>a[i];
    a[n]=LLONG_MAX;
    sort(a,a+n);
    s=a[0];ret=1;
    for(int i=1;i<n;){
	int v=upper_bound(a+i,a+n,s)-a;
	if(v==n) break;
	i=v;
	s+=a[v];
	++ret;
    }
    printf("%d\n",ret);

    return 0;
}

C : 一見難しそうだけど、少し考えると、元ある文字と文字の間には、1文字目が異なるならなんでも挿入出来ることがわかる。DPしなくても出来るらしい。

#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;++i)

bool ok[5010][5010];
string s,t;

bool ch(){
    if(s.size()>t.size()) return 0;
    ok[0][0]=1;
    rep(i,s.size()){
	int mi=5010;
	rep(j,t.size()){
	    if(ok[i][j]&&s[i]==t[j]){
		ok[i+1][j+1]=1;
		if(j+1<t.size()&&t[j]!=t[j+1]){
		    mi=min(mi,j+1);
		}
	    }
	}
	for(int j=mi;j<=t.size();++j) ok[i+1][j]=1;
    }
    return ok[s.size()][t.size()];
}

int main(){
    cin>>s>>t;
    if(ch()) cout<<"Yes\n";
    else cout<<"No\n";
    return 0;
}

D : 問題文が親切。x -> a*2 - xに移る。更にb*2 - (a*2 - x) = b*2 - a*2 + xという風に、xに関係なく移動幅が決まるので0から偶奇別にBFSするとなんとかなる。

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
#define mp make_pair
#define fi first
#define se second
#define rep(i,n) for(int i=0;i<n;++i)

const int B = 50010;
int d[2][100050],n,a[210],q;

int main(){
    memset(d,-1,sizeof(d));
    scanf("%d",&n);
    rep(i,n){scanf("%d",a+i);a[i]*=2;}
    queue<pii> que;
    que.push(mp(0,B));
    d[0][B]=0;
    while(!que.empty()){
	pii p=que.front();que.pop();
	int f=p.fi,x=p.se-B;
	rep(i,n){
	    int nx=a[i]-x;
	    if(nx>=-20000&&nx<=30000&&d[f^1][nx+B]==-1){
		d[f^1][nx+B]=d[f][x+B]+1;
		que.push(mp(f^1,nx+B));
	    }
	}
    }
    scanf("%d",&q);
    while(q--){
	int s,t;
	scanf("%d%d",&s,&t);

	int l=d[0][t-s+B],r=d[1][t+s+B],as;
	if(l!=-1&&r!=-1) as=min(l,r);
	else if(l!=-1) as=l;
	else if(r!=-1) as=r;
	else as=-1;
	printf("%d\n",as);
    }
    return 0;
}

G : JOIでよくありそうな感じ。最短路的なことをすると解けるが適当にやると計算量がダメ。
もう動き出して他にぶつかるのを考えた点を消す&同じ向きのロボットに当たったらそっちを動かすことにして打ち切ると大丈夫。

#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> pii;
typedef long long ll;

#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define rep(i,n) for(int i=0;i<n;++i)

int dx[]={0,0,-1,1};
int dy[]={1,-1,0,0};

struct ev{
    int id;ll tt;
    ev(int id, ll tt):id(id),tt(tt){}
    bool operator<(const ev& a) const{ return tt>a.tt; }
};

int n;
int dir[100010];
ll t,st[100010];
pii po[100010];
vector<int> xs,ys;
set<pii> sx[100010],sy[100010];

void rem(int i){
    int xx=lower_bound(xs.begin(),xs.end(),po[i].fi)-xs.begin(),
	yy=lower_bound(ys.begin(),ys.end(),po[i].se)-ys.begin();
    sy[xx].erase(mp(po[i].se,i));
    sx[yy].erase(mp(po[i].fi,i));
}

int main(){
    scanf("%d%lld",&n,&t);
    rep(i,n) st[i]=LLONG_MAX;    
    rep(i,n){
	char c[3];
	scanf("%d%d%s",&po[i].fi,&po[i].se,c);
	if(c[0]=='U') dir[i]=0;
	else if(c[0]=='D') dir[i]=1;
	else if(c[0]=='L') dir[i]=2;
	else dir[i]=3;
	xs.pb(po[i].fi); ys.pb(po[i].se);
    }
    sort(xs.begin(),xs.end()); sort(ys.begin(),ys.end());
    xs.erase(unique(xs.begin(),xs.end()),xs.end()); ys.erase(unique(ys.begin(),ys.end()),ys.end());

    rep(i,n){
	int xx=lower_bound(xs.begin(),xs.end(),po[i].fi)-xs.begin(),
	    yy=lower_bound(ys.begin(),ys.end(),po[i].se)-ys.begin();
	sx[yy].insert(mp(po[i].fi,i));
	sy[xx].insert(mp(po[i].se,i));
    }

    priority_queue<ev> que;
    que.push(ev(0,0));
    while(!que.empty()){
	ev e=que.top(); que.pop();
	if(st[e.id]<e.tt) continue;
	int xx=lower_bound(xs.begin(),xs.end(),po[e.id].fi)-xs.begin(),
	    yy=lower_bound(ys.begin(),ys.end(),po[e.id].se)-ys.begin();	
	st[e.id]=e.tt;
	rem(e.id);

	int d=dir[e.id];
	if(d==0){
	    for(auto it=sy[xx].upper_bound(mp(po[e.id].se,-1));it!=sy[xx].end();++it){
		int ii=(*it).se;
		ll nt=e.tt+(*it).fi-po[e.id].se;
		que.push(ev(ii,nt));
		if(dir[ii]==d) break;
	    }
	}else if(d==1){
	    for(auto it=sy[xx].lower_bound(mp(po[e.id].se,-1));;){
		if(it==sy[xx].begin()) break;
		--it;
		int ii=(*it).se;
		ll nt=e.tt-(*it).fi+po[e.id].se;
		que.push(ev(ii,nt));
		if(dir[ii]==d) break;
	    }	    
	}else if(d==3){
	    for(auto it=sx[yy].upper_bound(mp(po[e.id].fi,-1));it!=sx[yy].end();++it){
		int ii=(*it).se;
		ll nt=e.tt+(*it).fi-po[e.id].fi;
		que.push(ev(ii,nt));
		if(dir[ii]==d) break;
	    }
	}else{
	    for(auto it=sx[yy].lower_bound(mp(po[e.id].fi,-1));;){
		if(it==sx[yy].begin()) break;
		--it;
		int ii=(*it).se;
		ll nt=e.tt-(*it).fi+po[e.id].fi;
		que.push(ev(ii,nt));
		if(dir[ii]==d) break;
	    }	    
	}
    }
    rep(i,n){
	ll px=po[i].fi,py=po[i].se;
	if(st[i]<=t){
	    px+=(t-st[i])*dx[dir[i]];
	    py+=(t-st[i])*dy[dir[i]];
	}
	printf("%lld %lld\n", px, py);
    }
    return 0;
}