備忘録がてらICPC模擬地区大会及び地区大会で使用する"CSUS Programming Constest Control System"通称PC^2の使用法をまとめておこうと思います。Windows 7を前提に書いていますが、その他の環境でも同様の方法で動くと思います。以下、サーバー・ジャッジ・…

PKUとCodeforces用の補助スクリプトを過去に公開したのだが、一つのスクリプトで両方に対応したいと考えて統合してみた。さらに、M-JudgeとAOJにも対応してみた。対応オンラインジャッジ PKU JudgeOnline http://poj.org/ Codeforces http://www.codeforces.…

C++を書くときにはいつもVisual Studio 2010を使っている。Visual Studio 2010は個人的には非常によく出来たIDEだと思うのだが、非常につかづらい点が一つある。ヘルプだ。Visual Studio 2008の時のヘルプは専用のクライアントソフト(?)で閲覧する形になって…

端的に言うと、AnalyzerとTokenizerを継承したクラスをそれぞれ作れば良い。今回作成したTokenizerは以前よりQMACloneで使用している、辞書に含まれている単語を抜き出すというTokenizerである。アルゴリズムはVitabiアルゴリズムを少しだけ変えただけなので…

自分が開発・運営しているQMACloneでは全文検索エンジンにtritonn-MySQLを使用している。tritonnを使用する場合、yumやaptでインストールすることができるMySQLパッケージを使うことが実質できなくなってしまう(正確には共存できるはずだが面倒)。このためメ…

LLVMで(ryものすごくどうでも良いようなことをやっているような気がしないでもないのだが、とりあえずできたので書く。前回二つ分の合わせ技で行けるらしい。LLVMには関数ポインタを表す型は用意されていないっぽい(?)ので、代わりにi8*を使用する。ソースコ…

前の記事に引き続いてLLVMでJITアドレス空間にある関数にアクセスする方法。LLVMのチュートリアルのCh.4にやり方が載っているのだが、そのままでは動かなかった。理由はLLVMが関数のシンボルを見つけられないかららしい。VisualStudioではシンボルのエクスポ…

久々にLLVMをいじっている。LLVMにロマンを感じるのは自分がそういう人間だからなのだろうと思う。LLVMを使って作りたいと思っているものがあって、そのための下調べをしている。まずはJITアドレス空間にあるメモリにアクセスする方法。ネットを探したところ…

はてなダイアリーにPKUの解答をアップロードするのをやめようと思います。 理由はTokyoTechCoderと重複してアップロードするのが面倒になったためです。 今後はTokyoTechCoderのみにアップロードして行きたいと思います。

強連結成分分解 グループの定義が問題から読み取りにくい 実はちゃんとわかっていない Spaghetti Source - 強連結成分分解 http://www.prefield.com/algorithm/graph/strongly_connected_components.html int main() { int N, M; cin >> N >> M; Graph g(N +…

動的計画法 左上と右上の値のうち大きい方を伝搬していく int main() { int N; cin >> N; int dp[2][512]; memset(dp, 0, sizeof(dp)); int front = 1; int back = 0; int bestAnswer = INT_MIN; for (int row = 1; row <= N; ++row) { for (int column = 1;…

二分探索 整数部分を固定すると、小数部分は単調増加になる 整数部分をループで回して二分探索をすると通る long double TENS = 1.0; int saturate(long double value) { value -= (int)value; value *= TENS; return (int)value; } int main() { int L; cin…

やるだけ パターンは空気を読めばおｋ int main() { int N, S; cin >> N >> S; --S; REP(i, N) { int value = S++; REP(j, N) { if (j) { cout << " "; } if (i > j) { cout << " "; } else { cout << value + 1; } value += j + 1; value %= 9; } cout << e…

枝刈り探索 計算量は不明 int N, C; ll weights[1024]; ll sumWeights[1024]; ll bestAnswer = 0; void dfs(int i, ll value) { if (value + sumWeights[i] <= bestAnswer) { return; } bestAnswer = max(bestAnswer, value); if (i == N) { return; } if (v…

動的計画法 時間->コスト の表をmapでsparseに持たせている 牛で2重ループを回しても間に合うらしい struct Cow { int T1, T2, S; bool operator < (const Cow& rh) const { return T1 != rh.T1 ? T1 < rh.T1 : T2 != rh.T2 ? T2 < rh.T2 : S < rh.S; } }; i…

幅優先探索 及び全探索 以下のコードはPKUではTLE static const int dx[] = {0, 0, 1, -1}; static const int dy[] = {1, -1, 0, 0}; int main() { for (int w, h; cin >> w >> h && (w || h); ) { char maze[32][32]; memset(maze, 'x', sizeof(maze)); vec…

拡張ダイクストラ法 [最後に訪れた頂点][使用したチケットの集合]でダイクストラ 又は[最後に訪れた頂点][何枚目のチケット化]を外側でチケットの順番を回しても良い 以下の回答はPKUではTLE struct State { double cost; int node; int nextTicket; State(d…

やるだけ int table[0x80]; string encode(int n) { static const string letters = "ixcm"; static const string digits = "0123456789"; string s; for (int i = 0; i < 4; ++i) { int value = n % 10; n /= 10; if (value) { s = letters.substr(i, 1) + …

幾何 図形を何らかの形で正規化して比較する ここでは始点から各点への長さと角度で正規化している typedef complex<double> P; typedef vector<pair<double, double> > Normalized; bool equals(const Normalized& first, const Normalized& second) { if (first.size() != second.size()</pair<double,></double>…

やるだけ int main() { int m; cin >> m; REP(caseIndex, m) { int money, year, n; cin >> money >> year >> n; int bestAnswer = 0; REP(typeIndex, n) { int type, cost; double ratio; cin >> type >> ratio >> cost; if (type) { // 複利 int m = money…

以前公開していた焼きなましライブラリが古くなったので、新しく公開します。そして、以前の記事を編集しようとしたところ、誤って削除してしまいました。もとには戻せないようです・・・。 typedef long long ll; #define REP(i,n) for(int i=0;i<(int)n;++…

間にsshトンネル経由で自宅サーバーのファイルシステムがマウントできたらなぁと思っていたのだが、sshfsというそのまんまのソフトが有ることを知った。早速試してみようと思ったのだが、FUSEが必要となるらしく、いつも使っているWindows+Cygwinでは動かす…

ダイクストラ法 [x座標][y座標][右足/左足]でコストを持たせる [左足x座標][左足y座標][右足x座標][右足y座標]だとTLEだった const int dx[] = {1, 1, 1, 1, 1, 2, 2, 2, 3}; const int dy[] = {2, 1, 0, -1, -2, 1, 0, -1, 0}; static int dp[32][64][2]; s…

やるだけ ケーキに番号を振るやり方を間違えてREを連発してしまった struct Piece { int x, y; Piece() { } Piece(int x, int y) : x(x), y(y) { } }; int main() { for (int n, w, d; cin >> n >> w >> d && (n || w || d); ) { vector<Piece> ps; ps.push_back(Pi</piece>…

やるだけ 時間の分だけ配列を取って塗りつぶしていく方法と、数直線状で扱う方法がある この解答は後者 int main() { for (int N, M; cin >> N >> M && (N || M); ) { int r; cin >> r; vector<vector<pair<int, int> > > loginout(M + 1); REP(i, r) { int t, n, m, s; cin >> t ></vector<pair<int,>…

深さ優先探索 幅優先探索と見せかけておいて、実は最大10手まで 4^10=2^20で通ってしまう const int dx[] = {0, 0, 1, -1}; const int dy[] = {1, -1, 0, 0}; int maze[32][32]; int w, h; int answer; bool in(int x, int y) { return 0 <= x && x < w && 0 …

素数 TLEがきついためおそらくエラトステネスの篩が必須 int main() { #define MAX (1024*1024) static bool flag[MAX]; memset(flag, -1, sizeof(flag)); flag[0] = flag[1] = false; for (int i = 2; i * i < MAX; ++i){ if (!flag[i]){ continue; } for (…

幅優先探索 あらかじめエラトステネスの篩で素数表を作っておく static const int pows[] = {1, 10, 100, 1000}; int change(int number, int digit, int insert) { switch (digit) { case 0: return number / 10 * 10 + insert; case 1: return number / 10…

幾何 接する点を固定してベクトルの足し算と引き算 typedef complex<double> P; void go(const P& a, const P& b, const P& c, const P& d) { if (abs(a - c) > EPS) { return; } assert(abs(a - d) > EPS); assert(abs(b - c) > EPS); assert(abs(b - d) > EPS); P </double>…

幾何 複素数ライブラリを使うと楽 角度でソートして尺取メソッド int main() { double r; for (int X, Y; cin >> X >> Y >> r && r >= 0.0; ) { int N; cin >> N; vector<double> angles; for (int n = 0; n < N; ++n) { int x, y; cin >> x >> y; x -= X; y -= Y; i</double>…