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;
  }
}