2010-04-11

Codeforces Beta Round #9

Codeforces 凡ミス

凡ミスタグを付けなくてすむその日まで頑張る.

A Die Roll

(^p^)

B Running Student

sqrtの中身にintの範囲を超えるものを渡してて,それに気付かなかった(^p^)前にもsqrtの中身が負でバグってたことがあった。はぁ…

引数がおかしくなるケースがあるか考えよう

あとintの範囲は2^31^1 == 2147483647 だいたい 2 * 10^9.今回は(10^5)^2でint超えてた

C Hexadecimal's Numbers

10進数で0と1だけで構成できる,ある数を超えない数はいくつ？

1から*10 + 1、*10 を再帰的に数えた.

D How many trees?

ノード数N,高さがH以上の2分木は何通り構成できる？

木の性質かなぁ…ググル
大した情報ないので考える.
あるノードの左,右につけるものを考えるとき,自分より大きい数字がいくつ,小さい数字がいくつって情報だけでいいよな
じゃあこれに今の高さの情報を付け加えて再帰かな
高さがH以上になるには,あるノードの左の木が高さH以上じゃなくても右の木がH以上ならいいから…
返り値に最大の高さと構成数が必要？pair？？
って考えててこんがらかって終了
無条件の構成方法から,高さがH未満の構成方法を引くって方針に切り替えたらすんなり書けた

#include <iostream>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <map>
#include <queue>
#include <algorithm>
#include <complex>
#include <set>
#include <vector>
#include <bitset>

#define REP(i,N)for(int i=0;i<(int)N;i++)
#define MP(a,b) make_pair(a,b)
using namespace std;

int nextInt(){
  int ret=0,sign=1;
  char c=' ';
  while (!isdigit(c=getchar())){
    if (c==EOF) return -1;
    if (c=='-') sign=-1;
  }
  do{
    ret=ret*10+(c-'0');
  }while (isdigit(c=getchar()));
  return ret*sign;
}
void printlineInt(int num){
  char str[101];
  if (num<0) num=-num,putchar('-');
  else if (num==0) {puts("0");return;}
  str[100]='\0';
  int i=99;
  for (;num;i--){
    str[i]=num%10+'0';
    num/=10;
  }
  puts(&str[i+1]);
  return;
}
//template end
int N,H;
long long dp[36][36][36];
long long dp2[36][36][36]; 

long long rec(int l,int u,int h){
  if (dp[l][u][h] != -1LL) return dp[l][u][h];
  //cout << h << " " << H << endl;
  if (h >= H) return dp[l][u][h] = 0;
  if (l == 0 && u == 0){
    return dp[l][u][h] = 1LL;
  }
  long long r1=0,r2=0;
  REP(i,l){
    r1 += rec(i,l-i-1,h+1);
  }
  if (!l) r1 = 1;
  REP(i,u){
    r2 += rec(i,u-i-1,h+1);
  }
  if (!u) r2 = 1;
  //cout << l << " " << u << " " << h << " " << r1 * r2 << endl;
  return dp[l][u][h] = r1 * r2;
}
long long rec2(int l,int u,int h){
  if (dp2[l][u][h] != -1LL) return dp2[l][u][h];
  if (l == 0 && u == 0){
    return dp2[l][u][h] = 1LL;
  }
  long long r1=0,r2=0;
  REP(i,l){
    r1 += rec2(i,l-i-1,h+1);
  }
  if (!l) r1 = 1;
  REP(i,u){
    r2 += rec2(i,u-i-1,h+1);
  }
  if (!u) r2 = 1;
  //cout << l << " " << u << " " << h << " " << r1 * r2 << endl;
  return dp2[l][u][h] = r1 * r2;
}

int main(){
  N=nextInt(),H=nextInt();
  REP(i,36) REP(j,36) REP(k,36) dp[i][j][k] = -1LL;
  REP(i,36) REP(j,36) REP(k,36) dp2[i][j][k] = -1LL;
  long long ans=0;
  REP(i,N){
    ans += rec2(i,N-i-1,1) - rec(i,N-i-1,1);
  }
  cout << ans << endl;
}

(^p^)

2010-04-09

Codeforces Beta Round #8

Codeforces 凡ミス

Codeforces初参戦．WARush!!

A Train and Peter

簡単な問題なんだけど，最後まで自分の間違いに気付かなかった．終了後に手元でサンプルケースを作ってみたら一瞬で間違いがわかった…

教訓：テストケースを作ってみよう．

B Obsession with Robots

UDRLで与えられる道筋がショーテストパスかどうかを判定する問題．一度歩いた所をもう一度歩かなければいいと思っていたけど，蛇行運転もショーテストじゃないね．

123456789の順に歩くとき，同じ道は通ってないけどショーテストではない．

..67.
12589
.34..

これに気付かずWA．

C Looking for Order

終了後にダイクストラで解いた．breakを入れるかどうかでTLEがACになる．ていうかなんでここでbreakしていいのかよく分からない…

#include <iostream>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <map>
#include <queue>
#include <algorithm>
#include <complex>
#include <set>
#include <vector>
#include <bitset>

#define REP(i,N)for(int i=0;i<(int)N;i++)
#define MP(a,b) make_pair(a,b)
using namespace std;

int bx,by;
int N;
int x[25],y[25];
int dp[1 << 24] = {};
int path[1 << 24] = {};
int dist[25][25];
struct State{
  int state;
  int cost;
  bool operator<(const State& s)const{
    return cost > s.cost;
  }
};

int main(){
  while (~scanf("%d %d",&x[0],&y[0])){
    N=nextInt();
    REP(i,N)
      x[i+1] = nextInt(),y[i+1] = nextInt();
    REP(i,1<<N)
      dp[i] = 1 << 25;
    REP(i,N+1){
      REP(j,N+1){
        dist[i][j] = (x[i]-x[j]) * (x[i]-x[j]) +
          (y[i] - y[j]) * (y[i] - y[j]);
      }
    }
    priority_queue<State> up;
    up.push((State){0,0});
    while (!up.empty()){
      int state = up.top().state;
      int cost = up.top().cost;
      up.pop();
      //cout << bitset<10>(state) << " " << cost << endl;
      if (state == (1 << N) -1) {
        printlineInt(cost);
        int p = state;
        int s = path[state];

        for (;; s=path[s]){
          printf("0 ");
          //cout << bitset<10>(s) << " " << bitset<10>(p) << endl;
          REP(i,N){
            if (((s & (1 << i)) ^ (p & (1 << i)))){
              printf("%d ",i+1);
            }
          }
          p = s;
          if (!s) break;
        }
        printf("0 \n");
        break;
      }
      if (dp[state] < cost) continue;
      REP(i,N){
        if (state & (1 << i)) continue;
        
        int nstate = state | (1 << i);
        int ncost = cost + (dist[0][i+1] << 1);
        if (dp[nstate] > ncost){
          dp[nstate] = ncost;
          path[nstate] = state;
          up.push((State){nstate,ncost});
        }
        
        for (int j=i+1;j<N;j++){
          if (state & (1 << j)) continue;
          int nstate = state | (1 << i) | (1 << j);
          int ncost = cost + dist[0][i+1] + dist[0][j+1] + dist[i+1][j+1];
          if (dp[nstate] > ncost){
            dp[nstate] = ncost;
            path[nstate] = state;
            up.push((State){nstate,ncost});
          }
        }
        break; // このbreakをとるとTLE
      }
    }
  }
}

だれか説明してくだしあ．

結果

1490のdiv2からスタート(´・ω・｀)．その代わり次のラウンドはdiv2onlyみたいなので出れるみたい．その次div1onlyかもしれないからぜひ上がりたい．
codeforces用のスクリプト書こうかなぁ．

2010-04-08

Emacs Lisp for PKU Judge Online and others

Emacs Lisp PKU

id:halwhiteさんがpkuのスクリプトを公開していたので私も公開．poj-modeっていうのは知らなかった…

http://code.google.com/p/icpc-online-judge-scripts/source/browse/trunk/icpc-online-judge.el#

このLispは外部スクリプトをプロセスを生成して実行します．それにより以下の機能を提供します．

機能

PKUなどのオンラインジャッジサイトへの自動サブミット
上記の結果はポップアップする．
ファイルを開いたときにテンプレートファイルの自動挿入
ファイルを開いたときに自動的にサンプル入出力を作成する
サンプルテスト用コンパイルコマンドの補助(C-c C-cなどに割り当てると便利)

使い方

まず，適当なディレクトリに入れてload-fileしてください．

例：~/site-lisp/icpc-online-judge.elに保存した場合，
.emacsに次のように記述

(load-file "~/site-lisp/icpc-online-judge.el")

(この際，find-file-hookにいくつかの関数をhookします)

次に，icpc-online-judge.elを開いて最初の行，icpc-judge-alistを編集します．
icpc-judge-alistはパラメータリストのリストです．パラメータリストは次の構成になっています．

スクリプトを適用するファイルの正規表現
1にマッチしたとき挿入するテンプレートファイル
1のファイル名部分から，問題番号を抜き出す正規表現
適用するスクリプト
入出力ファイルを作成するときにスクリプトに渡す引数
サブミットする時にスクリプトに渡す引数
1をコンパイルするときのコマンド

パラメータ中では%に続けて特殊文字列が使えます．特殊文字列は次のようになっています．

%F 絶対パス
%f ディレクトリを含まないファイル名
%d パスのディレクトリ部分
%n 拡張子を含まないファイル名
%e 拡張子
%p 問題番号

例えば，pku1000.cppというファイルを1000.in,1000.outでテストする場合次のように記述します．

g++ %f && ./a.out < %p.in | diff %p.out -

これは次のように置き換えられます．

g++ pku1000.cpp && ./a.out < 1000.in | diff 1000.out -

関数は次の通りです．

icpc-submit-current-buffer 現在開いているファイルをサブミットする
icpc-submit-current-buffer-with-args サブミットするとき，引数を指定する
icpc-compile-and-test パラメータ7によりコンパイルする
icpc-mode-toggle 自動テンプレート挿入などの有効/無効を切り替える．

スクリプト

このlispは外部スクリプトを実行するため，スクリプトが別に必要になります．私の作ったpkuのperl スクリプトはこちらです．
http://code.google.com/p/icpc-online-judge-scripts/source/browse/trunk/pku.pl
このスクリプトの$idと$passを自分のものに書き換えて下さい．
あまりperl書かないから汚いです．
また，入出力の作成が全然甘いのですが，spojのスクリプトも作りました．
http://code.google.com/p/icpc-online-judge-scripts/source/browse/trunk/spoj.pl
本当は流行りのcodeforceで作ろうと思ったけど，googleのopenidが上手くできない…

補足

このスクリプトは引数が次のようになっている

*サブミット
# ./pku.pl submit 問題番号 送信するファイル
*入出力作成
# ./pku.pl sample 問題番号 入力保存先 出力保存先

とりあえず使ってみるなら

icpc-judge-onlineとpku.plを~/site-lisp/に保存，テンプレートファイルを~/icpc/icpc_template.cppに保存，pkuのファイルを~/icpc/pku/1000.cppに保存してみれば動くはずです．

(スクリプト作成者向け)スクリプト作成方法

このlispとスクリプトはexit codeと出力で会話をします．スクリプトの方で

print "hello world";
exit 0;

とすると，emacsのミニバッファにはhello worldが表示されます．またexit 1とすると，hello worldがポップアップします．また，exit 2では，emacsはカレントバッファをスクリプトが出力したものにします．

どうでも良い話

emacs lispの困るところは，マルチスレッドができないところで，昔emacs lispで送信もするものを使っていたのですが，問題のTLEが長い時やそもそもPKUが落ちているときはなかなか結果が帰ってこなくて，ずっとemacsが固まってました．それはとても嫌だったので，lispで固まらない方法はないかと探して外部スクリプトを実行してexit codeでやりとりする方法を考えました．emacs lispがマルチスレッドに対応してくれればこんなにめんどくさいことをしなくてすむのですが．

UVaとかスクリプトを他の言語でとか，誰か作って欲しいなぁ．

2010-04-04

SRM466 Div1

TopCoder 凡ミス

ケガからの復帰戦．一つも解けなかったけど撃墜成功してdiv1残れた．わーい．

250 LotteryCheating

文字をそんなにたくさん書き換えなくても答えに行くんじゃないかなぁと思って探索してみた．
答えをみると最大5なので，大間違いではない．間違いだけど．
手元でいくつか試してみたらTLEになるケースを発見．
いくつか高速化してみたけど全然間に合わない．
約数が奇数の数字を最初に求めて，そこに変換してみる方法かなぁと思った．
でも2 ^ 32個の候補を最初に調べるわけにいかないし…
- ここで約数奇数の法則性を探しに行くことが正解への分かれ道だったのだろうか．
でも，自分と同じく探索しようとした人は自分がTLEになるサンプルで落とせた．2撃墜．

id:halwhiteさんに探索と思ってはいけないと思うって怒られた(´・ω・｀)ｼｮﾎﾞｰﾝ

500 LotteryPyaterochka

見た感じ解ける気がするー．
でも250が解けてないので，普段解けない500を行くべきかとゆっくり考えられず．
とりあえずチケットは1 2 3 4 5 6 ... と順番に並んでると考えても全く同じことだとわかった．
で，あとはwinning numberが一行三つ以上になる並び方…こんがらかってきて250へ戻る．受験生なら解けたよ．きっと．

方針としては，winning numberが5行，4行のときと3行の一部の時はwinnerになれないということを計算する．あとで書いたらかなりシンプルだった．

class LotteryPyaterochka {
public:
  long long nCr(long long N,long long r){
    if (N < r) return 0;
    long long ret = 1LL;
    REP(i,r)
      ret *= N-i;
    REP(i,r)
      ret /= (i+1);
    return ret;
  }
  double chanceToWin(int N) {
    return 1.0 - (double)(nCr(N,5)*5*5*5*5*5+
                          nCr(N,4)*4*nCr(5,2)*5*5*5 +
                          nCr(N,3)*3*nCr(5,2)*nCr(5,2)*5)/nCr(N*5,5);
    
  }
}

long longにしないと桁あふれするみたい．こういうミスはよくやるので気を付けたい．

1000

未読．500が解けないと，ねぇ…

結果 x x x 2撃墜 100 1247 -> 1268

微増．思えばブログ作っていきなり怪我したのでtopcoder初参戦記だったり．

2010-03-27

1019 Number Sequence

PKU

1019をid:keitanxkeitanが２分探索で解いていて，そんな問題だったかなぁとビックリした．自分のを見返してみたらやっぱり２分探索ではなかった．確かに２分探索でも解けるし実行時間は速いけど，こうやっても解けるよーっていう紹介．

概要

112123123412345... という文字列のi(1 <= i < 2^31)番目の文字を求めよ

考え方．

群数列みたいに考えて，1 12 123 1234 ...と分けて，x番目の群はいくつ文字を含むかを考える．x番目の群は少なくともx文字以上含みそうなので，x番目の群までの文字数の合計はx(x+1)/2より多そう．だから，xの範囲は x(x+1)/2 < 2^32 => x < 2^16ぐらいになりそう．多く見積もって2^16ぐらいまで調べればよいので，２分探索しなくても十分間に合う．

ソース内では，numcntがx番目の群の中の文字数を数える関数．含まれる群がわかったら，その群の文字列をstringstreamで生成してその文字列のi - sum(numcnt(1),numcnt(2),...,numcnt(x-1))番目の文字を出力している．

long long?

keitanはlong longを使っていたけど，確かに2^31番目あたりの文字を調べようとすると，それを含む群までの文字数の合計は2^31を超えてしまう．でも，足していくのではなく，引いていけば2^31を超えることはない．(ソース見てください)

数字->文字列変換

数字を文字にしたり，また長い文字列を単語に分ける時はstringstreamが便利．

stringstream ss;
ss << 1 << 2 << 3; // ssの中身は"123"
string s;
ss >> s; // sは"123"

stringを使いたくないときはsprintfとか．

char s[10];
sprintf(s,"%d%d%d",1,2,3); //s は "123"

TopCoderでも"abc def ghi"みたいなstringが与えられて切り分けなきゃいけない時があるので，このときstringstreamを知ってると知っていないでは大違い．

ソース

int numcnt(int d){
  int a = d;
  int ret = 0;
  int t = 1;
  int b = 1;
  while (d >= 10){
    ret += t * 9 * b;
    d /= 10;
    t++;
    b*=10;
  }
  return ret + t * (a - b + 1);
}

int main(){
  int T=nextInt();
  while (T--){
    int N=nextInt();
    int i;
    for (i=1;N-numcnt(i) > 0;i++)
      N -= numcnt(i);
    stringstream ss;
    for (int j=1;j<=i;j++)
      ss << j;
    string str;
    ss >> str;
    cout << str[N-1] << endl;
  }
}

2010-03-25

TopCoder SRM464 Div1 550

TopCoder

参加はしていない．

概要

n組の中心座標のペアが与えられる．各組の座標を必ずどちらかひとつ使って正方形をn個描く．最小の正方形が最大となるような座標の選び方をしたときの正方形の一辺の長さを求めよ．

解法

2-SAT+2分探索
2-SATはだいぶ前にPKUで，2-SATで解けるらしいという問題を見たけど，実際に書いたことはなく，理解もちゃんとしていなかったのでこれを機にちゃんと解いた．
2-SATはCNFの節の個数が2個のものを解くアルゴリズム．CNFの節をimplicationの形に書き換え，各変数を頂点，implicationを辺とするグラフを作成する． $(p \vee q) \equiv (\~p \to q)$
そして $(p \to \~ q \to \~ p ) \wedge (\~ p \to q \to p)$ のような矛盾が生じないかを確認する．この例では，pか~pのどちらかが成田っていなければいけないのに，どちらでも矛盾が生じてしまう．

この問題では，i番目の座標ペアを $p_{ia},p_{ib}$ とすると，piaとpibは同時に成り立ってはいけないので否定の関係にあり，またpiaが成り立つときpjaが成り立たない事を $p_{ia} \to p_{jb}$ と表せる．この通りにグラフを生成し，矛盾が生じるかどうかを調べればよい．

この問題は頂点の数が少ないためWarshall-Floyd(O(n^3))でも大丈夫．高速化が必要な場合は強連結成分分解を用いてO(n+m)(mは節の個数)でもできる．以下はワーシャルフロイドを用いて実装した．

class ColorfulDecoration {
public:
  vector<int> xa,ya,xb,yb;
  bool check(int mid){
    int n = xa.size(),N=2*n;
    bool graph[N][N];
    memset(graph,false,sizeof(graph));
    REP(i,N)REP(j,N){
      int ii = i/2,jj=j/2;
      if (ii  == jj) continue;
      int x1,y1,x2,y2;
      if (i & 1) x1 = xa[ii],y1 = ya[ii];
      else x1 = xb[ii],y1 = yb[ii];
      if (j & 1) x2 = xa[jj],y2 = ya[jj];
      else x2 = xb[jj],y2 = yb[jj];
      if (abs(x1-x2) < mid && abs(y1-y2) < mid){
        graph[i][j ^ 1] = true;
      }
    }
    REP(i,2*n) graph[i][i] = true;
    REP(k,2*n) REP(i,2*n) REP(j,2*n){
      if (graph[i][k] && graph[k][j])
        graph[i][j] = true;
    }
    bool flag = true;
    for (int i=0;i<2*n;i+=2){
      if (graph[i][i+1] &&
          graph[i+1][i]) flag = false;
    }
    return flag;
  }
  int getMaximum(vector <int> XA, vector <int> YA, vector <int> XB, vector <int> YB) {
    xa = XA;
    xb = XB;
    ya = YA;
    yb = YB;
    int l = 0,h=1000000001;
    while (l < h){
      int mid = (l + h) / 2;
      if (check(mid)){
        l = mid+1;
      }else{
        h = mid;
      }
    }
    return l-1;
  }
}

2010-03-10

手首のリハビリ替わりにPKU．まだまだかくのしんどい．

PKU

概要

与えられた迷路のどこにいても脱出できる最短の方向リストを求めよ．
壁の方向に進もうとした場合はその場にとどまる．複数解ある場合はどれを出力してもよい．

その昔に友人がヒューリスティックで解いたよーとかいってて，どうやって解くんだろうと思っていたけど，病院に持っていったプリントにこの問題があったので考えてみた．この問題は64マスなので，setでキャッシュを取れるので幸せ．

解法

最初に出口と壁以外の全てのところに人がいると仮定して一歩ずつ動かして行く．幅優先だと余裕でTLEなので，ヒューリスティックに解く．ヒューリスティックの値は，『出口から一番遠い人の距離』(簡単だけど反転)．状態をビットで持ったせいか結構速く解けた(282MS)．

その他

最初通るわけねーと思ってリアルインプットでテストしながらやってました．ごめんなさい．
間違ったところは，long longを使うとき気をつけなきゃいけない

1LL << (i*N+j))

のLLの部分．わかってはいたのだけど，1LL << 32 == 2^32だけど，1 << 32 == 0．書き忘れていたところが何箇所か・・・

ブログの書き方わかんないから読みにくいかも．ごめんなさい．
ああ、手が痛い．