Hatena::ブログ(Diary)

macbook air is so hot(低温やけど的な意味で)

2013-12-01

Chrodic - Google Chrome™で動くマウスオーバー辞書拡張

01:25 |

ChrodicGoogle Chromeで動くmouseover dictionary extensionです。

f:id:kkishi:20131202000540p:image

特徴

作ったわけ

Firefoxで愛用していたMouseoverDictionaryという素晴らしいextensionがあるのですが、それと同じようなものがGoogle Chromeに無かった。Chromeを使い始めて以来ALCウェブサイトで引いていたのだけど、タブ移動のコンテキストスイッチがわずらわしくなってきたので作りました。

使い方

$ iconv -c -f SJIS -t UTF-8 EIJI-118.TXT > EIJI-118-utf-8.TXT

f:id:kkishi:20131202004324p:image

f:id:kkishi:20131202014429p:image

Ankiwebに単語を保存する場合

  • Ankiwebログインしておく。
  • 保存先のDeckをChrodicのOptionsページで設定する。

f:id:kkishi:20131202014430p:image

  • 保存したい単語の横に出ている数字に対応したキーを押す。

f:id:kkishi:20131202014431p:image

ソース

githubで公開しています。git pull & Load unpacked extensionインストールできます。

2010-03-02

IEEEXtreme 2009 の賞品が届いた

| 19:48 |

IEEEXtremeという、IEEE主催で1.5年に1回ほどのペースで開催されているプログラミングコンテストがあります。

今回で3回目となる本大会に、Konohanasakuyaというチーム名で@nodchipと@bonboriと一緒に参加しました。

二人のパワーのおかげで5位/700チームになれたので賞品が届きました。

コンテスト概要(@nodchip先生の記事)

http://topcoder.g.hatena.ne.jp/nodchip/20091026/1256527977

結果

http://www.ieee.org/web/membership/students/xtreme/2009results.html

賞品一覧

Tシャツ表

f:id:kkishi:20100302190859j:image

Tシャツ裏

f:id:kkishi:20100302190912j:image

ボールペン

f:id:kkishi:20100302191016j:image

ステッカー

f:id:kkishi:20100302190959j:image

2010-02-25

POJ 1769 Minimizing maximizer

| 01:36 |

データ構造を工夫しないと通らない、かといって典型的なデータ構造を探してきて適用すれば良いわけではない。どうにかオーダーに間に合うように工夫するのが楽しかった問題。

長さn (2 <= n <= 50000)の任意の数列を入力として、最も大きな数を出力する機械(Maximizer)を作りたい。ただし部品として使える道具は、ある区間[i, j] (1 <= i, j <= n) を昇順ソートしてくれる機械(Sorter)だけ。何段かこのSorterを重ねる事でMaximizerを作る。例えばn=10の場合だと[1, 10]のSorterが一つあれば良いし、[1, 5]のSorterの下に[5, 10]のSorterがあっても良い。

問題は、ある完成品のMaximizerが与えられているとき、無駄を省いて最小いくつのSorterでMaximizerが実現できるか答えよというもの。与えられるSorterの数はm(1 <= m <= 500000)。もちろんSorterの順序を入れ替えてはいけない。n=10の場合[1, 5] -> [3, 6] -> [5, 10]は[1, 5] -> [5, 10]に出来るので答えは2。

右端に数列の最大要素が移動しさえすれば良いので、要は上から下に選んだSorterを見ていった時に、左端から右端へ連続して移動できれば良い。f(i)を「ある位置iに最大要素を移動させるための最小コスト(Sorterの数)」として更新していけば答えが求まるので、典型的なDPと言えばそうなんだけれど、問題は最小コストを保持するデータ構造。

int dp[n];  // dp[i] = 位置iへ最大要素を移動させるための最小Sorter数

のようにしてしまいたくなるが、nの更新をm回繰り返すと50000*500000=250憶になってTLE。ここは次のような構造体をsetに入れて更新してゆくことでdpの代用とするのが正解(なのかは分からないがぎりぎり間に合った)。

struct S {
  int l;  // 区間の左端
  int r;  // 区間の右端
  int cost;  // 区間の最小コスト
  bool operator<(const S& s) const {
    return l < s.l;
  }
};

初めにsetには(S){1, n, INT_MAX}を入れておく。各段階では新たなSorterによって更新可能な範囲を書き換えていく。要はdpの区間を圧縮したようなもの。新たなSorterで更新可能な範囲の右端と左端の検索はlog(n)程度で済むし、区間はプログラムの実行全体でO(m)ほどしか生成されないので、setの各区間を更新していってもO(m*log(n))の時間で済む。

計算量の考察とそこそこの実装を求める良い問題でした。

2009-11-05

srm452

| 23:42 |

とても久しぶりに参加。


div1:250 NotTwo

最大1000*1000の盤面に、ユークリッド距離が丁度2になるような石のペアが存在しないように可能な限り石を置いた時に最大でいくつ置けるか。

整数座標でユークリッド距離が丁度2になるのは上下左右に2マス離れた場合だけ。

なので石を一つ置くと、置けないという制約がかかった場所が新たに最大4つできる。

制約がかかった場所を最小にしたいが、共有出来る制約が最大4である事は明らか。

そのような置き方は、盤面が無限に広がっている場合「斜めにジグザクに置く」「2*2の石を出来るだけ敷き詰める」という二つの置き方が考えられる。

盤面が2*2とかの時を特別扱いしなくて済むので後者でやると楽。

というのは終わってから気づいた話で、system test中とてもひやひやしてました。

passed system test 174.04

div1:500 IOIString

I,O,?の三文字のみからなる最大長さ2500の文字列が与えられる。

?をIまたはOと置き換えると、

I...(n文字)...O...(n文字)...I

のような部分文字列を含む文字列(IOI string)はいくつ出来るか。

IOI stringでない文字列の数はそれほど多くないので、そっちを引くのかなぁと思った程度。

compiled(challengeする事もあろうかと思って)

div1:1000

読んでません。

opened


結果は250で得た174.04のみで、レーティングは1413 -> 1427と微増。

良いなー黄色良いなー。

2009-09-14

C++テンプレートメタプログラミングでbrainfuck

17:34 |

フィボナッチや階乗を計算させるような、一つの整数値が結果になるものは書いた事があったのですが、もっと複雑なものを書いてみたくなったので、チューリング完全性の証明もおまけでついてくるbrainfuckインタプリタを書いてみました。

#include <cstdio>

//////////
// List //
//////////
class Null {};

template<class T, class U>
struct List {
  typedef T Head;
  typedef U Tail;
};

////////////
// Length //
////////////
template<class L>
struct Length;

template<>
struct Length<Null> { enum { value = 0 }; };

template<class T, class U>
struct Length<List<T, U> > { enum { value = 1 + Length<U>::value }; };

/////////////
// Reverse //
/////////////
template<class T, class U>
struct ReverseIter;

template<class T>
struct ReverseIter<Null, T> {
  typedef T Result;
};

template<class T, class U, class V>
struct ReverseIter<List<U, V>, T> {
  typedef typename ReverseIter<V, List<U, T> >::Result Result;
};

template<class L>
struct Reverse {
  typedef typename ReverseIter<L, Null>::Result Result;
};

/////////
// Int //
/////////
template<int v>
struct Int { enum { value = v }; };

//////////
// Char //
//////////
template<char c>
struct Char { static const char value = c; };

////////////////
// MakeMemory //
////////////////
template<unsigned int n>
struct MakeMemory {
  typedef List<Int<0>, typename MakeMemory<n - 1>::Result> Result;
};

template<>
struct MakeMemory<0> {
  typedef Null Result;
};

/////////
// Ref //
/////////
template<class T, unsigned int n>
struct Ref {
  enum { value = Ref<typename T::Tail, n - 1>::value };
};

template<class H, class T>
struct Ref<List<H, T>, 0> {
  enum { value = H::value };
};

///////////////
// BrainFuck //
///////////////
template<class PH, class PT, class MH, class MT, class StdOut>
struct BF;

// Finish
template<class PH, class MH, class MT, class StdOut>
struct BF<PH, Null, MH, MT, StdOut> {
  typedef typename Reverse<StdOut>::Result Result;
};

// > command
template<class PH, class PT, class MH, class U, class V, class StdOut>
struct BF<PH, List<Char<'>'>, PT>, MH, List<U, V>, StdOut> {
  typedef typename BF<List<Char<'>'>, PH>, PT, List<U, MH>, V, StdOut>::Result Result;
};

// < command
template<class PH, class PT, class U, class V, class MT, class StdOut>
struct BF<PH, List<Char<'<'>, PT>, List<U, V>, MT, StdOut> {
  typedef typename BF<List<Char<'<'>, PH>, PT, V, List<U, MT>, StdOut>::Result Result;
};

// + command
template<class PH, class PT, class MH, class U, class V, class StdOut>
struct BF<PH, List<Char<'+'>, PT>, MH, List<U, V>, StdOut> {
  typedef typename BF<List<Char<'+'>, PH>, PT, MH, List<Int<U::value + 1>, V>, StdOut>::Result Result;
};

// - command
template<class PH, class PT, class MH, class U, class V, class StdOut>
struct BF<PH, List<Char<'-'>, PT>, MH, List<U, V>, StdOut> {
  typedef typename BF<List<Char<'-'>, PH>, PT, MH, List<Int<U::value - 1>, V>, StdOut>::Result Result;
};

// . command
template<class PH, class PT, class MH, class MT, class StdOut>
struct BF<PH, List<Char<'.'>, PT>, MH, MT, StdOut> {
  typedef typename BF<List<Char<'.'>, PH>, PT, MH, MT, List<Char<MT::Head::value>, StdOut> >::Result Result;
};

// [ command
template<class PH, class PT, class MH, class MT, class StdOut, int level>
struct BFOBLOOP {
  typedef typename BFOBLOOP<List<typename PT::Head, PH>, typename PT::Tail, MH, MT, StdOut, level>::Result Result;
};

template<class PH, class PT, class MH, class MT, class StdOut>
struct BFOBLOOP<PH, PT, MH, MT, StdOut, 0> {
  typedef typename BF<PH, PT, MH, MT, StdOut>::Result Result;
};

template<class PH, class PT, class MH, class MT, class StdOut, int level>
struct BFOBLOOP<PH, List<Char<'['>, PT>, MH, MT, StdOut, level> {
  typedef typename BFOBLOOP<List<Char<'['>, PH>, PT, MH, MT, StdOut, level + 1>::Result Result;
};

template<class PH, class PT, class MH, class MT, class StdOut, int level>
struct BFOBLOOP<PH, List<Char<']'>, PT>, MH, MT, StdOut, level> {
  typedef typename BFOBLOOP<List<Char<']'>, PH>, PT, MH, MT, StdOut, level - 1>::Result Result;
};

template<class PH, class PT, class MH, class MT, class StdOut, bool jump>
struct BFOB {
  typedef typename BFOBLOOP<PH, PT, MH, MT, StdOut, 1>::Result Result;
};

template<class PH, class PT, class MH, class MT, class StdOut>
struct BFOB<PH, PT, MH, MT, StdOut, false> {
  typedef typename BF<PH, PT, MH, MT, StdOut>::Result Result;
};

template<class PH, class PT, class MH, class U, class V, class StdOut>
struct BF<PH, List<Char<'['>, PT>, MH, List<U, V>, StdOut> {
  typedef typename BFOB<List<Char<'['>, PH>, PT, MH, List<U, V>, StdOut, U::value == 0>::Result Result;
};

// ] command
template<class PH, class PT, class MH, class MT, class StdOut, int level>
struct BFCBLOOP {
  typedef typename BFCBLOOP<typename PH::Tail, List<typename PH::Head, PT>, MH, MT, StdOut, level>::Result Result;
};

template<class PH, class PT, class MH, class MT, class StdOut>
struct BFCBLOOP<PH, PT, MH, MT, StdOut, 0> {
  typedef typename BF<PH, PT, MH, MT, StdOut>::Result Result;
};

template<class PH, class PT, class MH, class MT, class StdOut, int level>
struct BFCBLOOP<List<Char<']'>, PH>, PT, MH, MT, StdOut, level> {
  typedef typename BFCBLOOP<PH, List<Char<']'>, PT>, MH, MT, StdOut, level + 1>::Result Result;
};

template<class PH, class PT, class MH, class MT, class StdOut, int level>
struct BFCBLOOP<List<Char<'['>, PH>, PT, MH, MT, StdOut, level> {
  typedef typename BFCBLOOP<PH, List<Char<'['>, PT>, MH, MT, StdOut, level - 1>::Result Result;
};

template<class PH, class PT, class MH, class MT, class StdOut, bool jump>
struct BFCB {
  typedef typename BFCBLOOP<typename PH::Tail, List<typename PH::Head, PT>, MH, MT, StdOut, 1>::Result Result;
};

template<class PH, class PT, class MH, class MT, class StdOut>
struct BFCB<PH, PT, MH, MT, StdOut, false> {
  typedef typename BF<PH, PT, MH, MT, StdOut>::Result Result;
};

template<class PH, class PT, class MH, class U, class V, class StdOut>
struct BF<PH, List<Char<']'>, PT>, MH, List<U, V>, StdOut> {
  typedef typename BFCB<List<Char<']'>, PH>, PT, MH, List<U, V>, StdOut, U::value != 0>::Result Result;
};

// read other character
template<class PH, class U, class PT, class MH, class MT, class StdOut>
struct BF<PH, List<U, PT>, MH, MT, StdOut> {
  typedef typename BF<List<U, PH>, PT, MH, MT, StdOut>::Result Result;
};

// interface
template<class Program>
struct BrainFuck {
  typedef typename BF<Null, Program, Null, MakeMemory<256>::Result, Null>::Result Result;
};

///////////////
// Execution //
///////////////
typedef List<Char<'+'>, List<Char<'+'>, List<Char<'+'>, List<Char<'+'>, List<Char<'+'>, List<Char<'+'>, List<Char<'+'>, List<Char<'+'>, List<Char<'+'>, List<Char<'['>, List<Char<'>'>, List<Char<'+'>, List<Char<'+'>, List<Char<'+'>, List<Char<'+'>, List<Char<'+'>, List<Char<'+'>, List<Char<'+'>, List<Char<'+'>, List<Char<'>'>, List<Char<'+'>, List<Char<'+'>, List<Char<'+'>, List<Char<'+'>, List<Char<'+'>, List<Char<'+'>, List<Char<'+'>, List<Char<'+'>, List<Char<'+'>, List<Char<'+'>, List<Char<'+'>, List<Char<'>'>, List<Char<'+'>, List<Char<'+'>, List<Char<'+'>, List<Char<'+'>, List<Char<'+'>, List<Char<'<'>, List<Char<'<'>, List<Char<'<'>, List<Char<'-'>, List<Char<']'>, List<Char<'>'>, List<Char<'.'>, List<Char<'>'>, List<Char<'+'>, List<Char<'+'>, List<Char<'.'>, List<Char<'+'>, List<Char<'+'>, List<Char<'+'>, List<Char<'+'>, List<Char<'+'>, List<Char<'+'>, List<Char<'+'>, List<Char<'.'>, List<Char<'.'>, List<Char<'+'>, List<Char<'+'>, List<Char<'+'>, List<Char<'.'>, List<Char<'>'>, List<Char<'-'>, List<Char<'.'>, List<Char<'-'>, List<Char<'-'>, List<Char<'-'>, List<Char<'-'>, List<Char<'-'>, List<Char<'-'>, List<Char<'-'>, List<Char<'-'>, List<Char<'-'>, List<Char<'-'>, List<Char<'-'>, List<Char<'-'>, List<Char<'.'>, List<Char<'<'>, List<Char<'+'>, List<Char<'+'>, List<Char<'+'>, List<Char<'+'>, List<Char<'+'>, List<Char<'+'>, List<Char<'+'>, List<Char<'+'>, List<Char<'.'>, List<Char<'-'>, List<Char<'-'>, List<Char<'-'>, List<Char<'-'>, List<Char<'-'>, List<Char<'-'>, List<Char<'-'>, List<Char<'-'>, List<Char<'.'>, List<Char<'+'>, List<Char<'+'>, List<Char<'+'>, List<Char<'.'>, List<Char<'-'>, List<Char<'-'>, List<Char<'-'>, List<Char<'-'>, List<Char<'-'>, List<Char<'-'>, List<Char<'.'>, List<Char<'-'>, List<Char<'-'>, List<Char<'-'>, List<Char<'-'>, List<Char<'-'>, List<Char<'-'>, List<Char<'-'>, List<Char<'-'>, List<Char<'.'>, List<Char<'>'>, List<Char<'+'>, List<Char<'.'>, Null > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > HelloWorld;
typedef BrainFuck<HelloWorld>::Result OutPut;

///////////
// Print //
///////////
template<class L>
inline void Print(L l);

template<>
inline void Print(Null l) { printf("\n"); }

template<class T, class U>
inline void Print(List<T, U> l) { printf("%c", T::value); Print(U()); }

int main() {
  Print(OutPut());
  return 0;
}

HelloWorldというのがbrainfuckプログラム本体です。Char<c>の型リストになっています。

インタプリタ本体は

template<class PH, class PT, class MH, class MT, class StdOut>
struct BF;

で、実行しているプログラムとメモリをzipper(kinabaさんの記事参照)で持っています。PHとPTがプログラム、MHとMTがメモリで、PTの先頭がプログラムポインタMTの先頭がメモリポインタです。

標準出力もStdOutという名前でリストで持っていて、実行が終わると

// Finish
template<class PH, class MH, class MT, class StdOut>
struct BF<PH, Null, MH, MT, StdOut> {
  typedef typename Reverse<StdOut>::Result Result;
};

でReverseして返されます。

最後にオーバーローディングされたPrint関数を呼び出す事で結果の型リストを表示しています。-O2をかけるとネストした関数呼び出しがフラットになって、mainではputcharを連続して呼び出すだけのコードになります。

条件分岐のたびに別の特殊化したテンプレートを実体化する必要があり、またg++は末尾呼び出しの最適化を行ってくれないので、あまり実行ステップの多いプログラムを実行する事はできません。HelloWorldを実行するだけでもデフォルトオプションではだめで、コンパイル

g++ -ftemplate-depth-1000 brainfuck.cc

のようにしてテンプレート実体化の深さの制限を増やしてやる必要があります。

関数定義があちこちに散らばってしまうのでとても書きづらいですが、引数のパターンマッチングが出来るのはなかなか気持ちがいいですね。

Connection: close