オンラインジャッジ日和

五反田 · 投稿記事 by **五反田** » 14年前

AOJにて、やっと解答問題数ランキングで40位以内に突入しました。

今日だけで超頑張ったら22問解けて大満足です。

いくつかの問題ではmap様様な感じになっていました。
せっかくなので今日解いた全ての問題のソースコードを貼りつけたいなと思います。
一応以下のようなものを全てのコードの先頭につけてました。

CODE:

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
static const double EPS = 1e-5;
typedef long long ll;

aoj1275
7:31
ヨセフスの問題というものらしいです。wikipediaみないとTLEしてまともに解けませんでした。

CODE:

int n,m,k;

int joseph(int n,int k){
	if(n==1)return 1;
	else return (k-1+joseph(n-1,k))%n+1;
}

main(){
	while(cin>>n>>k>>m){
		if(n==0 && m==0 && k==0){
			break;
		}else{
			cout=Q){
				i=Date[k];
				l=k;
			}
		}
		
		printf("%d\n",l);
	}
	
	return 0;
}

aoj2000
7:43
実装ゲー。面倒かと思って敬遠していましたが、案外すぐに書けました。

CODE:

int kousi[21][21];

int main(){
	int N,M;
	
	while(cin>>N){
		if(N==0)break;
		
		memset(kousi,0,sizeof(kousi));
		
		for(int i=0;i>x>>y;
			kousi[x][y]=1;
		}
		
		int M,cx=10,cy=10;
		if(kousi[cx][cy]){
			kousi[cx][cy]=0;
			--N;
		}
		cin>>M;
		for(int i=0;i > amida;

int main(){
	int n,m,a;

	while(cin>>n>>m>>a){
		if((n|m|a)==0)break;
		
		amida.clear();
		
		for(int i=0;i>h>>p>>q;
			
			amida[h][q]=p;
			amida[h][p]=q;
		}
		
		int h=1000;
		
		while(h){
			if(amida[h][a]==0){
				--h;
				continue;
			}
			
			//cout0)value+=125*n;
	n-=10;
	if(n>0)value+=15*n;
	n-=10;
	if(n>0)value+=20*n;
	return value;
}

int main(){
	int sui,sen,kon;
	

	sen=4280;
	
	
	while(cin>>sui){
		if(sui==-1)break;
		kon=kakaku(sui);
		cout>n){
		if(n==0)break;
		
		memset(kind,0,sizeof(kind));
		
		for(int i=0;i>k;
			++kind[k];
		}
		
		for(int i=0;i>n){
		if(n==0)break;
		
		for(int i=0;i>n;
			one[i]=n;
			++te[n];
		}
		
		int hiki=0;
		for(int i=1;i kyori;

int main(){
	int n;
	
	while(cin>>n){
		if(n==0)break;
		
		kyori.clear();
		int max,maxno;
		for(int i=0;i>p>>d1>>d2;
			kyori[p]=d1+d2;
			max=d1+d2;
			maxno=p;
		}
		
		for(map::iterator p=kyori.begin();p!=kyori.end();++p){
			if(p->second>max){
				max=p->second;
				maxno=p->first;
			}
		}
		cout>n){
		if(n==0)break;
		
		for(int i=0;i>pm>>pe>>pj;
			
			if(pm==100 || pe==100 || pj==100)puts("A");
			else if(pe+pm>=180)puts("A");
			else if(pe+pm+pj>=240)puts("A");
			else if(pe+pm+pj>=210)puts("B");
			else if(pe+pm+pj>=150 && (pe>=80 || pm>=80))puts("B");
			else puts("C");
		}
	}
	return 0;
}

aoj0222
10:57
素数は最近はエラトステネスの篩ぐらいしか使いませんね。回答者の実行速度やメモリサイズとかを見ると自分じゃぜんぜん追いつけない速さの人たちもいたりするので、どうなっているんだと驚くばかりです。コードサイズが大きい人はある程度ハードコードしてそうなんですが、500byte切っていて、なおかつ0.01とかの速度の人はどうなっているんでしょうかね？
ちなみに1TLEと1MLEを食らいました。

CODE:

char so[10000001];

main(){
	so[0]=so[1]=1;
	
	for(int i=2;i*i>n){
		if(n==0)break;
		
		while(1){
			if(so[n]|so[n-2]|so[n-6]|so[n-8]);
			else break;
			--n;
		}
		
		cout>d){
		if(d=pow(2,7-i)){
					d-=pow(2,7-i);
					pr[i]='1';
				}else{
					pr[i]='0';
				}
			}else if(i==8){
				pr[i]='.';
			}else{
				if(d>=pow(2,8-i)){
					d-=pow(2,8-i);
					pr[i]='1';
				}else{
					pr[i]='0';
				}
			}
		}
		
		if(d!=0)puts("NA");
		else puts(pr);
	}
	return 0;
}

aoj2216
13:36
A問題なので簡単ですね。ってか何で表示部分を関数にして分けてるんでしょうかね。

CODE:

void turi(int n){
	printf("%d %d %d\n",n%500/100,n%1000/500,n/1000);
}

main(){
	int a,b;
	while(cin>>a>>b){
		if(a==0 && b==0)break;
		
		turi(b-a);
	}
	return 0;
}

aoj2217
14:01
再帰をうまいこと使って何とか通せたと思います。結構考えるのが楽しい感じの問題でした。
探索をするようなコードは自分の中では高度な問題の部類になってしまうので、もうちょっと練習したいと思います。

CODE:

typedef struct t{
	int x,y;
	int loop;
	int scanned;
}za;

za gyou[100][100];

int loop;

int tansaku(int x,int y){
	if(gyou[x][y].scanned&&gyou[x][y].loop){
		return gyou[x][y].loop;
	}else if(gyou[x][y].scanned){
		++loop;
		gyou[x][y].loop=loop;
		return gyou[x][y].loop;
	}else{
		gyou[x][y].scanned=1;
		gyou[x][y].loop=tansaku(gyou[x][y].x,gyou[x][y].y);
	}
	return gyou[x][y].loop;
}

main(){
	int N;
	while(cin>>N){
		if(N==0)break;
		
		
		for(int i=0;i>x>>y;
				gyou[j][i].x=x;
				gyou[j][i].y=y;
				gyou[j][i].loop=0;
				gyou[j][i].scanned=0;
			}
		}
		
		loop=0;
		
		for(int i=0;i>n){
		if(n==0)break;
		
		for(int i=0;i>t;
				seki[j][i]=t;
				te[j][i]=0;
			}
		}
		
		for(int i=0;iseki[j][i]){
					max=seki[j][i];
					maxj=j;
				}
			}
			if(te[maxj][i]){
				cout>W>>Q){
		if(W==0 && Q==0)break;
		
		for(int i=0;i>c;
			
			if(c=='s'){
				int id,w;
				cin>>id>>w;
				
				int f=0,b=0;
				
				for(int i=0;i=w){
						cout>id;
				for(int i=0;i>n){
		if(n==0)break;
		
		int mem[n],min=0;
		
		for(int i=0;i>mem[i];
			min+=mem[i];
		}
		
		for(int i=0;i>j&1)po+=mem[j];
				else go+=mem[j];
			}
			if(abs(go-po)>D){
		if(D==0)break;
		
		double px,py,vx,vy,d;
		
		cin>>px>>py>>vx>>vy;
		
		if(py*vx==vy*px){
			
			double nvx=sqrt(px*px+py*py)*vx/sqrt(vx*vx+vy*vy),nvy=sqrt(px*px+py*py)*vy/sqrt(vx*vx+vy*vy);
			
			if(abs(nvx-px)D)puts("impossible");
		else printf("%.8lf\n",d);
	}
}

aoj1054
18:41
履歴管理が多少手間です。WとHの必要性がよく分かりませんでした。

CODE:

typedef struct _button{
	int xl,yu,xr,yl;
	string name;
}button;


map > page;
vector rireki;


main(){
	int n;
	while(cin>>n){
		if(n==0)break;
		
		page.clear();
		rireki.clear();
		
		int W,H;
		cin>>W>>H;
		
		for(int i=0;i>name>>b;
			if(i==0)rireki.push_back(name);
			for(int j=0;j>xl>>yu>>xr>>yl>>tname;
				button tbutton={xl,yu,xr,yl,tname};
				
				page[name].push_back(tbutton);
			}
		}
		
		int m;
		cin>>m;
		int p=0;
		
		for(int i=0;i>com;
			if(com=="click"){
				
				int x,y;
				cin>>x>>y;
				
				string target="";
				
				for(vector::iterator vp=page[rireki[p]].begin();vp!=page[rireki[p]].end();++vp){
					if(vp->xr>=x && vp->xlyuyl>=y)target=vp->name;
				}
				
				if(target=="")continue;
				
				if(p==rireki.size()-1){
					rireki.push_back(target);
					++p;
					
					
				}else{
					++p;
					rireki[p]=target;
					while(p+1>a>>b){
		if(a==0 && b==0)break;
		//printf("a %d b %d ",key(a),key(b));
		puts(key(a)>key(b)?"a":"b");
	}
}

aoj0105
19:50
mapはあらかじめ辞書順に格納されるようなので、それにたいしてイテレータでアクセスすればいいので楽な思いをしました。
が、最初　map > index;という感じで宣言したらコンパイルできなくて、いろいろと悩んでました。結局何でエラーだったのかいまだに分からず・・・。そんな名前の関数ありましたっけ？

CODE:

map > idx;


main(){
	string name;
	int page;
	
	while(cin>>name>>page){
		idx[name].push_back(page);
	}
	
	for(map >::iterator p=idx.begin();p!=idx.end();++p){
		
		coutfirstsecond.begin(),p->second.end());
		int sf=0;
		for(vector::iterator vp=p->second.begin();vp!=p->second.end();vp++){
			if(sf==1)cout>a>>b){
		if(a==0 && b==0)break;
		
		vector data;
		data.resize(4);
		int mins=a*a+b*b;
		for(int i=1;i*ii*i+j*j+k*k)mins=i*i+j*j+k*k;
					}
				}
			}
		}
		
		cout kyaku;

int main(){
	int n;
	while(cin>>n){
		if(n==0)break;
		
		kyaku.clear();
		
		for(int i=0;i>t;
			kyaku.push_back(t);
		}
		sort(kyaku.begin(),kyaku.end());
		ll ans=0;
		vector mati;
		mati.push_back(0);
		for(int i=0;i<n-1;i++){
			mati.push_back(mati[i]+kyaku[i]);
			ans+=mati[i+1];
		}
		
		
		cout<<ans<<endl;
	}
}

xxx · 投稿記事 by **xxx** » 14年前

今日はものすごい量解いてましたね
aoj0222は篩をしたときに求まった四つ子素数を別の場所に入れておくと早くなった気がします
memoryはわかりませんが・・・・

というかこんなに問題を解けるとは(- -;)
私は簡単な実装問題ぐらいしか解けてないんですよね
ほんとアルゴリズム勉強しないとなぁ

五反田 · 投稿記事 by **五反田** » 14年前

>>roxion1377さん
久しぶりにやったらものの見事にはまってしまいました。
自分も同じくで簡単な問題ぐらいしか解けないので、レーティングの順位だと2倍くらいに落ちるんですよね。

英語の問題にもっと手を出せれば少しば伸びるのでしょうかねぇ。

あーる@Reputeless · 投稿記事 by **あーる@Reputeless** » 14年前

つ、強すぎる・・・ (´∀｀;
こういうのがスラスラ解けるっていいなぁ～

ideyan · 投稿記事 by **ideyan** » 14年前

おぉ……凄いですね。
AOJは1051-1055の5問しかやったことがありません。
1056-1060もネタ満載なんで解きたいんですが能力が追いつかないんですよね……orz

レールガンは初撃か1回反射で当たらなかったら絶対当たらないということに
気付くまでに難儀した記憶があります＾＾；

五反田 · 投稿記事 by **五反田** » 14年前

>>あーるさん
逆に殆どこういうプログラミングしか出来ないので、なんだかなぁ、といった感じです。

>>ideyanさん
時々ネタ満載の問題があって面白いですよね。
超電磁砲は自分も、外から打ったら絶対に当たらなくね？みたいなことを最初に思って思考停止してました。

xxx · 投稿記事 by **xxx** » 14年前

ヒントなしで一発ACできた記念とehaさんにGolf買った記念に
AOJ0112

CODE:

long long s;n,d['~~'];
main(i){
  for(;scanf("%d",&n),n;printf("%lld\n",s)){
    for(i=n;i--;s=0)scanf("%d",d+i);
    for(qsort(d,n,4,"YZXRPQ\213\0+\x2\303");--n;)s+=d[n]*n;
  }
}

AOJ2001はソートして入れ替えれば結構早くなります

CODE:

#include
typedef struct{short h,p,q;}D;
int cmp(D*a,D*b){return a->h>b->h?1:-1;}
int main(void)
{
  short n,m,a,t[1001],i,p;
  D d[1001];
  for(;;){
    scanf("%hd%hd%hd",&n,&m,&a); if(!n)break;
    for(i=1;i<=n;i++){t[i]=i;}
    for(i=0;i<m;i++){scanf("%hd%hd%hd",&d[i].h,&d[i].p,&d[i].q);}
    qsort(d,m,sizeof(D),cmp);
    for(i=0;i<m;i++){
      p=t[d[i].p];
      t[d[i].p]=t[d[i].q];
      t[d[i].q]=p;
    }
    printf("%hd\n",t[a]);
  }
  return 0;
}

オンラインジャッジ日和

オンラインジャッジ日和

Re: オンラインジャッジ日和

Re: オンラインジャッジ日和

Re: オンラインジャッジ日和

Re: オンラインジャッジ日和

Re: オンラインジャッジ日和

Re: オンラインジャッジ日和

		8月 2025
日	月	火	水	木	金	土
					1	2
3	4	5	6	7	8	9
10	11	12	13	14	15	16
17	18	19	20	21	22	23
24	25	26	27	28	29	30
31