「AOJ261～270」の編集履歴（バックアップ）一覧に戻る
AOJ261～270 - (2013/02/19 (火) 01:21:43) のソース
*0261 Mayan Crucial Prediction
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0261
西暦をマヤ暦にマヤ暦を西暦に戻す問題。
解法
西暦をマヤ暦に戻すのは簡単でしたが、マヤ暦を西暦に戻すのは難しいですね。
手元のＧＣＣのtime_tが４バイトだったので値溢れが起きてtime.hで効率よくといきませんでした。
なので頭悪くひと月ごと引いていって計算しています。
ああ頭が悪い、、、
Ｃ＃使えば標準機能で西暦数万年とか扱えるのかな？
javascriptで解いても良かったかも。
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#include<iostream>
long long int GetDays(long long int y,long long int m,long long int d){
// 1・2月 → 前年の13・14月
if (m <= 2){
--y;
m += 12;
}
long long int dy = 365 * (y - 1); // 経過年数×365日
long long int c = y / 100;
long long int dl = (y >> 2) - c + (c >> 2); // うるう年分
long long int dm = (m * 979 - 1033) >> 5; // 1月1日から m 月1日までの日数
return dy + dl + dm + d - 1;
}
static int mdays[2][13] = {
{31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}, /* 平年 */
{31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}, /* 閏年 */
};
int isleap(int year){
return (year % 4 == 0 && year % 100 != 0 || year % 400 == 0);
}
struct YMD{
int y,m,d;
};
YMD after(YMD x, int n){
x.d += n;
while (x.d > mdays[isleap(x.y)][x.m - 1]) {
x.d -= mdays[isleap(x.y)][x.m - 1];
if (++x.m > 12) {
x.y++;
x.m = 1;
}
}
return (x);
}
int main(){
int b,ka,t,w,ki,y,m,d;
char text[100];
int startDay=GetDays(2012,12,21);
YMD baseDay;
baseDay.y=2012;
baseDay.m=12;
baseDay.d=21;
int mod=13*20*20*18*20;
while(1){
scanf("%s",text);
if(text[0]=='#')break;
int count=0;
for(int i=0;text[i]!='\0';i++)count+=(text[i]=='.');
if(count==2){
//西暦をマヤ暦に
sscanf(text,"%d.%d.%d",&y,&m,&d);
long long int day=(GetDays(y,m,d)-startDay)%mod;
ki=day%20;
day/=20;
w=day%18;
day/=18;
t=day%20;
day/=20;
ka=day%20;
day/=20;
b=day%13;
printf("%d.%d.%d.%d.%d\n",b,ka,t,w,ki);
}else{
//マヤ暦を西暦に
sscanf(text,"%d.%d.%d.%d.%d",&b,&ka,&t,&w,&ki);
int now=b*20*20*18*20+ka*20*18*20+t*18*20+w*20+ki;
YMD ans=after(baseDay,now);
printf("%d.%d.%d\n",ans.y,ans.m,ans.d);
}
}
}
*0262 Making Sugoroku
すごろくで絶対にゴールにたどり着けなくなる袋小路があるかをチェックする問題。
解法
すごろくをグラフとみて深さ優先探索してゴールにたどり着けないループを探します。
#include<stdio.h>
#include<string.h>
int n,m,board[260];
bool saiki(int p,int spents[260]){
if(p<0)p=0;
if(p>=m+1){
return true;
}
if(spents[p]==1)return false;
spents[p]=1;
bool re=false,t;
for(int i=1;i<=n;i++){
int nextP=p+i;
if(nextP>m+1)nextP=m+1;
nextP+=board[nextP];
if(nextP>m+1)nextP=m+1;
if(nextP<0)nextP=0;
t=saiki(nextP,spents);
re=re||t;
}
return re;
}
void dataSet(){
scanf("%d",&m);
for(int i=1;i<=m;i++)scanf("%d",&board[i]);
board[0]=board[m+1]=0;
int spents[260]={0};
bool ok=saiki(0,spents);
for(int i=1;i<=m;i++){
if(spents[i]==0)continue;
int spents2[260]={0};
ok=ok&&saiki(i,spents2);
}
printf("%s\n",ok?"OK":"NG");
}
int main(){
while(1){
scanf("%d",&n);
if(n==0)break;
dataSet();
}
}
*aoj263 Beat Panel
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0263
架空のパズルゲームで得られる最高得点を計算する問題。
*解法
ビープ音一回ごとで動的計画法を適用すれば答えはでますが時間制限が２秒と厳しい問題です。
速度アップのためにビット演算を使用したり、メモ化したりと色々工夫してます。
他の人のコード見てるとstd::mapを使わずＤＰを配列にして単純にループすれば速度出るみたいです。
#include<stdio.h>
#include<map>
#include<bitset>
#include<time.h>
#include<string.h>
int numofbits5(int bits)
{
bits = (bits & 0x55555555) + (bits >> 1 & 0x55555555);
bits = (bits & 0x33333333) + (bits >> 2 & 0x33333333);
bits = (bits & 0x0f0f0f0f) + (bits >> 4 & 0x0f0f0f0f);
bits = (bits & 0x00ff00ff) + (bits >> 8 & 0x00ff00ff);
return (bits & 0x0000ffff) + (bits >>16 & 0x0000ffff);
}
void calc(int n,int c){
int fingers[32],lights[32];
std::map<int,int> memo[32];
std::map<int,int>::iterator it;
int perm,perm2;
for(int i=0;i<n;i++){
int bit=1;
int finger=0;
int a;
for(int j=0;j<16;j++){
scanf("%d",&a);
finger|=(a*bit);
bit*=2;
}
lights[i]=finger;
}
for(int i=0;i<c;i++){
int bit=1;
int finger=0;
int b;
for(int j=0;j<16;j++){
scanf("%d",&b);
finger|=((b==1?0:1)*bit);//and演算子で消す
bit*=2;
}
fingers[i]=finger;
}
fingers[c]=65535;//何も押さない、これに何か意味が？
memo[0][0]=0;
int ans=0;
int check[65540];
for(int i=0;i<n;i++){
memset(check,-1,sizeof(check));
for(it=memo[i].begin();it!=memo[i].end();it++){
int p=(*it).first | lights[i];
int score=(*it).second;
perm=numofbits5(p);
for(int j=0;j<=c;j++){
int nextP=p&fingers[j];
perm2=numofbits5(nextP);
int nextScore=score+(perm-perm2);
if(check[nextP]!=-1&&check[nextP]>=nextScore)continue;
check[nextP]=nextScore;
memo[i+1][nextP]=nextScore;
if(ans<nextScore)ans=nextScore;
}
}
memo[i].clear();
}
printf("%d\n",ans);
}
int main(){
int n,c;
while(1){
scanf("%d %d",&n,&c);
//double t=clock();
if(n==0&&c==0)break;
calc(n,c);
//printf("\n(%lf)",clock()-t);
}
}
*264 Finite Field Calculator
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0264
解法
再帰下降構文解析で計算式をmod演算に置き換えるだけです。
再帰下降構文解析は論理的にできるかできないかの二択になるので、バグが出てもデバッグモードで追いかけにくいのが少し苦手で速度も出ませんでした。
データの読み込み部分か、ＤＩＶのテーブルを作る部分で速度低下になっているようです。
#include<stdio.h>
#include<string>
#include<stdlib.h>
#include<vector>
#include<iostream>
bool isErr;
long long int mod;
std::vector<std::string> formula;
long long int divTable[50000];
void ExGCD(long long int x,long long int y,long long int& a,long long int& b,long long int& c){
long long int r0=x,r1=y,a0=1,a1=0,b0=0,b1=1;
long long int q1,r2,a2,b2;
while (r1>0){
q1 = r0/r1;
r2 = r0%r1;
a2 = a0-q1*a1;
b2 = b0-q1*b1;
r0 = r1;
r1 = r2;
a0 = a1;
a1 = a2;
b0 = b1;
b1 = b2;
}
c = r0;
a = a0;
b = b0;
}
long long int saiki(int& p,int pr){
long long int x,y;
while(formula.size()>p){
std::string str=formula[p];
char c=str[0];
if(c=='('){
p++;
x=saiki(p,0);
p++;
}else if(c==')'){
return x;
}else if(c=='+'){
if(pr>=1){
return x%mod;
}
p++;
y=saiki(p,1);
x=(x+y)%mod;
}else if(c=='-'){
if(pr>=1){
return x%mod;
}
p++;
y=saiki(p,1);
x=(x+mod-y)%mod;
}else if(c=='*'){
if(pr>=2){
return x%mod;
}
p++;
y=saiki(p,2);
x=(x*y)%mod;
}else if(c=='/'){
if(pr>=2){
return x%mod;
}
p++;
y=saiki(p,2);
if(y==0){
p=formula.size();
isErr=true;
return 0;
}else{
x=(x*divTable[y])%mod;
}
}else{
x=0;
for(int i=0;i<str.size();i++){
x*=10;
x+=str[i]-'0';
}
p++;
}
}
return x%mod;
}
int main(){
char c;
long long int a1,b1,c1;
while(1){
std::cin>>mod;
if(mod==0)break;
for(long long int i=1;i<mod;i++){
ExGCD(i,mod,a1,b1,c1);
while(a1<0)a1+=mod;
a1%=mod;
divTable[i]=a1;
//std::cout<<"("<<i<<" "<<a1<<")";
}
formula.clear();
scanf("%c",&c);
isErr=false;
while(c!='\n'){
if(c=='+'||c=='-'||c=='*'||c=='/'||c=='('||c==')'){
std::string str="";
str+=c;
formula.push_back(str);
scanf("%c",&c);
}else if('0'<=c&&c<='9'){
std::string str="";
while('0'<=c&&c<='9'){
str+=c;
scanf("%c",&c);
}
formula.push_back(str);
}else{
scanf("%c",&c);
}
}
int point=0;
long long int ans=saiki(point,0);
if(isErr==true){
printf("NG\n");
}else{
for(int i=0;i<formula.size();i++){
std::cout<<formula[i];
}
std::cout<<" = "<<ans<<" (mod"<<" "<<mod<<")\n";
}
}
}
*266 Aka-beko and 40 Thieves
グラフ上を移動する集団が指定された移動手順でゴールにたどり着けるか答える問題。
解法
グラフ化してシミュレートするだけです。
#include<stdio.h>
int main(){
int G[6][2]={ { 1, 2}
,{-1, 4}
,{ 1,-1}
,{ 5, 2}
,{ 3, 5}
,{ 2, 1}};
char p[110];
while(1){
scanf("%s",&p);
int now=0;
if(p[0]=='#')break;
for(int i=0;p[i]!='\0';i++){
now=G[now][p[i]-'0'];
if(now==-1)break;
}
printf("%s\n",now==5?"Yes":"No");
}
}
*0267 Triangle of Blocks
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0267
ブロックの集まりに一定の操作を行って三角形の階段を作るとき何回の操作で階段になるか求める問題。
解法
順当にstd::listを使ってシミュレートするだけです。
#include<stdio.h>
#include<list>
#include<set>
int main(){
std::set<int> oks;
int sum=0;
for(int i=1;sum<=10000*100+1;i++){
sum+=i;
oks.insert(sum);
}
while(1){
int n,b;
scanf("%d",&n);
if(n==0)break;
int sum=0;
std::list<int> yama;
std::list<int>::iterator it;
for(int i=0;i<n;i++){
scanf("%d",&b);
sum+=b;
yama.push_back(b);
}
if(oks.find(sum)==oks.end()){
printf("-1\n");
continue;
}
int ans=-1;
for(int i=1;i<=10001;i++){
bool ok=true;
int no=1;
for(it=yama.begin();it!=yama.end();it++,no++){
if(no!=(*it)){
ok=false;
break;
}
}
if(ok==true){
ans=i-1;
break;
}
if(i==10001)break;
int sum=0;
it=yama.begin();
while(it!=yama.end()){
(*it)--;
sum++;
if((*it)==0){
it=yama.erase(it);
}else{
it++;
}
}
yama.push_back(sum);
}
printf("%d\n",ans);
}
}
*268 Kongo Type
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0268
32bitの実数型を実装する問題。
解法
とりあえずdouble型は2進数で表せる数なら小数部+実数部の桁数が１５桁を超えない限り誤差が出ないということを利用してdouble型で型をシミュレートしました。
なんかナンセンスマシーンを書いてしまったような気がします。
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int main(){
int ts[8],as[7],bs[2];
char s[10],last[30];
int n;
scanf("%d",&n);
for(int i=0;i<n;i++){
scanf("%s",s);
double ans=0;
for(int i=0;i<8;i++){
sscanf(&s[i],"%1x",&ts[i]);
}
if(ts[0]>=8){
ts[0]-=8;
printf("-");
}
bs[0]=(7&ts[6]);
bs[1]=ts[7];
ts[6]=(8&ts[6]);
double d=1.0/8.0;
for(int i=6;i>=0;i--){
ans+=d*ts[i];
d*=16.0;
}
d=1.0/8.0;
ans+=d*bs[0]+(d*1.0/16.0)*bs[1];
sprintf(last,"%.7lf",ans);
int len=strlen(last);
for(int i=len-1;i>0;i--){
if(last[i]!='0'||last[i-1]=='.')break;
last[i]='\0';
}
printf("%s\n",last);
}
}
*269 East Wind
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0269
日々変わる風向きから家に木の香りが届くか計算する問題。
解法
扇形の範囲内であるということは木を原点に家の相対座標を出しその座標をv(x,y)としたとき、内積の概念を使って風とvのcosがもとまります。
cosが範囲内でかつ家が扇の半径内ならその木の香りが届くとなります。
地道に一つ一つ計算していけば答えが出ます。
#include<stdio.h>
#include<math.h>
bool areaIn(double x1,double y1,double x2,double y2,double len,double cos1){
//風の向きx1,y1,木を原点とした時の家の相対座標x2,y2
if(hypot(x2,y2)>len)return false;//距離が遠かった
double t= (x1*x2+y1*y2)/(hypot(x1,y1)*hypot(x2,y2));//扇の範囲内
return t>=cos1;
}
void calc(int H,int R){
double hxs[101],hys[101];
for(int i=0;i<H;i++){
scanf("%lf %lf",&hxs[i],&hys[i]);
}
int U,M,S;
double du,dm,ds,uxs[11],uys[11],mxs[11],mys[11],sxs[11],sys[11];
scanf("%d %d %d %lf %lf %lf",&U,&M,&S,&du,&dm,&ds);
double cosU,cosM,cosS;
cosU=cos(0.5*du/180.0*M_PI);
cosM=cos(0.5*dm/180.0*M_PI);
cosS=cos(0.5*ds/180.0*M_PI);
for(int i=0;i<U;i++){
scanf("%lf %lf",&uxs[i],&uys[i]);
}
for(int i=0;i<M;i++){
scanf("%lf %lf",&mxs[i],&mys[i]);
}
for(int i=0;i<S;i++){
scanf("%lf %lf",&sxs[i],&sys[i]);
}
int ans[101]={0};
double w,a;
int max=0;
for(int i=0;i<R;i++){
scanf("%lf %lf",&w,&a);
double cosW=cos(w/180.0*M_PI);
double sinW=sin(w/180.0*M_PI);
for(int j=0;j<H;j++){
if(areaIn(cosW,sinW,hxs[j],hys[j],a,cosU)==false)continue;//私の梅から遠かった
bool ok=true;
for(int k=0;k<U;k++){
if(ok==false)break;
if(areaIn(cosW,sinW,hxs[j]-uxs[k],hys[j]-uys[k],a,cosU))ok=false;
}
for(int k=0;k<M;k++){
if(ok==false)break;
if(areaIn(cosW,sinW,hxs[j]-mxs[k],hys[j]-mys[k],a,cosM))ok=false;
}
for(int k=0;k<S;k++){
if(ok==false)break;
if(areaIn(cosW,sinW,hxs[j]-sxs[k],hys[j]-sys[k],a,cosS))ok=false;
}
if(ok==true)ans[j]++;
if(max<ans[j])max=ans[j];
}
}
if(max==0){
printf("NA\n");
}else{
int count=0;
for(int i=0;i<H;i++){
if(ans[i]==max){
if(count>0)printf(" ");
printf("%d",i+1);
count++;
}
}
printf("\n");
}
}
int main(){
int H,R;
while(1){
scanf("%d %d",&H,&R);
if(H==0&&R==0)break;
calc(H,R);
}
}
*270 Modular Query
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0270
数字の書かれた３０万枚のカードがある。
指定された数字で全てのカードの数字を割り、そのあまりを取った時、もっとも大きなあまりは幾つになるか。
指定は１０万個存在する。
解法
カードを割りますが、割る数ｎでni～n(i+1)までの数で最も余りが大きくなるのはn(i+1)に最も近いカードです。
これだけ優先して探せばアッという今に答えが出ます。
#include<stdio.h>
#include<string.h>
#include<set>
const int up=300000;
int main(){
int n,q,c;
std::set<int> cards;
scanf("%d %d",&n,&q);
for(int i=0;i<n;i++){
scanf("%d",&c);
cards.insert(c);
}
int num;
for(int i=0;i<q;i++){
scanf("%d",&num);
int ans=0;
for(int i=0;i*num<=up;i++){
std::set<int>::iterator it=cards.lower_bound(i*num);
if(it==cards.begin()){
if((*it)%num>ans)ans=(*it)%num;
}else if(it==cards.end()){
it--;
if((*it)%num>ans)ans=(*it)%num;
}else{
if((*it)%num>ans)ans=(*it)%num;
it--;
if((*it)%num>ans)ans=(*it)%num;
}
if(ans==num-1)break;
}
printf("%d\n",ans);
}
}
