制限時間が緩いので全探索を定数レベルで高速化すれば通る bool compareByConditions(const string& lh, const string& rh) { return lh.size() != rh.size() ? lh.size() > rh.size() : lh > rh; } string toString(int value, int length) { char buffer[1…

左/右に降りる場合のビットの変換にパターンがある それをそのまま書けば良い ビット演算のみで一行で書くこともおそらく出来る int main() { int numberOfTestCases; cin >> numberOfTestCases; for (int caseIndex = 0; caseIndex < numberOfTestCases; ++…

動的計画法 パスカルの三角形を定義通り書けば良い int main() { ll dp[128][128]; memset(dp, 0, sizeof(dp)); dp[0][0] = 1; for (int n = 1; n < 128; ++n) { for (int m = 0; m < 128; ++m) { if (m) { dp[n][m] += dp[n - 1][m - 1]; } dp[n][m] += dp[…

動的計画法 直前のマスの最適解を用いて現在のマスの最適解を求める int main() { int N; cin >> N; int first; cin >> first; vector<int> dp; dp.push_back(first); int bestAnswer = INT_MIN; for (int n = 2; n <= N; ++n) { vector<int> next; for (int i = 0; i </int></int>…

素直に実装するのみ 問題文を読み間違えて1WA int main() { int caseIndex = 0; for (int S, T, M; cin >> S >> T >> M && (S || T || M); ) { int counter[128][3]; memset(counter, 0, sizeof(counter)); for (int s = 0; s < S; ++s) { int Id; cin >> Id…

2点をfor文で回す 対応する残り2点が存在するかどうかをlog(N)で調べる int main() { for (int n; cin >> n && n; ) { set<pair<int, int> > positionSet; vector<pair<int, int> > positions; for (int i = 0; i < n; ++i) { int x, y; cin >> x >> y; positions.push_back(make_pair(x, y</pair<int,></pair<int,>…

全部同じ高さになるように移動するのみ int main() { int caseIndex = 0; for (int n; cin >> n && n; ) { vector<int> heights; int sum = 0; for (int i = 0; i < n; ++i) { int height; cin >> height; heights.push_back(height); sum += height; } const int</int>…

おにゅうPのクソゲー実況プレイを歌ってみました。知り合いから教えてもらったフリーの音程補正プラグインを使ってみました。自分の音程の不安定さをひしひしと感じましたorz

深さ優先探索 初めに待ちを固定して手に加えた状態から探索開始 深さ0〜3では順子・刻子を全数検査 深さ4では頭を全数検査 解となる文字列の生成ではどの順子・刻子・頭に待ちがあるかを固定して生成 重複した解が出力されないようsetを使用 途中状態をメモ…

動的計画法 以下の三つのパターンを考えれば良い 一つ前から縦のタイルを置くパターン 二つ前から横のタイル二つを置くパターン 二つ前から正方形のタイルを置くパターン 組み合わせの数が膨大になるため多倍長整数が必要となる nが64ビットまでかつmod何と…

動的計画法 次に奇数の液体を飲む場合は偶数番目の液体を飲んだ後の力の最大値+strengthに更新する 次に偶数の液体を飲む場合は上記の逆 int main() { int odd = INT_MIN / 2; int even = 0; int P; cin >> P; for (int i = 0; i < P; ++i) { int strength; …

Visual Studo 2010 RCを使っている。オンザフライでコンパイルエラーを表示してくれたり、インテリセンスが強化されていたりと、個人的には大変気に入っている。以前Visual Studio 2010 RCを使っていて、コンパイル時にIDEごと落ちるバグに会ってしまい、再…

現在LLVMがマイブームである。今日ふと思い立ってSSE組み込み関数が含まれたC++のコードがllvm-g++でどのように変換されるのか試してみた。元のC++ソースコードは以下の通り。 #include <nmmintrin.h> void add(float* x, float* y, float*z) { _mm_storeu_ps(z, _mm_add_</nmmintrin.h>…

巷ではこんな話題が流行っているらしいのだが、何か違和感を感じた。ようは再帰で書けという事なのだろうが、末尾再帰はループに展開できるはず。ただこの問題をといても面白くないので、もう一つの方の問題を解いてみる。この問題は2chにのどこかに書かれて…

Codeforcesという新進気鋭のプログラミングコンテストがあるらしいので参加してみることにした。Practiceをやってみたところ、ICPCとほぼ同じ形式だった。入出力を自分でコピペするのが面倒だったので自動化してみた。ぶっちゃけ前に作ったPKU用の自動チェッ…

趣味で書いているコードでハッシュを使った連想コンテナを使いたいのにTR1のunordered_mapが使えないという状況に遭遇した。仕方なくhash_mapで実装することにした。ところがVisual Studio 2008とgccで仕様が異なっており、コード互換性をとるために四苦八苦…

LLVMで遊ぼうと思い、ソースコードを落としてコンパイルを始めた。ところがインストラクション通りにやっているはずなのに上手くいかない。試行錯誤していくうちに何とかコンパイルすることができた。その時の手順を備忘録がてら書いていくことにする。 ソー…

ダイクストラ法の練習問題として適しています 入力がやや厄介かもしれません typedef complex<double> P; bool input(P& p) { double x, y; if (!(cin >> x >> y)) { return false; } p = P(x, y); return true; } int main() { vector<P> positions; P p; input(p); po</p></double>…

アップロードしました。テイルズオブグレイセスの主題歌です。あまり上手くないですがお聞き下さい。

環境変数にWindows SDKのincludeフォルダとlibフォルダを登録しておかないとコンパイルエラーが出まくるらしい。ということで↓こんな感じにしたらbootstrap.batは正常終了した。現在コンパイル中。 set INCLUDE=C:\Program Files\Microsoft SDKs\Windows\v7.…

隣り合う数字の差の絶対値を配列に格納 配列をソート 配列が1,2,...n-1となっているかどうかを確認 int main() { int n; while (cin >> n) { vector<int> values; for (int i = 0; i < n; ++i) { int value; cin >> value; values.push_back(value); } vector<int> sad</int></int>…

Range Coderは現在最も良く使われているエントロピー符号化の一つである。最近Range Coderを使う機会があり、ネット上のライブラリを使っていた。しばらく問題なく使えていたのだが、ある時を境にテストコードが通らなくなった。サイズの小さいテストで失敗…

文字列の練習に調度良いと思います 問題文で与えられたとおりに処理して終りです int main() { for (string line; cin >> line && line != "0"; ) { while (line.size() > 1) { int value = 0; const int length = line.size(); for (int i = 0; i < length;…

研究室で教授から研究室Wikiの動作が遅いので何とかして欲しいと頼まれた。研究室で使用しているWikiはPukiwikiで、主に研究室ゼミで使用する発表資料の共有等に使用されている。一番表示に時間がかかるのがこの発表資料を共有するページである。使用ポリシ…

画像URLの中に"\"が含まれていた場合、ディレクトリの区切りではなく、エスケープされた文字として認識してしまうらしい。原因が分かったのでGreaseMonkeyで自動的に置換するようにしてみた。下記がそのスクリプト。 // ==UserScript== // @name Repair Imag…

Twitter上ではすでにつぶやいたのですが、復習される方のために1/24に行われたJAG Winter Contest 2010の簡易解説を上げておきます。 A:最小になる≒極値≒微分したら0になる です。a,b,cについて偏微分した式=0とすると、3連立方程式になります。コレを解けば…

chokudai先生の最新記事を読んで思ったのだが、状態をノードと考えるというのは普通の人にできるのだろうか？ この状態=ノードという考え方はアルゴリズムではよく使われる比喩なのだが、普通の生活では全く出てこない概念だと思う。できれば将棋を例に上げ…

Windows7のエクスプローラーでflvやmp4などの動画ファイルのサムネイルを表示させたいと思い、ググッていろいろ試していたのだが、やっと表示させることができた。やり方は以下の通り。 自分で入れたコーデックを全てアンインストール サムネイルを表示させ…

カードの順番を逆にしてTrie木を作り、ノードの数を数えて終わりです メモリが足りなかったりTLEしたりで、何どもやり直しました int main() { const string firstLetters[] = {"A","2","3","4","5","6","7","8","9","10","J","Q","K"}; const string second…

フェリーには詰め込めるだけ詰め込めば良い 貪欲にシミュレーションするだけです int count(int l, const vector<int>& lengths) { int answer = 0; int sum = 0; for (vector<int>::const_iterator it = lengths.begin(); it != lengths.end(); ++it) { sum += *it; i</int></int>…