Hatena::Grouptopcoder

tanakhの日記 このページをアンテナに追加 RSSフィード

2010-08-15

SRM479

18:12 | SRM479 - tanakhの日記 を含むブックマーク はてなブックマーク - SRM479 - tanakhの日記 SRM479 - tanakhの日記 のブックマークコメント

最近負け続きだったので書く気力が出なくて放置していたが、

やっぱり書いたほうが復習になると思うので、再開。

http://www.topcoder.com/stat?c=coder_room_stats&cr=22627322&rd=14158&rm=305523

実に7回ぶりの500AC。良かった。毎回これぐらい出来ればいいんだけどなあ。

250 175.27 AC

飛行機の座席にコーヒーと紅茶を運ぶのにかかる時間を最小化しろ、という問題。最小化といっても、これ後ろから運ぶだけだよなあ、不安になりながらも適当に実装。意外と面倒。紅茶注文する人が47人までしかいないので、コーヒーもそれぐらいの時間で計算できるはずだけど、めんどくさすぎる。よく考えたら、44Mぐらいなめても間に合いそうだ。適当になめる実装にして終了。時間がかかりすぎた…。

500 221.98 AC

飛行機の路線と街があるので、目的の街に制限以内に到着できる経路のうちで、もっとも安全な経路の安全度を出力せよ。経路の安全度とは、乗り換えの待ち時間の最短である。

時間をある値以下にしながら、もうひとつのものを最適化…。こういうのどうやって解くんだったかな。ひとつの値の最適化なら簡単なのに。はっ…待ち時間の最短を固定すれば、あとはダイクストラするだけだ。それで答えを二分探索すればいい。珍しく解法が結構早く浮かんだ。あとは適当に実装するだけ、と思いきや、なぜかダイクストラの実装に恐ろしく時間がかかる。多少エッジの生成が面倒ではあったが、さすがにかかりすぎで、終了5分前に何とかデバッグ完了してサブミットできた。危なかった。

1000 Opened

思い出Open。

Challenge

終了間際に500をサブミットした人が居て、そのコードがどうもサンプルが通らないように見えたのだが、さすがにサブミットする以上サンプルぐらいは通していると思って詳しく読んでいたら、読んでいるうちに他の人に落とされた。もう少し大胆に行くべきだったか。

反省

250も500もコード書くのに時間がかかりすぎてだめだ。修行が足りない。Challengeももっと積極的に行かねばなあ。

トラックバック - http://topcoder.g.hatena.ne.jp/tanakh/20100815

2010-06-06

Google Code Jam 2010 Round 2

21:21 | Google Code Jam 2010 Round 2 - tanakhの日記 を含むブックマーク はてなブックマーク - Google Code Jam 2010 Round 2 - tanakhの日記 Google Code Jam 2010 Round 2 - tanakhの日記 のブックマークコメント

http://code.google.com/codejam/contest/dashboard?c=635102#s=a

A-small/large、B-small/large、C-small、D-small正解の50点で74位/3000人。

500位以上で通過。

前回あんなこと書いてましたが、haskell.orgが落ちていたので大事を取ってC++で。

単純に準備不足というのもある。次はどうしたものか。

A

21:21 |  A - tanakhの日記 を含むブックマーク はてなブックマーク -  A - tanakhの日記  A - tanakhの日記 のブックマークコメント

「ダイアモンド」が与えられるので、なるべく少ない数を追加してこれを「エレガントなダイアモンド」に変化させよ、という問題。「ダイアモンド」はひし形に配置された整数の列で、「エレガントなダイアモンド」は上下左右対称なダイアモンド。

妙にスコアが低いけど、そこまで簡単とは思えない。実際にはもちろん簡単なのだけど、実装が意外とバグり易いのではないか。解法としては、新しい中心をどこかに決めて、そこを中心とした上下左右対称になっているかを調べて、有効な中心の中でもっとも半径の小さそうなものを選べばよいのだが、添え字を間違えまくってものすごく時間を食ってしまった。結局30分ほどかけて完成したもののなぜか通らず。このままデバッグしていいものか迷うが、中断して次の問題へ。

C-small

21:21 |  C-small - tanakhの日記 を含むブックマーク はてなブックマーク -  C-small - tanakhの日記  C-small - tanakhの日記 のブックマークコメント

B-smallの点数が高かったのでC-smallを解くことに。

変形ライフゲームのようなルールがあって、すべてのセルが死滅するまでのターン数を求めよという問題。

Smallはサイズが100x100までだったので、愚直に実装してアクセプト。5分ほどで書けた。Aでどはまりしたが、これで少し調子が出てきた。

B-small

21:21 |  B-small - tanakhの日記 を含むブックマーク はてなブックマーク -  B-small - tanakhの日記  B-small - tanakhの日記 のブックマークコメント

D-smallとどちらにするか迷ったが、他の人たちのサブミット数を見てこちらに。

サッカーのトーナメントがあって、各試合に対してチケットの値段が設定されている。また、各チームに対して、そのチームの試合を何回まで見逃してもいいかが与えられる。これを満たすようにチケットを買うとき、必要な金額の最小を求めよ。ただしsmallはすべてのチケットの値段が1である。

smallの条件だと、なるべくトーナメントの上のほうのチケットを買うほうがいい。なので、上から再帰的にまだチケットを買う必要があるかを計算するだけ。というわけで適当にsmallを通す。

A

21:21 |  A - tanakhの日記 を含むブックマーク はてなブックマーク -  A - tanakhの日記  A - tanakhの日記 のブックマークコメント

Dの問題文を読んだけど理解できなかったのでひとまずAを通すことに。

対称かどうかの判定が間違っている。なぜか上下左右対称じゃなく点対称になっているか調べていた。修正してサブミット。

B-large

21:21 |  B-large - tanakhの日記 を含むブックマーク はてなブックマーク -  B-large - tanakhの日記  B-large - tanakhの日記 のブックマークコメント

再度Dの問題文を読んでみたがやっぱり理解できないのでB-largeをやることに。

smallの条件だとトーナメントの上のほうを常に買うのがいい。largeの条件だとどちらかわからない。上のを買った場合と買わなかった場合、二回再帰すれば答えは求まるが…。よく考えたら、二回再帰しても全く計算量のオーダは変わらないじゃないか。なんだなんだという感じで適当に修正してサブミット。一応smallの正解と照合するというチェックはしておく。

D-small

21:21 |  D-small - tanakhの日記 を含むブックマーク はてなブックマーク -  D-small - tanakhの日記  D-small - tanakhの日記 のブックマークコメント

残り40分ほど、C-largeとD-smallどちらをやるか。C-largeの得点の高さにひるんでD-smallを今度こそ頑張ることにする。

ある点があって、それとは別の点の集合から、それぞれその点を通る円を書く。すべての円の共通部分の面積を求めよ。ただしsmallは点の数2つまで。

読んでみると何のことはない、smallは2円の共通部分の面積を求めるだけの問題だ。ライブラリはないがこれぐらいは何とかなるだろうということで解き始める。二円の中心を結ぶ直線と二円の交点と円の中心を結ぶ直線からなる三角形を考えて、その角を中心角とする扇形を計算すればいい。余弦定理でその角を求め、三角形の面積の公式で面積を求める。特に問題なくアクセプトした。

反省・感想

21:21 |  反省・感想 - tanakhの日記 を含むブックマーク はてなブックマーク -  反省・感想 - tanakhの日記  反省・感想 - tanakhの日記 のブックマークコメント

Aが通らなかったときは今回はもう駄目かと思ったが、徐々に調子が上がってきた感じだった。最初駄目でもあきらめてはいけないということだ。C-largeは点数にひるんだが、そこまで難しい感じでもなさそうだ。今回は途中経過見ていけそうな感じだったから手をつけなかったが、次は500人→25人と一気に狭まるので、多少の冒険もしないと万に一つの可能性も生まれないだろう。次がOnlineの最終ラウンドなので、勝っても負けても悔いが残らないようにしたい。

トラックバック - http://topcoder.g.hatena.ne.jp/tanakh/20100606

2010-05-29

University of Aizu Programming Contest 2010 (UAPC2010)

05:15 | University of Aizu Programming Contest 2010 (UAPC2010) - tanakhの日記 を含むブックマーク はてなブックマーク - University of Aizu Programming Contest 2010 (UAPC2010) - tanakhの日記 University of Aizu Programming Contest 2010 (UAPC2010) - tanakhの日記 のブックマークコメント

http://rose.u-aizu.ac.jp/onlinejudge/cvolume.jsp?contestID=UAPC2010

5時間11問。10問正解で4位でした。問題文日本語+問題易しめという好条件ではありますが。

A

こういうのはAが一番簡単と相場が決まっているのでAから。

数字を前からなめるだけ…と思いきや途中でお腹が痛くなる。

#include <iostream>
#include <vector>
using namespace std;

int main()
{
  for (int n; cin>>n, !(n==0); ){
    vector<int> v(n);
    for (int i=0; i<n; i++) cin>>v[i];

    bool fst=true;
    for (int i=0; i<n; i++){
      int e=i;
      for (int j=i+1; j<n; j++){
        if (v[j-1]+1==v[j]) e=j;
        else break;
      }
      if (fst) fst=false;
      else cout<<" ";
      if (i==e) cout<<v[i];
      else cout<<v[i]<<"-"<<v[e];
      i=e;
    }
    cout<<endl;
  }
  return 0;
}

B

ええと、どうやるんだ?サイズが微妙に小さいが全探索が通るサイズではない。いやいや、橋の容量が小さいところからとるのが最適に決まっているじゃないか。ソートしてなめるだけ。n*2^nなDPでも通ったりするのだろうか?

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
  for (int n; cin>>n, !(n==0); ){
    vector<pair<int, int> > v;
    for (int i=0; i<n; i++){
      int a, b; cin>>a>>b;
      v.push_back(make_pair(b, a));
    }
    sort(v.begin(), v.end());
    int acc=0;
    for (int i=0; i<n; i++){
      acc+=v[i].second;
      if (acc>v[i].first){
        cout<<"No"<<endl;
        goto _exit;
      }
    }
    cout<<"Yes"<<endl;
  _exit:;
  }
  return 0;
}

C

レールガンってそういう仕組だったのかー。角度が外れてたら二度と当たらないということに気づかなかったので、愚直に実装。反射の式がとても怪しくて全く自信がなかったが一発アクセプト。多少間違っていたとしても通りそうですね。

#include <iostream>
#include <iomanip>
#include <vector>
#include <complex>
using namespace std;

typedef complex<double> pt;

pair<double,double> cross_circle_and_line(pt a, pt u ,pt c ,double r)
{
  double b=real(u*conj(a-c));
  double d=b*b-norm(u)*(norm(a-c)-r*r);
  d=max(d, 0.0);
  return make_pair((-b+sqrt(d))/norm(u),
		   (-b-sqrt(d))/norm(u));
}

pt tani(const pt &p)
{
  return p/abs(p);
}

int main()
{
  cout<<setiosflags(ios::fixed)<<setprecision(10);
  for (double d; cin>>d, !(d==0); ){
    double px, py; cin>>px>>py;
    pt p(px, py);
    double vx, vy; cin>>vx>>vy;
    pt v(vx, vy);

    double total_dist=0;
    for (;;){
      pt vv=-p/v;
      if (abs(vv.imag())<1e-9 && vv.real()>0){
	total_dist+=abs(p);
	break;
      }
      pair<double, double> ss=cross_circle_and_line(p, v, pt(0, 0), 1);
      //cout<<"+++ "<<ss.first<<" "<<ss.second<<endl;
      double s=max(ss.first, ss.second);
      total_dist+=abs(v*s);
      pt np=p+s*v;
      pt tt=v/tani(np);
      pt nv=v-tani(np)*tt.real()*2.0;
      p=np;
      v=nv;
      //cout<<total_dist<<": "<<s<<", "<<p<<", "<<v<<", "<<abs(v)<<endl;
      if (total_dist>d) break;
    }
    //cout<<"==="<<endl;
    if (total_dist>d)
      cout<<"impossible"<<endl;
    else
      cout<<total_dist<<endl;
  }
  return 0;
}

D

シミュレーションするだけで、仕様も割とシンプルなのですぐにできたが、配列の添字を一箇所間違えて一回REをもらう。

#include <iostream>
#include <vector>
#include <map>
#include <string>
using namespace std;

struct link_dat{
  link_dat(){}
  link_dat(int l, int u, int r, int d, const string &p)
    :l(l), u(u), r(r), d(d), p(p) {}

  bool in(int x, int y){
    return (x>=l && x<=r && y>=u && y<=d);
  }

  int l, u, r, d;
  string p;
};

int main()
{
  for (int n; cin>>n, !(n==0); ){
    int w, h; cin>>w>>h;
    map<string, vector<link_dat> > page;
    string home;
    for (int i=0; i<n; i++){
      string name; cin>>name;
      int m; cin>>m;
      if (i==0) home=name;
      vector<link_dat> links;
      for (int j=0; j<m; j++){
	int l, u, r, d; cin>>l>>u>>r>>d;
	string p; cin>>p;
	links.push_back(link_dat(l, u, r, d, p));
      }
      page[name]=links;
    }
    vector<string> hist;
    hist.push_back(home);
    int cursor=0;

    int m; cin>>m;
    for (int i=0; i<m; i++){
      string cmd; cin>>cmd;
      if (cmd=="show"){
	cout<<hist[cursor]<<endl;
      }
      else if (cmd=="forward"){
	cursor++;
	cursor=min(cursor, (int)(hist.size()-1));
      }
      else if (cmd=="back"){
	cursor--;
	cursor=max(0, cursor);
      }
      else if (cmd=="click"){
	int x, y; cin>>x>>y;
	vector<link_dat> &links=page[hist[cursor]];
	for (int i=0; i<links.size(); i++){
	  if (links[i].in(x, y)){
	    hist.resize(cursor+1);
	    hist.push_back(links[i].p);
	    cursor++;
	    break;
	  }
	}
      }
    }
  }
  return 0;
}

E

最小全域木の個数?わからん…。

J

Eが分からないので解いてる人が多かったJに移る。素因数分解するだけのように見える。a<=bなものというのでちょっとギョッとするが、a==bなのは両方Lの時だけだから、適当に計算して、後で補正できるだろう。適当に計算して提出。

#include <iostream>
#include <vector>
using namespace std;

int main()
{
  int limit=1000000;
  vector<int> primes;
  vector<bool> flg(limit, true);
  for (int i=2; i<limit; i++){
    if (flg[i]){
      primes.push_back(i);
      for (int j=i+i; j<limit; j+=i)
	flg[j]=false;
    }
  }

  for (long long l; cin>>l, !(l==0); ){
    vector<pair<long long,int> > ps;
    long long n=l;
    for (int i=0; i<primes.size(); i++){
      long long p=primes[i];
      if (p*p>n) break;
      int cnt=0;
      while(n%p==0){
	n/=p;
	cnt++;
      }
      if (cnt>0){
	ps.push_back(make_pair(p, cnt));
      }
    }
    if (n>1) ps.push_back(make_pair(n, 1));

    long long ans=1;
    for (int i=0; i<ps.size(); i++){
      ans*=(ps[i].second+1)*2-1;
    }
    cout<<(ans+1)/2<<endl;
  }
  return 0;
}

E

J解きながらEを考えていたところによると、辺の数が2個のみというのは制約が強すぎるので、簡単な解き方があるだろうということ。サンプルを紙に書いてみると、ループになっていた。そうか。次数2だとループにしかならない。ループの中で最小要素の個数を数えて掛け合わせるだけだ。そうと分かれば簡単に実装。サブミット。

#include <iostream>
#include <vector>
#include <cstdio>
using namespace std;

int main()
{
  for (int n; scanf("%d", &n), !(n==0); ){
    vector<pair<pair<int,int>, pair<int,int> > > g;
    vector<bool> f(n, false);
    for (int i=0; i<n; i++){
      int a, b, c, d;
      scanf("%d%d%d%d", &a,&b,&c,&d);
      g.push_back(make_pair(make_pair(a, b), make_pair(c, d)));
    }
    long long ans=1;
    for (int i=0; i<n; i++){
      if (f[i]) continue;
      f[i]=true;
      int maxp=g[i].first.second;
      int maxc=1;
      for (int b=i, c=g[i].first.first; ; ){
	if (f[c]) break;
	f[c]=true;
	int n=0;
	int p=0;
	if (g[c].first.first!=b){
	  n=g[c].first.first;
	  p=g[c].first.second;
	}
	else{
	  n=g[c].second.first;
	  p=g[c].second.second;
	}
	if (p>maxp) maxp=p, maxc=1;
	else if (p==maxp) maxc++;

	b=c;
	c=n;
      }
      ans=(ans*maxc)%10007;
    }
    cout<<ans<<endl;
  }
  return 0;
}

F

普通にDPするとO(n^2)掛かりそう。ところでなぜ狼なんだろう、という疑問をこらえて、もっと重要な違和感の意味を考える。なぜ精度要求が10^-2までなんだ?そうか、これは一回成功するごとに指数的に確率が下がっていくから、精度がこの程度でいいなら、n*10程度のDPでも十分だ。誤差も指数的に減るので、蓄積はない。というわけで適当に書いてアクセプト。

#include <iostream>
#include <iomanip>
#include <vector>
#include <cmath>
using namespace std;

int main()
{
  int limit=100001;
  vector<vector<double> > tbl(10, vector<double>(limit, 0));

  for (int i=1; i<limit; i++){
    for (int l=0; l<10; l++){
      double p=pow(0.5, l);
      tbl[l][i]=(1-p)*tbl[0][i-1];
      if (l!=9) tbl[l][i]+=p*(1+tbl[l+1][i-1]);
    }
  }

  cout<<setiosflags(ios::fixed)<<setprecision(10);
  for (int n; cin>>n, !(n==0); ){
    cout<<tbl[0][n]<<endl;
  }
  return 0;
}

G

問題文がきな臭い…。これは問題サイズが小さいから単なるめんどいダイクストラのようだ。ノードは位置とサイコロの状態の組みで、サイコロの状態は三面の目のタプルで表した。意外とすんなりアクセプト。

#include <iostream>
#include <vector>
#include <map>
#include <set>
using namespace std;

struct dice{
  dice(int u, int s, int e): up(u), south(s), east(e) {}

  dice rotate(int dir){
    if (dir==0)
      return dice(south, 7-up, east);
    if (dir==1)
      return dice(7-east, south, up);
    if (dir==2)
      return dice(7-south, up, east);
    if (dir==3)
      return dice(east, south, 7-up);
  }

  bool operator==(const dice &r) const{
    return up==r.up && south==r.south && east==r.east;
  }
  bool operator<(const dice &r) const{
    if (up!=r.up) return up<r.up;
    if (south!=r.south) return south<r.south;
    return east<r.east;
  }

  int up;
  int south;
  int east;
};

int main()
{
  for (int h, w; cin>>h>>w, !(h==0&&w==0); ){
    vector<vector<int> > bd(h, vector<int>(w, 0));
    for (int y=0; y<h; y++){
      for (int x=0; x<w; x++){
	cin>>bd[y][x];
      }
    }
    int sy, sx; cin>>sy>>sx;
    int gy, gx; cin>>gy>>gx;

    multimap<int, pair<dice, pair<int, int> > > mm;
    set<pair<dice, pair<int, int> > > close;
    mm.insert(make_pair(0, make_pair(dice(1, 2, 3), make_pair(sx, sy))));
    while (!mm.empty()){
      int dist=mm.begin()->first;
      dice d=mm.begin()->second.first;
      int cx=mm.begin()->second.second.first;
      int cy=mm.begin()->second.second.second;
      mm.erase(mm.begin());

      if (cx==gx && cy==gy){
	cout<<dist<<endl;
	break;
      }
      //cout<<cx<<", "<<cy<<endl;

      if (close.count(make_pair(d, make_pair(cx, cy))))
	continue;
      close.insert(make_pair(d, make_pair(cx, cy)));

      static const int vect[8]={
	0,-1,1,0,0,1,-1,0
      };
      for (int v=0; v<4; v++){
	int nx=cx+vect[v*2+0];
	int ny=cy+vect[v*2+1];
	if (nx>=0 && ny>=0 && nx<w && ny<h){
	  dice nd=d.rotate(v);
	  int ndist=dist+bd[ny][nx]*(7-nd.up);
	  if (!close.count(make_pair(nd, make_pair(nx, ny))))
	    mm.insert(make_pair(ndist, make_pair(nd, make_pair(nx, ny))));
	}
      }
    }
  }
  return 0;
}

H

特定の頂点を通る最短路の個数…?うーむ、どうやるんだろう。ウォーシャルフロイド回しながら個数も計算できるのだろうか。適当に実装してみる。全然だめだ。最短路の長さ計算してから個数を計算できないか?よく考えると、任意の最短路からなるグラフはDAGだ。ループはない。よし、適当にDPで求まる。特定の頂点を通る最短路の個数は、始点→その点の最短路の個数*その点→終点の最短路の個数ぽい。これを全体の個数で割れば良さそう。実装する。WA。だめぽ。

I

Hが全然通らないので、Iに移動。問題サイズが不自然に小さい。これは探索か。盤面の情報が最大で25ビットしかないので、これをIntで持ちつつ2^25ノード25^4*2^25辺のグラフでダイクストラか?まあ書いてみるか。書き書き。幅優先で十分じゃないか。書き直し。サブミット。TLE。まあそんなもんか。TLEが8秒なのに対して10秒で切られているので、小手先の高速化でどうにかなるのか分からない。ピコーン。そうだ。同じ場所は2回以上反転する領域の左上とはならない。という事は、左上から見ていって、最初に現れた1を左上とする領域で反転すれば大幅に枝刈りされる+大幅に探索が高速化される。サブミット。0.4秒ぐらいで通った。

#include <iostream>
#include <vector>
#include <map>
#include <queue>
using namespace std;

int upb(int n)
{
  int ret=0;
  while(n>0) ret++, n/=2;
  return ret;
}

int main()
{
  for (int n; cin>>n, !(n==0); ){

    vector<int> pat;
    for (int i=0; i<n; i++){
      for (int j=0; j<n; j++){
	for (int k=i; k<n; k++){
	  for (int l=j; l<n; l++){
	    vector<vector<int> > tmp(n, vector<int>(n, 0));
	    for (int a=i; a<=k; a++){
	      for (int b=j; b<=l; b++){
		tmp[a][b]=1;
	      }
	    }
	    int bd=0;
	    for (int a=0; a<n; a++){
	      for (int b=0; b<n; b++){
		bd=(bd<<1)|tmp[a][b];
	      }
	    }
	    pat.push_back(bd);
	  }
	}
      }
    }

    vector<vector<int> > pats(n*n+1);
    for (int i=0; i<pat.size(); i++){
      pats[upb(pat[i])].push_back(pat[i]);
    }

    int bd=0;
    for (int i=0; i<n; i++){
      for (int j=0; j<n; j++){
	int t; cin>>t;
	bd=(bd<<1)|t;
      }
    }

    queue<pair<int, int> > mm;
    vector<bool> close(1<<(n*n), false);
    mm.push(make_pair(0, bd));
    close[bd]=true;
    while(!mm.empty()){
      int dep=mm.front().first;
      int cbd=mm.front().second;
      mm.pop();
      //cout<<cbd<<endl;
      int ub=upb(cbd);
      for (int i=0; i<pats[ub].size(); i++){
	int nbd=cbd^pats[ub][i];
	if (nbd==0){
	  for (int i=0; i<=dep; i++)
	    cout<<"myon";
	  cout<<endl;
	  goto _exit;
	}
	//cout<<"*** "<<nbd<<endl;
	if (close[nbd]) continue;
	close[nbd]=true;
	mm.push(make_pair(dep+1, nbd));
      }
    }
  _exit:;
  }
  return 0;
}

H

残り一時間ほど。これを通してすっきり終わるか。しかし、なぜ通らないのか全く分からない。枝の重みが距離であるという記述がないので、最短経路の定義からして怪しくなってくる。なんだか枝の重みが大きいほど通りやすいから短いと言えるのか?ならば、重みの和を最大にするのか。しかし、どうやる?うーむ。わからない。そんな埼玉コンテスト的問題の解釈違いを疑いつつ、入力の仕様読み違いがないことを確認するためにassert入れてサブミットしまくる。どうやら思い違いはなかったようだ。そうこうしているうちに、同じ頂点への最短路の扱いがおかしいことに気づく。なんのことはない。単なるバグであった。

>

K

思い出サブミット!

感想

積み残しがなかったのですっきり満足。いつもこれぐらいできればいいんだがなあ。

トラックバック - http://topcoder.g.hatena.ne.jp/tanakh/20100529

2010-05-10

Google Code Jam 2010 Qual

09:58 | Google Code Jam 2010 Qual - tanakhの日記 を含むブックマーク はてなブックマーク - Google Code Jam 2010 Qual - tanakhの日記 Google Code Jam 2010 Qual - tanakhの日記 のブックマークコメント

Haskellを全世界に広めるというサイモンとの約束を果たすために私は、Haskellのみを用いてトップ25に残らねばならないッ!

とりあえず...

Qualification Roundです。時間が24時間もあるので、どうにでもなります。一応全部通しました。今後のためのテンプレート作成などもぼちぼち考える。

サブミットしたソースなどは下記リンクより。

http://code.google.com/codejam/contest/scoreboard?c=433101#sp=1001

A

一回の操作で、1*0 というパターンが 0*1 に変わる。これは整数のインクリメントに他ならない。ゆえに、K`mod`(2^N) == 2^N-1 かどうかを調べればよい。

import Control.Monad
import Control.Applicative
import Text.Printf

gcjMain f m = do
  n <- readLn
  dat <- replicateM n m
  forM_ (zip [1..n] dat) $ \(i, d) -> do
    printf "Case #%d: %s\n" i (f d)

main = gcjMain solve $ map read . words <$> getLine

solve [n, k]
  | k `mod` 2^n == 2^n-1 = "ON"
  | otherwise = "OFF"

B

なんだか難解な問題文が書いてあるが、要するに、与えられた整数列に同じ数を足して、gcdが最も大きくなるようにすればいいらしい。ただし、入力は50桁ぐらいある。

同じ数を足した後も差は変わらなくて、差もgcdの倍数になっているはずなので、要するに差のgcdをとってやれば良い。

Haskellには使い易い多倍長整数とgcdがあるので、とても楽。

import Control.Monad
import Control.Applicative
import Text.Printf

gcjMain f m = do
  n <- readLn
  dat <- replicateM n m
  forM_ (zip [1..n] dat) $ \(i, d) -> do
    printf "Case #%d: %s\n" i (f d)

main = gcjMain solve $ tail . map read . words <$> getLine

solve (x:xs) = show ((x+g-1)`div`g*g-x :: Integer) where
  g = abs $ foldl1 gcd $ filter (/=0) $ map (x-) xs

C

入力がやや大きいので、ちょっと怯む。全部回すのは流石にまずそうだ(実際のところ、普通に回せてしまうようだが…)。仮にできたとしても、Haskellでリストを用いた実装は不可能だし、O(1)でアクセスできる配列を用いるのも面倒くさい(これは練習しておかねばならないが)。

ループを検出して、ループを一気に進めてやれば良いかなと思って実装する。実装が意外と面倒くさい。Haskellでリストを書き換えながらループをするとか、Haskellらしからぬ気もする。というふうに書いているところで、もっと綺麗でかつ速い方法を思いついた。

n回先にどこに行くのかというのは、n/2回でどこに行くのかを計算すればそこから求まるので、結局ベクトルに対して高速な累乗のようなことをしてやれば一発で求まるのである。計算量はO(NlogR)。下記コードではリストを用いているのでO(N^2logR)になっている。

import Control.Monad
import Control.Applicative
import Text.Printf

gcjMain f m = do
  n <- readLn
  dat <- replicateM n m
  forM_ (zip [1..n] dat) $ \(i, d) -> do
    printf "Case #%d: %s\n" i (f d)

main = gcjMain solve $ do
  [r, k, n] <- map read . words <$> getLine
  gs <- map read . words <$> getLine
  return (r :: Int, k, gs)

solve (r, k, gs) = show $ snd . head $ mult incs r where
  n = length gs
    
  mult v n
    | n == 1 = v
    | n `mod` 2 == 0 = vadd v2 v2
    | otherwise = vadd (vadd v2 v2) v
      where
        v2 = mult v (n`div`2)
        
  vadd v1 v2 =
    [ (diff+ndiff, inc+ninc)
    | (i, (diff, inc)) <- zip [0..] v1
    , let ni = (i + diff) `mod` n , let (ndiff, ninc) = v2 !! ni ]
    
  incs = [ takek $ take n (drop i (gs++gs)) | i <- [0..n - 1]]
  takek gs = last $ takeWhile ((<=k).snd) $ scanl (\(c, a) e -> (c+1, a+e)) (0, 0) gs

TigerTiger2011/07/22 18:56Never would have thunk I would find this so idnipsensable.

rzutdarzutda2011/07/22 22:277qr6HB <a href="http://nkwdcmmrjgjo.com/">nkwdcmmrjgjo</a>

gmwkdoytpflgmwkdoytpfl2011/07/23 21:54sPXoEP , [url=http://ogopvlokvewo.com/]ogopvlokvewo[/url], [link=http://xwvscoubkmxr.com/]xwvscoubkmxr[/link], http://cnqtnbcjusgw.com/

kgdzzukgdzzu2011/07/25 20:40bTNxd1 <a href="http://atdblfahscal.com/">atdblfahscal</a>

dkyomfdaendkyomfdaen2011/07/26 00:49XyOs8q , [url=http://hoyqrsyjstup.com/]hoyqrsyjstup[/url], [link=http://jnkvmrbexcza.com/]jnkvmrbexcza[/link], http://pfqbfhemeijo.com/

トラックバック - http://topcoder.g.hatena.ne.jp/tanakh/20100510

2010-05-04

SRM469

00:57 | SRM469 - tanakhの日記 を含むブックマーク はてなブックマーク - SRM469 - tanakhの日記 SRM469 - tanakhの日記 のブックマークコメント

2114 -> 2112 レートが動かない…

250 199.88 AC

座席がいくつか埋まってる映画館で二人隣りあって座れる座り方の数。サイズは10^9x10^9までだけど、埋まってるのは47個まで。

やるだけかなあと思ったら、サイズがでかい。そんなでかい映画館ないやろ。埋まってるところが少ないので、その行だけ調べて他は掛け算すれば良いか。サブミットしてからテストするPetr方式してたら、最後に掛け算する時にlong longにするのを忘れてるのを発見。再サブミット。おわた…。

500 202.98 WA

映画を見てるのだけど、眠くなってくる。映画の怖いシーンが来ると、ちょっと眠気が覚める。なるべくたくさん映画を見れるように、うまいこと映画を観る順番を決めよう。最適解が複数ある場合は辞書順最小。映画は20本まで。

20てことは、2^20だろうなあ。でもすぐ思いつく探索は、状態として、見た映画のパタンと現在の睡眠値で、2^20*(45*20)ほど必要になる。これは無理っぽい。そうこうしているうちに20分経過。逆に考えて、ある映画の集合を完全に視聴するのに必要な、最小の睡眠値をDPすることにすれば、それが初期値以下のパターンの中で一番大きいものを選べば良いということになる。なんとなく行けそうなので、適当に実装。適当にサブミット。なんとなく怪しい…。

1000 Opened

時間が少なかったので読まずに見直しへ。

Challenge Phase

250の再送が響いて相当ひどい順位。500も殆どの人がサブミットしていて、かなり駄目な感じ。なんとかせねばと思って見ていると、250で10^9回ループ回してラインごとに計算している人がいる。10億がすんなり通るほど、SRMは甘くないぜ…というわけで、撃墜成功。250、オーバーフローしている人がいると思ったのだけど、誰もおらず。500見てるとグリーディーな人が何人かいて、明らかに落とせそうだったのだけど、確実に落とせるケースを作れず、断念。

System Test

500が落ちた。DPの途中では、個数最大じゃなくて、必要初期睡眠値最小でやっているので、途中の辞書順が怪しいのだった。すっかり気づいていなかった。気づいていても時間的に修正は間に合わなかったかもしれない。同じ部屋の人も500は相当落ちていた。かなりの謎。2人しか通っていなかった。

500はビットパターンが同じだと同じ睡眠値になるから、とても自明な方法で大丈夫なのですね…。なんで気付かなかった。

反省

Petr方式はやめようと思った。特に集中力が足りてないときは。

辞書順最小は罠。出来ていそうでも出来ていないこともあるみたいだから、じっくり考える事。

rng_58rng_582010/05/05 15:42Petrは、手元でプラグインでテスト -> submit -> Arena上でテスト です

tanakhtanakh2010/05/06 00:48なるほど。私はCodeProcessorそのまま使ってるので、テストケース追加とかはArenaでしかやってなかったのがいけなかったです…。

トラックバック - http://topcoder.g.hatena.ne.jp/tanakh/20100504