2011-04-03
The 11th Zhejiang University Programming Contest
その他コンテスト |
http://acm.zju.edu.cn/onlinejudge/showContestRankList.do?contestId=324
どうも開催されていたようなので参加してきました。
UVaでもあったようで出たかったのですが、時間を把握してないうちに終わってしまったようです。残念。
取り敢えずAをひらいてみる。
普通に無理そうなので、しばらく待機して一番最初に解かれていたJを開く。
やるだけ。
main(){
int t;
cin>>t;
while(t--){
int p;
cin>>p;
int t;
map<int,int> app;
rep(i,p){
cin>>t;
app[-t]++;
}
int ans,ansn=0;
FOR(miter,app){
if(miter->S>ansn){
ansn=miter->S;
ans=-miter->F;
}
}
cout<<ans<<endl;
}
}
次にCを開く。Zodiacは十二支という意味だとは知りませんでしたね。これも書くだけなのかと思ったのですが、与えられた年における干支を答える問題かと思って書くと、サンプルが合わないので適当に順番を逆に変えると通りました。
そのときは逆順に回るものなのだとか考えて、さっさと次にいってしまったのですが、今更ながら、与えられるのが年齢でその人の生まれた年の干支を答えるんだと理解しました。
main(){
int t;
cin>>t;
while(t--){
int p;
cin>>p;
switch(p%12){
case 2:cout<<"Tiger";break;
case 1:cout<<"Rabbit";break;
case 0:cout<<"Dragon";break;
case 11:cout<<"Snake";break;
case 10:cout<<"Horse";break;
case 9:cout<<"Ram";break;
case 8:cout<<"Monkey";break;
case 7:cout<<"Rooster";break;
case 6:cout<<"Dog";break;
case 5:cout<<"Pig";break;
case 4:cout<<"Rat";break;
case 3:cout<<"Ox";break;
}
cout<<endl;
}
}
次にACが多いGへ。ガウス素数というものの個数を数えるらしいです。最初意味が分からずに日本語wikipediaを読んだりしましたが、ようするに問題文の二つの条件のどちらかに引っかかるものの数を答えれば良さそうなので、書く。
TLE。
素数判定をO(n^(1/2))にするとWAになりました。
ここからしばらくはまりタイムに。ガウス整数の判定関数にいくつかバグがあったりしたのですが、出力形式の最後のほうに書いている既約分数で出力というのを完全に見落としていたのがかなり痛かったです。それを直してAC。
bool isg(int a,int b){ rep(tt,2){ if(a==0 && b!=0 && abs(b)%4==3){ bool ok=true; for(int i=2;i*i<=abs(b);i++){ if(b%i)continue; ok=false; break; } if(ok)return true; } swap(a,b); } ll k=ll(a)*a+ll(b)*b; if(k==2)return true; if(a && b && k%4==1){ bool ok=true; for(ll i=2;i*i<=k;i++){ if(k%i)continue; ok=false; break; } if(ok)return true; } return false; } main(){ int t; cin>>t; while(t--){ int x1,x2,y1,y2; cin>>x1>>x2>>y1>>y2; int c=0,p=0; for(int i=x1;i<x2+1;i++){ for(int j=y1;j<y2+1;j++){ ++p; if(isg(i,j)){ //cout<<i<<' '<<j<<endl; ++c; } } } cout<<c/__gcd(c,p)<<'/'<<p/__gcd(c,p)<<endl; } }
次は、その時点で正解数が多かったのはIだったのですが、どちらかというとDのほうが面白そうだったのでそちらを先に解くことに。(決してIの問題文が長くて面倒だったわけではないです)
最初は独自にクラスを作ろうと思ったのですが、setやmapに突っ込むためのコードの書き方が分からなかったので、pairとかを使わせてもらいました。
あとは与えられた命令を素直に実装していくだけでした。
一発AC。
typedef map<string,pair<string,set<string> > > cla; main(){ int t; cin>>t; while(t--){ string in; while(getline(cin,in))if(in=="begin")break; cla exist; while(getline(cin,in)){ if(in=="end")break; if(in.substr(0,5)=="class"){ string cname,sname; int pos=in.find(':'); if(pos>=0){ cname=in.substr(6,pos-6); sname=in.substr(pos+1); }else{ cname=in.substr(6); } if(exist.count(cname)){ cout<<"oops!"<<endl; continue; } if(sname.size() && exist.count(sname)==0){ cout<<"oops!"<<endl; continue; } exist[cname]; if(sname.size())exist[cname].F=sname; cout<<in<<endl; }else if(in.substr(0,3)=="def"){ string cname=in.substr(4,in.find('.')-4); string mname=in.substr(in.find('.')+1); if(exist.count(cname)==0){ cout<<"oops!"<<endl; continue; } if(exist[cname].S.count(mname)){ cout<<"redef "<<cname<<'.'<<mname<<endl; }else{ exist[cname].S.insert(mname); cout<<in<<endl; } }else if(in.substr(0,5)=="undef"){ string cname=in.substr(6,in.find('.')-6); string mname=in.substr(in.find('.')+1); if(exist.count(cname)==0 || exist[cname].S.count(mname)==0){ cout<<"oops!"<<endl; }else{ exist[cname].S.erase(mname); cout<<in<<endl; } }else{//call string cname=in.substr(5,in.find('.')-5); string mname=in.substr(in.find('.')+1); bool ok=false; while(exist.count(cname)){ if(exist[cname].S.count(mname)){ ok=true; cout<<"invoke "<<cname<<'.'<<mname<<endl; break; } cname=exist[cname].F; } if(!ok)cout<<"oops!"<<endl; } } cout<<endl; } }
次にIへ。若干TLEが怖かったのですが、要するに、日付を全探索すれば良いということだと思ったので、日付を生成するためにhttp://d.hatena.ne.jp/atetubou/20110324/1300943742からコードを引っ張ってきました。そして、その日付文字列と日付のチェックサムをあらかじめ計算しておきました。
で、ここからバグバグに。
まずおかしかったのは、出力文字列の抽出箇所でした。あとは、添字がところどころおかしかったりしたのですが、一番の問題は日付の生成でした。
まず、日付の生成を2011年4月2日で打ち切らなかったこと。そして、1900年は閏年ではないということをすっかり忘れていたことです。
string day[4000000]; int dayw[4000000]; int mon[]={31,28,31,30,31,30,31,31,30,31,30,31}; int wi[]={7,9,10,5,8,4,2,1,6,3,7,9,10,5,8,4,2,1}; main(){ int y=1900,m=1,d=1; int num=0; rep(i,4000000){ if(y==2011 && m==4 && d==3)break; ++num; int ty=y,tm=m,td=d; day[i]+=ty/1000+'0'; ty%=1000; day[i]+=ty/100+'0'; ty%=100; day[i]+=ty/10+'0'; ty%=10; day[i]+=ty+'0'; day[i]+=tm/10+'0'; day[i]+=tm%10+'0'; day[i]+=td/10+'0'; day[i]+=td%10+'0'; int tw=0; rep(j,8){ tw+=(day[i][j]-'0')*wi[j+6]; } dayw[i]=tw; if(m==12 && d==31){ y++; m=1; d=1; if((y%4==0 && y%100!=0) || y%400==0)mon[1]=29; else mon[1]=28; continue; } if(d==mon[m-1]){ ++m; d=0; } ++d; } int t; cin>>t; while(t--){ string in; cin>>in; if(in.size()==15){ int ans=16,idx=0; rep(i,num){ int tans=0; rep(j,6){ if(in[j+6]!=day[i][j+2])++tans; } if(tans<ans){ ans=tans; idx=i; if(ans==0)break; } } cout<<in.substr(0,6)<<day[idx].substr(2)<<in.substr(12)<<endl; }else{ int tw=0; int ans=16,idx; char last; rep(i,17){ if(i==6)i=14; tw+=wi[i]*(in[i]-'0'); } rep(i,num){ int tans=0; rep(j,8){ if(in[j+6]!=day[i][j])++tans; } int sw=tw+dayw[i]; int a=(12-sw%11)%11; if((a==10 && in[17]!='X') || (a!=10 && in[17]-'0'!=a))++tans; if(tans<ans){ ans=tans; idx=i; last=a+'0'; if(a==10)last='X'; } } cout<<in.substr(0,6)<<day[idx]<<in.substr(14,3)<<last<<endl; } } }
これで5問AC。
残り時間は1時間ちょっとなので、もう一問くらい解けそうだと思ったのですが、問題文とAC数から判断するに、BかEしか自分には残っていないように思われました。
文字列処理系はDで調子が良かったので、せっかくだからということでEを選んだのですが、WAからPEに変わった後は何をどうやってもPEのままでした。
コンテストが終わってから、問題文をよく読むとtabが出現していた場合の処理を変に分岐させていたので、それを直してからsubmitしてみたものの結局PE。
どこがおかしいのか分からないままモヤモヤしてます。
結局5問解いて、28位でした。1問以上解いている人が404人いるようなのでなかなかいい順位にはつけていたのではないかと思います。まぁ、UVaのコンテストに流れた人が多かったようですけどね！！