Fleuryのアルゴリズム
[参考元] R・J・ウィルソン『グラフ理論入門』 近代科学社、2013、p.45.
オイラー・グラフとは
連結グラフで、すべての辺を含む閉じた小道があるグラフをオイラーグラフと呼ぶ。そのような小道をオイラー小道と呼ぶ。
連結グラフGがオイラーグラフであるための必要十分条件は、Gの点の次数がすべて偶数であること。
Fleuryのアルゴリズム
Fleuryのアルゴリズムはオイラー小道の構成法を与えるアルゴリズム。任意の点uから出発して、次の規則に従う限り自由に辺をたどる。
1.たどった辺を除去する。もし孤立点が生じたらそれも除去する。
2.どの段階でも、他にたどる辺がない場合以外は橋をたどらない。
橋とはカットセットが１本のときの辺のこと。
直感的には、ある連結グラフから１本の辺を除いたときに非連結グラフとなるような辺。
プログラム
オイラーグラフならオイラー小道を求める。オイラー小道は上で述べたFleuryのアルゴリズムを用いる。
橋となるかの判定は深さ優先探索でおこなう。
/* Fleuryのアルゴリズム */ #include <iostream> #include <vector> #include <algorithm> using namespace std; const int MAX_V = 20; vector<int> G[MAX_V]; bool visited[MAX_V]; int V, E; /* すべての頂点の次数が偶数ならばオイラーグラフ */ bool IsEulerianGraph() { for (int i = 0; i < V; i++) if (G[i].size() % 2 != 0) return false; return true; } /* 橋の判定の初期化*/ void InitBridge() { for (int i = 0; i < V; i++) visited[i] = false; } // 深さ優先探索で連結の確認 void dfs(int v, int s, int t) { visited[v] = true; if (v == t) swap(s, t); for (int i = 0; i < G[v].size(); i++) { if (v == s && G[v][i] == t) continue; if (!visited[G[v][i]]) dfs(G[v][i], s, t); } } /* uvが橋であればtrue */ bool IsBridge(int u, int v) { InitBridge(); dfs(u, u, v); for (int i = 0; i < V; i++) if (!visited[i]) return true; return false; } /* オイラー小道を返す */ vector<int> EulerCircuit() { vector<int> ret; int e = E, v = 0; ret.push_back(0); while (e > 0) { bool flag = false; for (int i = 0; i < G[v].size(); i++) { if (!IsBridge(v, G[v][i])) { flag = true; int u = G[v][i]; G[v].erase(G[v].begin() + i); for (int j = 0; j < G[u].size(); j++) if (G[u][j] == v) G[u].erase(G[u].begin() + j); v = u; e--; break; } } if (!flag) { int u = G[v][0]; G[v].erase(G[v].begin()); for (int i = 0; i < G[u].size(); i++) if (G[u][i] == v) G[u].erase(G[u].begin() + i); v = u; e--; } ret.push_back(v); } return ret; } int main() { cin >> V >> E; for (int i = 0; i < E; i++) { int s, t; cin >> s >> t; G[s].push_back(t); G[t].push_back(s); } if (!IsEulerianGraph()) cout << "オイラーグラフではありません" << endl; else { vector<int> trail = EulerCircuit(); for (int i = 0; i < trail.size(); i++) cout << trail[i] << " "; cout << endl; } return 0; }
TODO
簡単な場合のverifiedしかしていない。
橋の判定をもっとスマートに
入力のグラフを変形しているので修正
非不偏版エンドニム
輪講メモ。
[参考元]
- 作者: M.H.Albert,R.J.Nowakowski,D.Wolfe,川辺治之
- 出版社/メーカー: 共立出版
- 発売日: 2011/09/21
- メディア: 単行本
- クリック: 5回
- この商品を含むブログ (1件) を見る
非不偏版エンドニムはエンドニムの変形。
エンドニムとは、一列に並ぶ箱の山が与えられて、対局者はどちらか一方の端にある箱の山から好きな数だけ箱を取り除くことができる。
端にある箱の山が取り除かれたら、その隣にある山から箱を取り除くことができる。
最後の箱を取り除いた対局者の勝ち。
非不偏版エンドニムは、上のエンドニムに、左は左端の山から箱を取り除く、右は右端の箱の山から箱を取り除くという条件を付したもの。
左、右は対局者の取りうる選択肢が異なるので、対局者を区別するために呼ぶ。
入力形式
複数のデータセットの並びが入力として与える。入力の終わりはゼロひとつの行で示される。
各データセットは以下の通り。
１行目 箱の山の個数 n (整数)
２行目 左端から１番目の山の箱の個数 左端から２番目の山の箱の個数 ・・・ 左端からn番目の山の箱の個数
出力形式
入力データセットごとに与えられた初期局面の帰結類。帰結類とは次の４つの状態
・L 左必勝
・R 右必勝
・N 先手必勝
・P 後手必勝
#include <iostream> #include <climits> using namespace std; const int MX_SIZE = 1000; int inp[MX_SIZE]; int memo_l[MX_SIZE][MX_SIZE], memo_r[MX_SIZE][MX_SIZE]; int n; int right_aw(int l, int r); int left_wb(int l, int r); void init(); void init() { for (int i = 0; i < n; i++) cin >> inp[i]; for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) memo_l[i][j] = memo_r[i][j] = INT_MAX; } int right_aw(int l, int r) { if (memo_r[l][r] != INT_MAX) return memo_r[l][r]; int ret; if (r - l == 0) ret = inp[r]; else { if (inp[l] <= left_wb(l + 1, r)) ret = 0; else { ret = right_aw(l + 1, r) - left_wb(l + 1, r) + inp[l]; if (ret < 0) ret = 0; } } return memo_r[l][r] = ret; } int left_wb(int l, int r) { if (memo_l[l][r] != INT_MAX) return memo_l[l][r]; int ret; if (r - l == 0) ret = inp[r]; else { if (inp[r] <= right_aw(l, r - 1)) ret = 0; else { ret = left_wb(l, r - 1) - right_aw(l, r - 1) + inp[r]; if (ret < 0) ret = 0; } } return memo_l[l][r] = ret; } int main() { while (cin >> n, n) { int lw, rw; init(); if (n <= 3) { rw = right_aw(0, n - 1); lw = left_wb(0, n - 1); } else { rw = right_aw(1, n - 2); lw = left_wb(1, n - 2); } if (inp[0] <= lw && inp[n - 1] <= rw) cout << "N: 先手必勝" << endl; else if (inp[0] > lw && inp[n - 1] > rw) cout << "P: 後手必勝" << endl; else if (inp[0] > lw && inp[n - 1] <= rw) cout << "L: 左必勝" << endl; else if (inp[0] <= lw && inp[n - 1] > rw) cout << "R: 右必勝" << endl; else cout << "分からない" << endl; } return 0; }
CODEFORCES #182 Div2 C. Yaroslav and Sequence
(1)nが奇数の時
例1. n = 3の時、符号だけに着目すると
[1] +++++
[2] ++++-
[3] +++--
[4] ++---
[5] +----
[6] -----
操作で
(6)→(3)→(4)→(1)
(5)→(2)→(3)
と何回かの操作ですべての場合に対して符号を正にできる。
(2)nが偶数の時
(2-1)入力列の正の符号が奇数個の場合は(1)の時と同様に、何回かの操作ですべて場合に対して符号を正にできる。
(2-2)入力列の正の符号が偶数個の場合は、１つの符号が負で、残りの符号を正の列に変換できる。
#include <iostream> #include <algorithm> using namespace std; int main() { int n, sum, p, tmp, min_all; sum = p = 0; min_all = 10000; cin >> n; for (int i = 0; i < 2 * n - 1; i++) { cin >> tmp; if (tmp >= 0) p++; else tmp *= -1; sum += tmp; min_all = min(min_all, tmp); } if (n % 2 == 1 || (n % 2 == 0 && p % 2 == 1)) cout << sum << endl; else cout << sum - 2 * min_all << endl; return 0; }
AOJ 0081 A Symmetric Point
[問題]
AOJ 0081 「A Symmetric Point」
１つの直線と１つの点が与えられる。与えられた点と線対称な点を答える。
[参考元]
座標変換は５個。
1. 平行移動
2. 拡大・縮小
3. 回転
4. 鏡映
5. スキュー
P1を原点に平行移動する量をtとする。
直線P1-P2とx座標の正方向の角度をθとする。
1. 点Qをt平行移動
2. 点Qを-θ回転移動
3. 点Qをx軸に対して鏡映
4. 点Qをθ回転移動
5. 点Qを-t平行移動
#include <iostream> #include <iomanip> #include <cmath> using namespace std; // x軸方向にtx, y軸方向にtyだけ平行移動 void translation(double tx, double ty, double &x, double &y) { x += tx; y += ty; } // thetaだけ回転 void rotation(double theta, double &x, double &y) { double tx = x; double ty = y; x = cos(theta) * tx - sin(theta) * ty; y = sin(theta) * tx + cos(theta) * ty; } // x軸に関する鏡映 void x_reflection(double &x, double &y) { y *= -1; } int main() { double x1, y1, x2, y2, xq, yq; char ch; cout << setiosflags(ios::fixed) << setprecision(6); while (cin >> x1 >> ch >> y1 >> ch >> x2 >> ch >> y2 >> ch >> xq >> ch >> yq) { double theta = atan((y2 - y1) / (x2 - x1)); translation(-x1, -y1, xq, yq); rotation(-theta, xq, yq); x_reflection(xq, yq); rotation(theta, xq, yq); translation(x1, y1, xq, yq); cout << xq << " " << yq << endl; } }
openFrameworks in Ubuntu12.10
Ubuntu12.10 64bit上でopenFrameworksを使用してみる。
[2013年4月25日作成]
参考元： Beyond Interaction PDF版をCreative Commonsライセンスで配布開始!
本当にありがとうございます。
Code::Blocks IDEを使わないでターミナルとエディタ(Emacs24)のみでビルドしてみる。以下openFrameworksをOFと表記する。
OFはインストールされていることを前提。
インストール方法はOFのLinuxダウンロードセットアップガイドに詳しく書かれている。
1.どんなことが出来るのかを知るためにExampleのサンプルを全部実行。
Examplesを全部実行してくれるスクリプトの場所に移動$ cd of_v0.7.4_linux64_release $ ls addons changes.txt export license.md projectGenerator scripts apps examples libs other readme.txt $ cd scripts/linux $ ls archlinux cleanAllExamples.sh compileOF.sh debian removeFMOD.sh testAllExamples.sh buildAllExamples.sh codeblocks_wizard compilePG.sh fedora template ubuntu
・buildAllExamples.sh
of_v0.7.4_linux64_release/examples以下にあるサンプルプログラムをすべてコンパイルする。
・testAllExamples.sh
of_v0.7.4_linux64_release/examples以下になるサンプルプログラムをすべて実行する。コンパイルされていなければコンパイルして実行する。なので先にbuildAllExamples.shを実行してサンプルをすべてコンパイルしておくと待たずにすむ。
サンプルプログラムのコンパイルと実行
$ ./buildAllExamples.sh $ ./testAllExamples.sh
Escキーを押すとそれぞれのプログラムが停止する。いくつかのプログラムは、実行時に引数などが必要なためにエラーが出るが気にしない。
他のスクリプトは放置プレイ。
2. 新規プロジェクトを作成する
プロジェクトの作成$ pwd of_v0.7.4_linux64_release $ cd projectGenerator $ ./projectGenerator
プロジェクトジェネレーターが起動するので「Name」の所をクリック。
「testProject」というプロジェクト名を入力して「OK」。
右下の「GENERATE PROJECT」をクリック。
作成されたプロジェクトの場所
$ cd ../ $ pwd of_v0.7.4_linux64_release $ cd apps/myApps $ ls testProject $ cd testProject $ ls Makefile addons.make bin config.make obj src testProject.cbp testProject.workspace $ ls src main.cpp testApp.cpp testApp.h
プロジェクトジェネレータで作成されたプロジェクトはapps/myAppsの下に「testProject」という名前で作成される。
プロジェクトをいじる場合はsrcディレクトリ以下の「main.cpp」、「testApp.cpp」、「testApp.h」を編集する。
「main.cpp」ファイルを見るとウィンドウを生成して「testApp.cpp」を呼び出している。
ビルド（コンパイル）と実行
$ pwd
$ of_v0.7.4_linux64_release/apps/myApps/testProject
$ make
$ ./bin/testProject
Ubuntu12.10 64bit インストール後設定 (かなり適当)
参考元: Ubuntu 12.10をインストールした直後に行う設定 ＆ インストールするソフト
[デュアルディスプレイ]
システム設定→ディスプレイ→「複数のディスプレイをミラーする(M)」のチェックを外す→解像度の選択[HUDのショートカット無効化]
・AltキーでHUDが立ち上がってウ・ァィ
システム設定→キーボード→ショートカット→Launchers→「HUDを表示するキー」の右をクリック→Deleteキーを入力して「無効化」にする．
[外付けディスプレイを使用する（HHK）]
システム設定→キーボードレイアウト→右下の「＋」を選択→「英語（US）」を追加→「英語（US）」を選択して「＜を右に９０度回転したやつ」を選択して、「英語（US）」を「日本語」の上にする
・ノートパソコンのキーボードとHHKを切り替えるための設定
キーボードレイアウトのオプション→配列を変更するときに使用するキー→「両方のShiftキーを同時に押す」を選択
・ノートパソコン側のCtrlキーの位置の変更
キーボードレイアウトのオプション→Ctrlキーの位置→「CapsLockをCtrlとして扱う」を選択
[Dashのオンライン検索を使用しない]
システム設定→プライバシー→「オンライン検索結果を含める」をオフ→「アクティビティの記録」をオフ
[ディレクトリ名を日本語から英語に変更する]
$ env LANGUAGE=C LC_MESSAGES=C xdg-user-dirs-gtk-update
「Dont't ask me this again」を選択→「Update Names」を選択
[Google Chromeのインストール]
参考元
$ wget -q -O - https://dl-ssl.google.com/linux/linux_signing_key.pub | sudo apt-key add - $ sudo gedit /etc/apt/sources.list.d/google.list $ deb http://dl.google.com/linux/chrome/deb/ stable main $ sudo apt-get update $ sudo apt-get install google-chrome-stable
＊インストール後に「/etc/apt/sources.list.d/google-chrome.list」が作成されるので「/etc/apt/sources.list.d/google.list」を削除しなければいけない。google.listという名前で作成するより、
google-chrome.listが良いのでは、検証はしてない。
[Google Chrome上の設定]
Google Chromeの設定→設定
・ダウンロード→「ダウンロード保存先」の「変更」を選択して変更
・「ホームボタンを表示する」を選択→新しいタブ→「アドレス」を選択して「http://www.google.co.jp」と入力→OK
・「ブックマークバーを常に表示する」を選択
・コンテンツの設定→現在地の「すべてのサイトに対して自分の物理的な現在地の追跡を許可しない」を選択
・コンテンツの設定→メディアの「カメラやマイクへのアクセスをサイトに許可しない」を選択
[プロンプトを変更]
デフォルトのプロンプトPS1では階層が深くなるにつれて見えにくくなるので変更
./bashrcの「PS1=」右辺の「w」を「W」に変更。これによって、カレントディレクトリが絶対パス表示ではなく現在のディレクトリに変更される。
[色々削除]
Ubuntuソフトウェアセンター→インストール済み→削除するもの「連絡先、Empathy Internet Messaging, Firefoxウェブブラウザー, Firefox用のUbufox拡張機能, Gwibberソーシャルクライアント, ゲーム全部, Ubuntu One, Amazon」
$ sudo apt-get remove unity-lens-shopping # unity-lens-shoppingの削除 $ sudo apt-get remove ubuntuone-client python-ubuntuone-client python-ubuntuone-storageprotocol # ubuntuoneの削除
[Emacs24をインストール]
$ sudo apt-get install emacs24
[Gnome Terminalのプロフィル設定]
[ubuntu restricted extras]
$ sudo apt-get install ubuntu-restricted-extras
$ sudo add-apt-repository ppa:webupd8team/java $ sudo apt-get update $ sudo apt-get install oracle-java8-installer
[Topcoder Areanaをインストール]
TopCoderのホームページ→「O(n)」のタブをクリック→「LOAD COMPETITION ARENA」を選択してダウンロード
・Arenaの起動
javaws ContestAppletProd.jnlp
・Arenaの設定
参考元: 闇ゼミ::TopCoder
[LaTeXのインストール]
$ sudo apt-get install texlive-lang-cjk $ sudo apt-get install xdvik-ja // txfonts.styを使用するため $ sudo apt-get install texlive-fonts-recommended
[openFrameworksのインストール]
openFrameworks→linuxダウンロード「code::blocks(64bit)」を選択→
$ tar -xzvf of_v0.7.4_linux64_release.tar.gz $ cd $HOME/of_v0.7.4_linux64_release/scripts/linux/ubuntu $ sudo ./install_codeblocks.sh $ sudo ./install_dependencies.sh $ sudo ./install_codecs.sh
[OpenCVのインストール]
$ sudo apt-get install libopencv-dev
＊もしエラーが出る場合は一度再起動
・画像処理用サンプル画像
標準画像／サンプルデータ
・コンパイル
$ g++ -o $name $name.cc `pkg-config opencv --cflags --libs`
[Inkscapeインストール]
$ sudo apt-get install inkscape
[VLCインストール]
$ sudo apt-get install vlc
市販のDVDやレンタルDVDが再生されない時は次のコマンドを実行してみてください。
参考元： How To Enable DVD Playback In Ubuntu 12.10 Quantal Quetzal
#libdvdread4のインストール（たぶん入っている） $ sudo apt-get install libdvdread4 # libdvdread4の起動 $ sudo /usr/share/doc/libdvdread4/install-css.sh
[Qt]
$ sudo apt-get install qt-sdk
[デフォルトの句読点の変更 mozcの導入]
「、 。」から「， ．」にデフォルトでの変更．
「わからん」さんのホームページを参考
$ sudo apt-get install mozc-server mozc-utils-gui ibus-mozc
再起動．
$ ibus-setup &
「インプットメソッド」→「インプットメソッドの選択」→「日本語」→「Mozc」を選択→インプットメソッドの「日本語ーMozc」を選択→「上へ(U)」で一番上に→「日本語ーMozc」を選択→「設定」を選択→句読点を変更
・Emacsにmozc
$ sudo apt-get install emacs-mozc emacs-mozc-bin
・ショートカットキーの取り消し
$ ibus-setup &
一般→キーボードショートカット→「切り替え」の「...」をクリック→「Alt」とモディファイされているキーボードショットカットを選択して削除
一般→キーボードショットカット→「次のインプットメソッド:」を削除
Emacsのinit.elに次を追加
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;; ;; mozc ;; ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;; 最低限の設定 (require 'mozc) ;; or (load-file "/path/to/mozc.el") (set-language-environment "Japanese") (setq default-input-method "japanese-mozc") ;; GUIの候補選択ウィンドウをカーソルの直下にぶら下げる (setq mozc-candidate-style 'overlay) ;; key-chord.elとの併用 (require 'key-chord) (key-chord-define mozc-mode-map "aa" "aa")
.bashrcに次を追加
alias emacs='XMODIFIERS=@im=none emacs'
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
- -
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
[マルチブート環境や仮想マシン上のWindowsの時計が狂うのを防ぐ]
$ sudo sed -i 's/UTC=yes/UTC=no/g' /etc/default/rcS
[WindowsとUbuntuをデュアルブート設定の時、デフォルトでWindowsを起動]
PCを起動時のGrubの設定画面で、上から数えてWindowsが何番目にあるかをメモ。
仮に、上からN番目とする。
「/etc/default/grub」ファイルを変更する。
GRUB_DEFAULT=0
の０をN-1に変更して保存。
GRUB_DEFAULT=N-1
設定を更新するために次のコマンドを打つ。
$ sudo update-grub
SRM575 Div2 250
レーティングが760->683と下げが止まらない。
次回頑張ります。
[２５０の問題文]
「与えられたint型の配列から２つの要素を入れ替えて、いくつの異なった配列を作ることができるか。」
[方針]
int型配列の要素を２つ入れ替えて文字列にしてmapで判定。
[ソースコード]
#include <string> #include <vector> #include <map> #include <sstream> #include <algorithm> using namespace std; class TheSwapsDivTwo { string toString(vector<int> num) { stringstream ss; for (int i = 0; i < num.size() - 1; i++) ss << num[i] << " "; ss << num[num.size() - 1]; return ss.str(); } public: int find(vector <int> sequence) { map<string, bool> m; int cnt = 0; for (int i = 0; i < sequence.size(); i++) { for (int j = i + 1; j < sequence.size(); j++) { vector<int> ch = sequence; swap(ch[i], ch[j]); string s = toString(ch); if (m.count(s) == 0) { cnt++; m[s] = true; } } } return cnt; } };
setを使えば簡単にできるみたい。
set<vector<int>> s;
コンテナを勉強します。
