こんにちは。 前回は苦杯をなめたSRMですが、今回はHard以外通して青に昇格しました。Hardは剰余を取るのを忘れるという凡ミスでテストケースが通らず時間切れ。あと少し早く気付ければ・・・。 さて解説に行きたいと思いますが、今回の問題はMiddleが簡単なグラフ探索を用いる以外はEasyもHardも割とごり押しで解けました。では、実際に問題ごとに解説していきたいと思います。 Easy (256点) この問題は天 ...

こんにちは。 だいぶ昔から気になってはいたのですが、C++ STLではsortとpriority_queueで並び替えられる順序が違うのが気になっています。 sortもpriority_queueも並べ替え順序の初期値はstd::lessになっているはずなんですが、次のプログラムを実行すると、逆の並び順になります。 ソースコード #include <stdlib.h> #include <time.h> #include <queue> #include <vector> #include <algorithm> using namespace std; int main() { vector<int> v; priority_queue<int> que; srand((unsigned long)time(NULL)); for(int i=0; i<10; i++) { int x = rand() % 100; v.push_back(x); que.push(x); } std::sort(v.begin(), v.end()); for(int ...

こんにちは。 以前からずっとやろうと思っていてできていなかったTopCoderに先日はじめて参加してみました。事前に574回のを見ていったのですが、雰囲気楽勝そう？とか思ったら、本番全然できなくて泣きそうになりました。 自己分析してみると574回はグラフ探索系の問題が中心で僕が得意なのが多かったのですが、575回は深さ優先探索中心の問題でぱっと解法が思いつきませんでした。まだまだ精進が足りないようです ...

第5回の今回は「Numerical System」という問題です。いつものように参考ページは以下の通りです。 「ACM/ICPC国内予選突破の手引き」 「AOJの問題ページ」 この問題はm,c,x,iという文字をローマ数字のように使い、それでいて2-9の数字を各桁の数を表すのに使う表記法(MCXI記法)を扱う問題です。 方針は立てるまでもなくMCXI記法と普通の数字との間の変換を行えばよいということです。力 ...

第4回の今回も少し飛びまして「Get Many Persimmon Trees」という問題を解説したいと思います。参考ページは以下の通り。 「ACM/ICPC国内予選突破の手引き」 「AOJの問題ページ」 さてこの問題では次のような条件が与えられています。 W×Hのフィールドに柿の木 (Persimmon Tree) が何本か生えている そのフィールド内に大きさS×Tの領地がもらえることになった 柿の木の数が最大になるような領地の取り方が知りたい この問題も効率よくやろ ...

第3回はAOJにジャッジがないので少し飛びまして「When Can We Meet?」を解説したいと思います。いつものように参考ページは 「ACM/ICPC国内予選突破の手引き」 「AOJの問題ページ」 になります。 さてこの問題はどういう問題かといいますと、 ある会議を行うために複数人の人が集まれるもっともよい日を調整する 会議の構成メンバー数Nと必要最低出席者数Qが与えられる 会議は今日から100日後までに行われる とい ...

前回に引き続きACM/ICPC国内予選突破ページに紹介されている過去問を全力で解説します。参考ページは http://www.deqnotes.net/acmicpc/ になります。今回は第2回目の「Ohgas’ Fortune」という問題。僕はAOJでやっているのでAOJのリンクを貼っておきます。 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1135 この問題は利息の計算をシミュレーションする問題。注意するべきと思われるポイントは次の2つ。 問題文だと若干分かりづらいが、単利と複利が途中で入れ替わることはなく、どちら ...

どうもtatsyです。 GCJのQualification Roundが2週間後に迫ったということで、 http://www.deqnotes.net/acmicpc/ のページに書かれているACM/ICPC国内予選突破の手引きにある問題を僕なりの全力で解説してみたいと思います。 第1回の今回は「Hanafuda Shuffle」という問題です。 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1129 この問題は特定枚数与えられている数字が書かれたカードをシャッフルしたときに一番上のカードが何かを出力するプログラムを書く、と ...

さて、前回に引き続きましてColor Constancyのアルゴリズムです。前回の記事はこちらからどうぞ。 Color Constancy のアルゴリズム (第1回) 今回は後半の3つのアルゴリズム、 Rahmanのアルゴリズム 準同型フィルタを用いたアルゴリズム Faugerasのアルゴリズム を紹介したいと思います。それでは、レッツスタート！ Rahmanのアルゴリズム RahmanのアルゴリズムはMooreのアルゴリズムとほぼ同等の仮定に ...

本日は画像処理の中でも割と古典的？と思われるColor Constancyのアルゴリズムをいくつか紹介したいと思います。このアルゴリズムはEbnerの「Color Constancy」という本の7章に紹介されているもので、LandのRetinex理論をベースとしたものです。 紹介するアルゴリズムは Hornのアルゴリズム Blakeのアルゴリズム Mooreのアルゴリズム Rahmanのアルゴリズム 準同型フィル ...