「AOJ再挑戦86～90」の編集履歴（バックアップ）一覧に戻る
AOJ再挑戦86～90 - (2014/02/04 (火) 21:54:13) のソース
*問86 Patrol
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0086
一筆書きの判定問題
解法
一筆書きの判定をそのまま。
#include<stdio.h>
int main(){
int a,b;
while(scanf("%d %d",&a,&b)!=EOF){
int c[255]={0};
c[a]++;
c[b]++;
while(scanf("%d %d",&a,&b)){
if(a==0&&b==0)break;
c[a]++;
c[b]++;
}
bool ok=(c[1]%2)&(c[2]%2);
for(int i=3;i<101;i++){
if(c[i]%2==1)ok=false;
}
printf("%s\n",ok?"OK":"NG");
}
*問87 Strange Mathematical Expression
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0087
逆ポーランド記法で表記された式を計算する問題
解法
スタック使った実装ゲーム。
#include<stdio.h>
#include<stack>
#include <ctype.h>
#include <stdlib.h>
int main(){
while(1){
char siki[10],c;
double a,b;
std::stack<double> nums;
while(scanf("%s%c",siki,&c)!=EOF){
if(isdigit(siki[0])||siki[1]!='\0'){
nums.push(atof(siki));
}else{
b=nums.top(),nums.pop();
a=nums.top(),nums.pop();
switch(siki[0]){
case '+': nums.push(a+b); break;
case '-': nums.push(a-b); break;
case '*': nums.push(a*b); break;
case '/': nums.push(a/b); break;
}
}
if(c=='\n')break;
}
printf("%lf\n",nums.top());
if(scanf("[\n]",&c)==EOF)break;
}
}
*問88 The Code A Doctor Loved
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0088
文字列圧縮の問題。
解法
対応表を作るくらいしか思いつかないです。
列を文字列指定してExcelのA列に表をコピペして
=CONCATENATE("ctos","['",A1,"']=""",,B1,"""")
と、あとは\が必要な文字だけ修正すればstd::mapの対応表を作る時間がかかりません。
それくらいですね。
あとは２つ目の表はAからZまではビットがきれいに並んでるので自動生成するだけです。
長いのでカット。
*問89 The Shortest Path on A Rhombic Path
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0089
菱形の計算。
解法
一段ずつの動的計画法。
斜めにしたら縦横だしもうちょっと書きようはあるかな。
#include<stdio.h>
#include<algorithm>
#include<string.h>
int main(){
int row[52]={0};
int oldRowSize=0;
char c;
int memo[52]={0};
while(1){
int next[52]={0};
int nowRowSize=0;
while(scanf("%d%c",&row[nowRowSize],&c)!=EOF){
nowRowSize++;
if(c=='\n')break;
}
for(int i=0;i<nowRowSize-(oldRowSize<nowRowSize);i++){
next[i]=memo[i]+row[i];
}
if(oldRowSize<nowRowSize){
for(int i=1;i<nowRowSize;i++){
next[i]=std::max(next[i],memo[i-1]+row[i]);
}
if(nowRowSize==1)next[0]=row[0];
}else{
for(int i=1;i<oldRowSize;i++){
next[i-1]=std::max(next[i-1],memo[i]+row[i-1]);
}
}
memcpy(memo,next,sizeof(memo));
if(nowRowSize==1&&nowRowSize<oldRowSize)break;
oldRowSize=nowRowSize;
}
printf("%d\n",memo[0]);
}
*問90 Overlaps of Seals
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0090
平面上でシールが最大限重なってる場所を求める問題。
解法
交点か円の中心だけをチェックすればよいです。
原点に片方の円の中心を、片方をX軸状にとり交点を求め、これを回転して平行移動して交点を求めます。
#include<stdio.h>
#include<vector>
#include<math.h>
void crossDXY_Sub(double len,double &reX1,double& reY1){
double herfLen=len/2;
reX1=herfLen;
reY1=sqrt(1-herfLen*herfLen);
}
void crossDXY(double dx,double dy,double& reX1,double& reY1,double& reX2,double& reY2){
double x1,y1,len,sinX,cosX;
len=hypot(dx,dy);
crossDXY_Sub(len,x1,y1);
sinX=dy/len;
cosX=dx/len;
reX1=x1*cosX-y1*sinX;
reY1=x1*sinX+y1*cosX;
reX2=x1*cosX+y1*sinX;
reY2=x1*sinX-y1*cosX;
}
void calc(int n){
double xs[101],ys[101];
std::vector<double> crossX,crossY;
for(int i=0;i<n;i++){
scanf("%lf,%lf",&xs[i],&ys[i]);
crossX.push_back(xs[i]);
crossY.push_back(ys[i]);
}
for(int i=0;i<n;i++){
for(int j=i+1;j<n;j++){
double dx=xs[j]-xs[i];
double dy=ys[j]-ys[i];
if(dx==0&&dy==0)continue;
if(dx*dx+dy*dy<=4){
double x1,x2,y1,y2;
crossDXY(dx,dy,x1,y1,x2,y2);
crossX.push_back(x1+xs[i]);
crossY.push_back(y1+ys[i]);
crossX.push_back(x2+xs[i]);
crossY.push_back(y2+ys[i]);
//printf("(%lf %lf %lf %lf)",x1+xs[i],y1+ys[i],x2+xs[i],y2+ys[i]);
}
}
}
int ans=0;
for(int i=0;i<crossX.size();i++){
double x=crossX[i];
double y=crossY[i];
int count=0;
for(int j=0;j<n;j++){
double dx=xs[j]-x;
double dy=ys[j]-y;
if(dx*dx+dy*dy<=1.0000001)count++;
}
if(ans<count)ans=count;
}
printf("%d\n",ans);
}
int main(){
int n;
while(scanf("%d",&n)!=EOF){
if(n==0)break;
calc(n);
}
}
