Google Kickstart 2020 Round 1B - Wandering Robot の解説 - minus9d's diary
Google Kickstart 2020 Round 1Bの最後の問題、Wandering Robot についてやっと理解できたので解説を書きます。 問題概要 W*Hの盤面が与えられる。盤面には ある矩形１つ分の穴が空いている。ロボットは左上の(1, 1)を出発し、等確率で右か下に移動する。ただし盤面の右端に到達した場合は必ず下に、盤面の下端に到達した場合は必ず右に移動する。ロボットが穴に落ちずに盤面の右下(W, H)に到着できる確率を求めよ。 着想 例えば以下の盤面を考えます。■は穴を表します。 ★に着目してください。ロボットが右下に到達するためには、必ず★のどれか一つを通らなければいけません。かつ、★を2つ以上通ることはできません。なので、各★を通る確率を個別に求め、その和をとれば、答が求まりそうです。 各セルを通る確率は、以下のように求められます。さきほどの盤面の場合、3つの★の確
Pythonの並列処理・並行処理のための標準モジュールの比較 - minus9d's diary
Pythonで並列処理・並行処理を提供する標準モジュールは数多くあり、初めてだと違いを理解するのは困難です。この記事では、それぞれの違いについて調べました。 threadモジュール(Python 2), _threadモジュール(Python 3) かつてPython 2にはthreadモジュールという複数のスレッドを扱うためのモジュールが存在していましたが、Python 3でdeprecated扱いになりました。一応_threadモジュールという名前で残っています。公式でも述べられているように、一般には、thread/_threadモジュールではなく、より高レベルなthreadingモジュールの使用が推奨されるようです。 threadingモジュール threadingモジュールは、先述の通り、複数のスレッドを扱うためのモジュールです。thread/_threadモジュールより高レベルと
mapでキーの有無を調べるには、find()よりcount()が便利 - minus9d's diary
mapコンテナ(mとする)でキーの有無を調べる場合、今まではメンバ関数のm.find()を呼ぶ方法を使っていた。m.find()を使う方法では、「m.find()の戻り値がm.end()に等しければキーが存在しない、そうでなければキーが存在する」としてキーの有無を判別していた。 しかし、m.count()を使った方がより直感的である。m.count()を使う方法では、「m.count()の戻り値が0に等しければキーが存在しない、1に等しければキーが存在する」という簡単仕様なので分かりやすい。 以下のコードでは、find()を使う場合とcount()を使う場合とを比較した。どちらも結果は同じである。 #include <iostream> #include <map> using namespace std; bool has_key_using_find(map<int, string>
C++11で、chronoライブラリを使って時間を計測する - minus9d's diary
C++11で新しく加わったchronoライブラリを使うと、簡単に経過時間が計測できる。もう環境依存のコードを書かなくてよくなるなら嬉しい。 サンプルコードは以下。シンプルなのですぐわかると思う。 #include <iostream> #include <chrono> int main() { auto start = std::chrono::system_clock::now(); // 重い処理 long long j = 0; for(int i = 1; i <= 100000000; ++i) { j += i; } auto end = std::chrono::system_clock::now(); // 経過時間をミリ秒単位で表示 auto diff = end - start; std::cout << "elapsed time = " << std::chron
今すぐに使いたいC++11の新機能 - minus9d's diary
最近導入の敷居が下がってきたC++11に興味が湧いてきた。C++11の新機能を眺めてみると、正直半分くらいの項目はよく理解できないのだが、いくつかの項目は"Better C++"としていますぐにでも使いたいものであった。今回は導入の効果が高そうなC++11の新機能を紹介する。 autoによる型推論 C++03以前では、必ず変数の宣言時に型を指定しなければいけなかった。そのため、例えばSTLでイテレーションを回すときには以下のように長ったらしい書き方をしなければいけなかった。 map<int, int> m; ... for(map<int, int>::iterator it = m.begin(); it != m.end(); ++it) { ... } ここでmの型をmapに変更すると、それにともなってイテレーションの型もmap::iteratorに変更しなければならず大変面倒くさか
カラー画像を3色で分離、さらに色を入れ替えた画像を作成 - minus9d's diary
コード 以下の通り。 void bgr_split(){ cv::Mat src = cv::imread("./input/baboon.jpg", 1); vector<cv::Mat> planes; // 3つのチャネルB, G, Rに分離 (OpenCVではデフォルトでB, G, Rの順) cv::split(src, planes); // 保存 cv::imwrite("./output/b.jpg", planes[0]); cv::imwrite("./output/g.jpg", planes[1]); cv::imwrite("./output/r.jpg", planes[2]); // チャネルを入れ替えた画像を作成し保存 cv::Mat dst; vector<cv::Mat> color_shuffle; color_shuffle.push_back( pl
gprofを使いこなす - minus9d's diary
C/C++のコードの速度を改善するときに有効な方法は、処理時間を多く消費する関数を見極めて、その関数を改善することである。どの関数が(1)どれだけ処理時間を消費するか、(2)何度呼ばれているか、(3)どの関数を呼んでいる/どの関数に呼ばれているか、などを測定する行為をプロファイリングといい、その手助けをするツールをプロファイラと呼ぶ。今回はC/C++のプロファイラとして有名なgprofの使い方を紹介する。 プログラムの例 GNUプロファイラーによるコード処理速度の向上 のコードを参考にして作成した以下のコードをgprofでプロファイリングしてみよう。main()はa()とb()を100000回呼ぶ。b()はa()の約4倍時間を消費する。またmain()自身も、a()とb()を呼び出してその結果を待つ以外に、a()の約1/3の時間を消費する。 // main.cpp #include <cs
cv::Mat使用時の画素へのアクセス方法 - minus9d's diary
OpenCVのcv::Matクラスに格納された画像データの各画素にアクセスする方法を、以下の2種類ご紹介する。 atメソッドを用いる方法 dataメソッドを用いる方法 画素にアクセスする回数が少ないのならatメソッド、全画素に順番に読み出すなど頻繁に画素にアクセスするのならdataメソッドを用いる方法が良いと思う。 atメソッドを用いる場合 画素をピンポイントで読んだり書いたりするには、atメソッドを使う。ただし、atメソッドを使うには、Matクラスが1画素あたり何バイトからなるのかを事前に知っていないといけない。 例：白黒画像の場合 1画素の濃淡は1バイト(0〜255)で表されるので、以下のようになる。 cv::Mat img = cv::imread("cat.jpg"); int intensity = img.at<unsigned char>(y, x); //X座標がx, Y座
PCA(Principal Component Analysis)を具体的に計算する - minus9d's diary
(2013/6/18修正) PCAの計算方法を天下り的に説明します。専門家ではないので誤りが含まれる可能性があることをあらかじめご了承ください。データの例はExample of Principal Component Analysis (PCA).mp4 - YouTubeで使われているものをそのまま流用しています。というか、このあやしい説明を読むよりかこの動画を見た方がいいかもしれません。 PCAの目的 ベクトル基底を変換することにより、できるだけ情報を失うことなく次元を削減すること。 データの例 2つの独立変数X, Yを持つ10組のデータがあるとする。 X Y 1.4 1.65 1.6 1.975 -1.4 -1.775 -2.0 -2.525 -3.0 -3.95 2.4 3.075 1.5 2.025 2.3 2.75 -3.2 -4.05 -4.1 -4.85 プロットするとこん
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
