Hatena::Grouptopcoder

敗戦記

2011-04-16

Codeforces Beta Round #68

| 10:45

あまりに眠すぎるうえにCが解けないので途中で寝てしまいました。

A

  • 開く。map<int,string>に点数を負にしてつっこむ。

4分

B

  • 問題文が長いけれど頑張って読む。
  • キューに突っ込んで、幅優先探索を書く。
  • 2回ほどプリテストでWAをだした後通過。

45分

C

  • 開く。ここらへんで眠気が高まってきて、問題文の意味の把握にも手間取る。
  • Nクイーン問題に似たような奴っぽい?
  • 紙にいくつか小さいケースを書いてみても結局分からなかったので、眠かったこともあり、残り30分ぐらいで寝ました。

System Test

  • oo--- Bは微妙な感じがしたので安心しました。

1633 -> 1666 (+33) 紫に戻れました。

HillHill2012/11/15 02:46You're a real deep thinker. Thanks for sharnig.

ftcfwuknftcfwukn2012/11/15 12:37Hmh9Qx <a href="http://inqrsekwlrnt.com/">inqrsekwlrnt</a>

2011-04-14

Codeforces Beta Round #67 (Div. 2)

| 22:27

翌日は一限からでしたが試しに参加してみました。

前回、前々回がいろいろと酷い出来で凹んでいたので、満足のいく回で良かったです。

A

  • long longから0を省いてstring型にする関数と、stringを数字にする関数を書いた。

4分

B

  • 実装ゲー。
  • mapとか使いながら、pair<int,string>の配列にintをマイナスにしてつっこんでソートして出力した。

16分

C

  • 読む。最初TLEしない解法がすぐに思い浮かばない。
  • でも他の人達は即効で解いている人もいるので、そこまで難しくないのだろうと考える。
    • 最大公約数の約数を全列挙することにした。
  • あとは約数を-にして突っ込んだvectorをソートしてlower_boundした。
  • 提出した後に微妙にlong longを使っていなかったことにビクビクしていた。

36分

このあとDとEを読むが、Eは幾何なので無理で、DはTLEしない解法が思いつきそうになかったのでhack狙いで提出しようかなどと考えて取り合えずCのハックへ。

Hack

  • Cであきらかに一つのクエリにO(gcd(a,b))欠けている人が居たので落としました。
  • ここらへんでよくみると去年一緒にICPCに出てくれた先輩が同じ部屋だということに気づく。
    • ただ、Cで一つのクエリをO(gcd(a,b)^(1/2))で処理していて、これだと最大で1万×1万以上になり、ギリギリ間に合わさそうなので落とさせていただきました。

D

  • ここらへんであとは約数を全列挙しているものしか残っていないのでDのTLE解を書く。
  • 最小値を0にしたままだったのでプリテスト通らない。
    • 直してアクセプト

95分

Hack

  • 明らかに自分と同じ解法の人が居たので、急いでDのジェネレーターを書く。
  • 入力の形式を勘違いして何回か向こう側で弾かれる。
    • なんとか直して提出。
  • 二人ほど落とす。
  • 最後にCでTLEしそうな人が居たので落とす。

一限からなので終わったら速攻で寝ました。

SystemTest

  • ooox- Dは寝ながら考えていたのですが、解法全然思いつきませんでしたね。

結局3問とハック点500点で3212点で部屋一位、参加者全体では46位でした。

TLEが狙える回は、ソースコードを細かいところまで見る必要がなく、forの個数とかだけを見ればいいので恐ろしく楽でいいと思います。

ただ、部屋内でSystemTestで結構落ちている人もいて、約数全列挙でもスクリプト系言語で書いた人は約数の個数が多いケースでTLEになっていたようです。次からはせっかくのチャンスなので取りこぼしを少なくしたいです。

1533 -> 1633 (+100) 切りの良い上昇。

2011-04-10

UVa Huge Easy Contest Ⅱ

| 23:56

http://uva.onlinejudge.org/index2.php?option=com_onlinejudge&Itemid=13&page=show_contest_standings&contest=279&fullscreen=1

なかなか面白そうだと思ったので参加しました。

24時間で26問解くというコンテストでした。

20位にいるI.Tというのが自分です。

続きを読む

2011-04-08

TopCoder SRM 502 Div1

| 18:51

今日から大学だけど午後からだったので参加。

Easy

  • 開く。
  • 方針は割とすぐに浮かんだので、範囲が被っているものを取り除くようなコードを書く。
  • 最後のサンプルが合わない。
    • prefixとsufixを勘違いしていた。直してサブミット

213.14

Medium

  • 読む。
  • 幅優先探索的なことがしたかったけれど、サイズ的に無理そうなので考える。
  • 最初、ある時間に一番大きな点数がもらえる問題を貪欲に解くようにする。
  • サンプルが通らない。
  • 解かれていない問題のうち、一番多い得点がもらえるものを解く。
  • サンプルがあった。
  • それ以外に方針が思い浮かばないので提出。

321.36

Hardは読んだけれど全く分かりませんでした。

System Test

  • ox- greedyが通るわけはなかった。
  • easyが通ったので少し安心。

1238 -> 1336 (+98) 多少DIV2が遠のきました。

2011-04-03

The 11th Zhejiang University Programming Contest

| 23:14

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のコンテストに流れた人が多かったようですけどね!!