画像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>…

何日目にどの問題を解いているかというDPです この解答ではダイクストラ法チックに解いています int B[512]; int A[512]; int Bs[512][512]; int As[512][512]; int main() { int M, P; cin >> M >> P; for (int i = 0; i < P; ++i) { cin >> B[i] >> A[i]; …

ソートして貪欲にシミュレーションすれば良いようです struct Cow { ll t; ll d; bool operator<(const Cow& rh) const { return d * rh.t > rh.d * t; } }; int main() { int N; cin >> N; vector<Cow> cows; for (int i = 0; i < N; ++i) { Cow cow; cin >> cow</cow>…

最長部分繰り返し文字列という問題だと思います Spaghetti Sourceのライブラリをお借りしました #define SETNUM(rank, i,s) \ NUM[i] = make_pair(make_pair(rank[i], i+s

直接解をを求めようとすると難しいです ある値が与えられたとき、その値が解として正しいかどうかは線形時間で求めることができます コレを使って解を二分探索で求めることができます int pickupGreedy(const vector<int>& ds, int length) { int result = 0; int</int>…

k-th shortest pathという有名問題です Spaghetti Sourceのライブラリを使用しています static const int INF = INT_MAX / 2; #define REP(i,n) for(int i=0;i<(int)n;++i) #define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i) #def…

サイズが大きくないためDPで解けます 有るか無いかのビットフラグをキーにする典型的なDPです bool isValid(int value, int N) { bool last = false; for (int shift = 0; shift < N; ++shift) { if (last && (value & (1 << shift)) != 0) { return false; …

ハフマン木を作る要領で解けるようです 分割するのではなく、全部バラけた状態からくっつける方向で考えると解けるようです int main() { int N; cin >> N; priority_queue<ll, vector<ll>, greater<ll> > ls; for (int i = 0; i < N; ++i) { ll l; cin >> l; ls.push(l); } ll </ll></ll,>…

うまい解法が思いつかなかったためテーブル埋込みを使いました 2^20個を1セットとしてテーブルに持たせ、端数の部分を全探索しました int numofbits5(ulong bits) { bits = (bits & 0x55555555) + (bits >> 1 & 0x55555555); bits = (bits & 0x33333333) + (…

主人公(?)の位置と正方形の一辺を表すベクトルで全探索です N int main() { static char farm[128][128]; static char firstLine[128]; gets(firstLine); const int N = atoi(firstLine); for (int x = 0; x < N; ++x) { gets(farm[x]); } int answer = 0; f…

スタックを使って高さを管理していけば解けるようです int main() { vector<int> stk; int N; cin >> N; ll sum = 0; for (int i = 0; i < N; ++i) { int h; cin >> h; while (!stk.empty() && stk.back() <= h) { stk.pop_back(); } sum += stk.size(); stk.push</int>…

各桁のビットに着目して解いていく 各桁ごとにビットが立つ確率を求め、それらを2^i倍して足していけば良い 答えが合わずに困ってたら、1〜nまでで考えていたのが原因だった。本当は0〜n-1 G++で提出したらWA、C++だとACだった。やっぱり納得が行かない。 in…

答えの値で二分探索を行った 初めkの値の意味を取り違えており、毎ターンk+1乾燥させるようにしていた。WA 入力の直後に--kしたら、0割りでRE k==1の場合は自然乾燥させる場合と等価になるので、max_elementを返せば良い static int a[128 * 1024]; bool che…

問題文を見て目を疑った どう切っても良いので、とりあえずスライスしてみた コンパイラにG++を選択するとWAでC++だとPE or ACという、ちょっと納得の行かない結果になった %.15lfだとOLE、%.10lfだとPE、%.9lfだとACというのも納得が行かなかった int main(…

Twitter上で@tozangezanさんがつぶやいていた問題 サイズが500000なのでO(N log N)のアルゴリズムまでなら通る可能性が高い この回答では最初に500000まで求めてから、最後に入力を処理している #include <iostream> #include <set> using namespace std; static int a[5000</set></iostream>…

丁寧にシミュレーションをすれば良い 左右に玉が転がる部分の判定ルーチンは使いまわせるように関数化した bool check(const string& s, int pos, int dir) { for (; 0 <= pos && pos < s.size(); pos += dir) { if (s[pos] == '.') { return true; } else i…

現在競技プログラミング界隈でプチ炎上中のこの問題を解いてみた。解答に20分。途中バグに悩まされて大幅に時間をロスした。正直修行が足りないと思う。 この問題を解いていて感じたことは、この会社は基本レベルがクリアできている人が欲しいんだろうなぁと…

自分の使用しているAlienware M15xの新BIOSが公開されたので早速アップデートしら酷い事になった。まずBIOSのFlash書き換えソフトがうまく動作しない。1回目に起動したときは新しいBIOSをFlashしています的な表示のまま固まってしまった。数十分待っても反応…

http://acm.pku.edu.cn/JudgeOnline/problem?id=3093 DP あかかじめ値段の昇順にソートしておく 安い店から順に辿っていき、買うか買わないかで分岐する 他の店で買えなくなるまで買うという条件を満たすため、自分が買わなかったマリゲータのうち最も安い物…

http://acm.pku.edu.cn/JudgeOnline/problem?id=3088 DP解法 やり方が何通りかあるらしい ある押すボタンの集合について、それらのボタンを使ったシーケンスが何通り作れるかを計算していく 最後に全てのパターンを足して出力 ll solve(int B) { static ll d…

http://acm.pku.edu.cn/JudgeOnline/problem?id=3087 データサイズた小さいため単純にシミュレーションをするだけで間に合う int main() { int N; cin >> N; for (int testCase = 1; testCase <= N; ++testCase) { int C; cin >> C; int permutation[256]; f…

http://acm.pku.edu.cn/JudgeOnline/problem?id=2386 典型的な幅優先探索 int main() { int N, M; cin >> N >> M; static bool wall[128][128]; memset(wall, -1, sizeof(wall)); for (int y = 1; y <= N; ++y) { for (int x = 1; x <= M; ++x) { char c; ci…

ハードディスクを漁っていたらLinear Predictive Coding(線形予測符号)のJava実装が見つかったので公開してみる。 public class LinearPrediction { public double[] burg(double[] y, int P) { final int ly = y.length; final double[] f = Arrays.copyOf(…