2009-06-09

UTPC2009

プログラミング

去年は出題側でしたが、今年は解く側で参加。結果は6問で(24)位(1問去年の問題案から使い回しがあるので順位は参考ということで)

A

やるだけ。Accept

B

典型的なDP。ただ点ではなくエッジが通れないので２問目にしてはややめんどう。Accept

C

一人の方の手を固定して、残りの手を9!通り試すだけ。Accept
一瞬モンテカルロとか頭の悪いことを思いついた。

D

最初面倒と思って飛ばす

E

なぜか4桁しかないと思って、探索のコードを書き終わった後に1000桁だということに気づく。

F

50000^2の解法は分かるんだけど、そこから枝刈すれば通るのかなとか思う。

D

とりあえずやれば解けるのは明らかなので書き始める。最初BigDecimalとかを使おうと思ってAPIを読みだしたけどはまりそうだったので、まじめに文字列処理をしだす。
0.000...の部分を除去するところで

replaceFirst("^0\\.(0*)", "")

とするべきところを

replaceFirst("0\\.(0*)", "")

と書いていてはまった。
Accept

E

探索のコードの4桁での出力を眺めていると縮約の回数が隣り合う文字列の取り方によらないことに気づく、ということであまり確証はなかったが先頭から縮約するコードを送ったら通る。
Accept

G

解いていた人が一番多かったので、読んでみる。とりあえず解いている人の人数から単純にシミュレーションして、十分な回数回したらループと判定するというロジックで通るのではという方針で書く。
途中>=とすべきなところを>と書いていてはまる。
Accept

F

とりあえず、25億だったら間に合う気がして送ったら案の定TLE。でその後入力をScannerからBufferedReaderに変更したり小手先の最適化を行ったけど通らない。
オートマトンを作ればいいのではとか思ったけど、どうみてもNFAになるので線形時間だと無理。

残り時間はFとあとI,Kあたりを考えていたが通せず終了。

2009-05-23

メモ：Makefileで明示的にコマンドを実行させる。

プログラミング

a.out: A.cpp
	g++ -o a.out A.cpp
clean:
	rm -f a.out

のようなコードを書いて、make cleanと行った場合にcleanというファイルがディレクトリにあると'clean'を最新版と判定するため実行されない。
明示的に実行させるためには以下の行を追加すればうまくいく。

.PHONY : clean

参考：http://www.ecoop.net/coop/translated/GNUMake3.77/make_4.jp.html

2009-05-16

Warm Up Contest

プログラミング

会津大学主催のプログラミングコンテストに参加してみた。
レジストしてからc,c++しか使えないことに気づいてどうしようかと思ったけど、勉強も兼ねて参加。
結果は６問中３問でした。

A：Traffic Analysis

経過時間をソートして最大の間隔のものをとるだけ

B：Cubes Without Holes

n*n*nの立方体(n <= 500)に何本かの線分を貫通させる。このとき穴の開いていない立方体が何個あるか答えよという問題。
500^3 = 1250万だから500*500*500の配列を用意して穴をあけるのをシミュレートしていけば大丈夫かと思ったけどTopCoderと違って1ケースにつき何秒ではなく、何個かのケースの合計で1秒のためTLEをもらった。
結局穴が空いた立方体の座標をsetにつっこんでn^3からsetのサイズを引くという方針で通した。

C：Simple GUI Application

入れ子構造になっているGUIのXMLっぽい設定ファイルが与えられるのでパースしなさいという問題。
パースとかよりもC++で部分文字列をどう取るんだっけみたいな文法的知識がないことに苦戦した。
C.cpp

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

struct Panel{
  vector<Panel> children;
  string name;
  int x1,y1,x2,y2;
  Panel(string name , int x1, int y1 , int x2 , int y2):name(name),x1(x1),y1(y1),x2(x2),y2(y2)
  {}
  void add(Panel p){
    children.push_back(p);
  }
  int size(){
    return children.size();
  }
};

typedef pair<Panel , int> result;

result parse(const string &tags , int p){
  int ts = tags.find('<' , p);
  int te = tags.find('>' , p);
  string name = tags.substr(ts + 1 , te - ts - 1);
  ts = tags.find('<' , te);
  int x1,y1,x2,y2;
  string value = tags.substr(te + 1 , ts - te - 1);
  sscanf(value.c_str() , "%d,%d,%d,%d" , &x1 , &y1, &x2, &y2);
  Panel panel(name , x1 , y1 , x2 , y2);
  string endtag("</"); endtag += name; endtag += ">";
  int et = tags.find(endtag , ts);
  p = ts;
  while(p != et){
    result res = parse(tags , p);
    panel.add(res.first);
    p = res.second;
  }
  result r(panel , et + endtag.size());
  return r;
}

bool find(Panel p , int x , int y){
  if(p.x1 <= x && x <= p.x2 && 
      p.y1 <= y && y <= p.y2){
    if(p.size() == 0){
      cout << p.name << " " << p.size() << endl;
      return true;
    }
    for(int i = 0 ; i < p.size() ; i++){
      Panel child = p.children[i];
      if(find(child , x , y)){
        return true;
      }
    }
    cout << p.name << " " << p.size() << endl;
    return true;
  }
  return false;
}

int main(){
  int n;
  while(1){
    cin >> n;
    if(n == 0)break;
    string tags;
    cin >> tags;
    Panel root = parse(tags , 0).first;
    int x , y;
    for(int i = 0 ; i < n ; i++){
      cin >> x >> y;
      if(!find(root ,x , y)){
        cout << "OUT OF MAIN PANEL 1" << endl;
      }
    }
  }
  return 0;
}

2008-11-09

left-leaning red-black tree

プログラミング

DO++に紹介してあったleft-leaning red-black treeという赤黒木の一種で実装が簡単なものを実装してみた．get,put,deleteを実装したところ156行となった．アルゴリズムイントロダクションの実装が疑似コードで150行程度なので*1．

また，JavaのTreeMapと挿入+検索+削除の合計の実行時間を比較したところオーダー的にはほぼ同程度の性能となった*2．

public class LLRB <Key extends Comparable<Key> , Value>{
  private static final boolean RED = true;
  private static final boolean BLACK = false;  
  private Node root;
  private class Node{
    private Key key;
    private Value val;
    private Node left , right;
    private boolean color;
    
    Node(Key key , Value val , boolean color){
      this.key = key;
      this.val = val;
      this.color = color;
    }
  }
  
  public Value get(Key key){
    return get(root , key);
  }
  
  public void put(Key key , Value value){
    root = put(root, key , value);
    root.color = BLACK;
  }
    
  public boolean isEmpty(){
    return root == null;
  }
  
  public boolean containsKey(Key key){
    return get(key) != null;
  }
  
  public void delete(Key key){
    root = delete(root , key);
    if(root != null)root.color = BLACK;
  }

  private Value get(Node x , Key key){
    while(x != null){
      int cmp = key.compareTo(x.key);
      if(cmp == 0)return x.val;
      else if(cmp < 0)x = x.left;
      else x = x.right;
    }
    return null;
  }
    
  private Node put(Node h , Key key , Value value){
    if(h == null)return new Node(key , value , RED);    
    int cmp = key.compareTo(h.key);
    if(cmp == 0) h.val = value;
    else if(cmp < 0) h.left = put(h.left, key, value);
    else h.right = put(h.right , key , value);
    if(isRed(h.right) && !isRed(h.left)) h = rotateLeft(h);
    if(isRed(h.left) && isRed(h.left.left)) h = rotateRight(h);
    if(isRed(h.left) && isRed(h.right))flipColors(h);
    return h;
  }

  private Node delete(Node h , Key key){
    if(key.compareTo(h.key) < 0){
      if(!isRed(h.left) && !isRed(h.left.left))
        h = moveRedLeft(h);
      h.left = delete(h.left, key);
    }else{
      if(isRed(h.left))
        h = rotateRight(h);
      if(key.compareTo(h.key) == 0 && h.right == null)
        return null;
      if(!isRed(h.right) && !isRed(h.right.left))
        h = moveRedRight(h);
      if(key.compareTo(h.key) == 0){
        h.val = get(h.right , min(h.right));
        h.key = min(h.right);
        h.right = deleteMin(h.right);
      }else
        h.right = delete(h.right , key);
    }
    return fixUp(h);
  }

  private Key min(Node h){
    if(h.left == null)return h.key;
    return min(h.left);
  }

  private Node deleteMin(Node h){
    if(h.left == null)return null;
    if(!isRed(h.left) && !isRed(h.left.left))
      h = moveRedLeft(h);
    h.left = deleteMin(h.left);
    return fixUp(h);
  }
   
  private Node moveRedLeft(Node h){
    flipColors(h);
    if(isRed(h.right.left)){
      h.right = rotateRight(h.right);
      h = rotateLeft(h);
      flipColors(h);
    }
    return h;
  }
  
  private Node moveRedRight(Node h){
    flipColors(h);
    if(isRed(h.left.left)){
      h = rotateRight(h);
      flipColors(h);
    }
    return h;
  }
  
  private Node fixUp(Node h){
    if(isRed(h.right))
      h = rotateLeft(h);
    if(isRed(h.left) && isRed(h.left.left))
      h = rotateRight(h);
    if(isRed(h.left) && isRed(h.right))
      flipColors(h);
    return h;
  }
  
  private Node rotateLeft(Node h){
    Node x = h.right;
    h.right = x.left;
    x.left = h;
    x.color = h.color;
    h.color = RED;
    return x;
  }
  
  private Node rotateRight(Node h){
    Node x = h.left;
    h.left = x.right;
    x.right = h;
    x.color = h.color;
    h.color = RED;
    return x;
  }
  
  private void flipColors(Node h){
    h.color = !h.color;
    h.left.color = !h.left.color;
    h.right.color = !h.right.color;
  }
  
  private boolean isRed(Node h){
    if(h == null)return false;
    return h.color == RED;
  }
}

*1:FIXUPのところは倍で数えています

*2:両対数なので実際は倍程度速度が違います，まあ定数倍なので大した問題ではない

2008-09-23

ダイガンマ関数

プログラミング

http://mallet.cs.umass.edu/より

class Digamma {
  public static final double EULER_MASCHERONI = -0.5772156649015328606065121;
  public static final double DIGAMMA_COEF_1 = 1.0 / 12;
  public static final double DIGAMMA_COEF_2 = 1.0 / 120;
  public static final double DIGAMMA_COEF_3 = 1.0 / 252;
  public static final double DIGAMMA_COEF_4 = 1.0 / 240;
  public static final double DIGAMMA_COEF_5 = 1.0 / 132;
  public static final double DIGAMMA_COEF_6 = 691.0 / 32760;
  public static final double DIGAMMA_COEF_7 = 1.0 / 12;
  public static final double DIGAMMA_LARGE = 9.5;
  public static final double DIGAMMA_SMALL = .000001;

  public static double digamma(double z) {
    double psi = 0;
    if (z < DIGAMMA_SMALL) {
      psi = EULER_MASCHERONI - (1 / z);
      return psi;
    }
    while (z < DIGAMMA_LARGE) {
      psi -= 1 / z;
      z++;
    }
    double invZ = 1 / z;
    double invZSquared = invZ * invZ;
    psi += Math.log(z)
        - .5
        * invZ
        - invZSquared
        * (DIGAMMA_COEF_1 - invZSquared
            * (DIGAMMA_COEF_2 - invZSquared
                * (DIGAMMA_COEF_3 - invZSquared
                    * (DIGAMMA_COEF_4 - invZSquared
                        * (DIGAMMA_COEF_5 - invZSquared
                            * (DIGAMMA_COEF_6 - invZSquared * DIGAMMA_COEF_7))))));
    return psi;
  }
}

2008-05-15

SPOJ Open Contest 2008

プログラミング

http://www.spoj.pl/ZFUN08/
SPOJのコンテストに先週あたりから参加しています。あんまり長期間行うコンテストに参加した経験はなかったのですが、色々と文献調査とかしながら問題を解くのはなかなか面白いです。
一応、一通り手をつけて現在ランキング7位につけています。
追記 5/20までというのを5/20の23:59までと勘違いしてたのだが実際は5/20の00:00で終わりだった。最終結果は11位でした。
圧縮の問題はブロックソート+MTFを行った後適応型レンジコーダで圧縮すると101350byteから35000byteぐらいに縮まって、レンジコーダのところで前の文字列を考慮するようにすると32000byte弱まで縮まった、ただデータを文字列で埋め込んでいて改行記号とかを埋め込めなかったので1バイトあたり7ビットしか情報を持たせられなかったので送ったプログラムのサイズはもう少し悪くなっている(あと解凍プログラムが2000byteほどある)
レンジコーダの実装に当たっては以下のサイトを参考にした。
http://www.geocities.jp/m_hiroi/light/pyalgo36.html
http://www.geocities.jp/m_hiroi/light/pyalgo39.html

2008-04-20

Google AJAX Language API

プログラミング

今研究室で四年生の実験のTAをやっています。実験の題材は「パターン認識システムの製作」でパターン認識を使った何かシステムを作るというもの。テーマを相談させて決定させたところ言語の自動判別をやることになった。
言語の自動判別というと最近Google AJAX Language APIという言語の判別と翻訳を行ってくれるものが出てたなと思って少し触ってみた。
http://d.hatena.ne.jp/j7400157/20080322/1206201444のエントリを参考にして与えられた文章を指定した言語に変換するものを作ってみた、少し変えた所としては言語の変換に失敗した場合、一度英語に直して指定した言語に変換するという処理を行っている。
ソースは以下。またここで動作確認ができる。

<html>
  <head>
    <script type="text/javascript" src="http://www.google.com/jsapi"></script>
    <script type="text/javascript">
      google.load("language", "1");
      function init() {
        var langList = document.getElementById("target-language");
        for (var lang in google.language.Languages) {
          var langOpt = new Option(lang, google.language.Languages[lang]);
          langList.options[langList.options.length] = langOpt;
        }
      }
      google.setOnLoadCallback(init);
      function setResult(result){
        document.getElementById("result").value = result;
      }
      function translate(){
        var source = document.getElementById("source").value;
        google.language.detect(source , function(result){
            if(result.error){
              return ;
            }
            var langList = document.getElementById("target-language");
            var destLang = langList.options[langList.selectedIndex].value;
            //入力言語を選択言語に直す
            google.language.translate(source , result.language , destLang , function(result2){
              if(result2.error){
                translate2(source , result.language , destLang);
                return ;
              }
              setResult(result2.translation);
            });
        });
      }
      function translate2(source , srcLang , destLang){
        //入力言語をまず英語に変換して、その後選択言語に直す
        google.language.translate(source , srcLang , "en" , function(res){
          google.language.translate(res.translation , "en" , destLang , function(res2){
            setResult(res2.translation);
          });
        });
      }
    </script>
  </head>
  <body>
    <textarea id="source" rows="5" cols="50"></textarea><br />
    <select id="target-language"></select>に<input type="submit" value="翻訳" onclick="translate()" /><br />

    <textarea id="result" readonly="readonly" rows="5" cols="50"></textarea></br>
  </body>
</html>

ちなみに言語の自動判別のやりかたとしては

Wikipediaなどから各言語ごとのテキストを教師データとして取ってくる
データをアルファベットの頻度などの特徴量ベクトルに変換する
作成した特徴量ベクトルを用いて、入力に対してNaive Bayesかk-NNを使って判定する

のような方法があるのかなと思っている。