0261 Mayan Crucial Prediction
解法
西暦をマヤ暦に戻すのは簡単でしたが、マヤ暦を西暦に戻すのは難しいですね。
手元のＧＣＣの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
解法
ビープ音一回ごとで動的計画法を適用すれば答えはでますが時間制限が２秒と厳しい問題です。
速度アップのためにビット演算を使用したり、メモ化したりと色々工夫してます。
他の人のコード見てると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
解法
再帰下降構文解析で計算式を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
解法
順当に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
解法
とりあえず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
解法
扇形の範囲内であるということは木を原点に家の相対座標を出しその座標を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
解法
カードを割りますが、割る数ｎで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);
}
}
最終更新：2013年02月19日 01:21
