Searching in the dash

Ubuntu13.04に基づいて話をします．

Ubuntuに新しく追加された機能の１つにDashという検索システムがあります．
UbuntuTips/Desktop/HowToUseUnity - Ubuntu Japanese Wiki
Dashで検索する際の注意について話します．

おおまかに言うとDashで検索したキーワードが外部に送信されるということです．
「システム設定」→「詳細」→「Legal Notice」にこの事が書かれています．
この機能の是非は述べませんが，私が問題と思っているのは「Legal Notice」が日本語で書かれていない所です．

Ubuntu日本語フォーラム(Ubuntu日本語フォーラム / Searching in the dash)に投稿したのですが返信がなかったので，
日本語訳(2013年3月20日に翻訳)を下に記載します．
英語は苦手なので間違っている箇所があるかもしれませんので参考程度に見てください．
問題があれば削除しますので連絡ください．

・オプトアウト[拒否]の仕方
「システム設定」→「プライバシー」→「Dashで検索するとき：オンラインの検索結果を含める」をオフにする．

Searching in the dash - Legal notice
ダッシュによる検索　ー　法定通知

This search function is provided to you by Canonical Group Limited (Canonical).
この検索機能はカノニカルグループリミテッドから提供されています。

This legal notice applies to searching in the dash and incorporates
the terms of Canonical's legal notice (and privacy policy).
この法定通知はダッシュによる検索に適用され、カノニカル法定通知の用語
（そしてプライバシーポリシー）に取り入れられます。

Collection and use of data
データの収集と利用

When you enter a search term into the dash Ubuntu will search
your Ubuntu computer and will record the search terms locally.
検索ワードをダッシュに入力したとき、UbuntuはあなたのUbuntuマシンから
検索をしてローカルに検索ワードを保存します。

Unless you have opted out (see the “Online Search” section below),
we will also send your keystrokes as a search term to productsearch.ubuntu.com
and selected third parties so that we may complement
your search results with online search results from such third
parties including: Facebook, Twitter, BBC and Amazon.
もしあなたがオプトアウト[拒否]しない限り（下にある「オンライン検索」の章を見てください）、私たちはあなたのキーストロークも検索ワードとしてproductsearch.ubuntu.com
と選択したサードパーティー[第三者団体]に送信します。
なぜならあなたの検索結果をサードパーティ（Facebook, Twitter, BBC, Amazon）
からのオンライン結果を用いて補完できるようにです。

Canonical and these selected third parties will collect your search terms
and use them to provide you with search results while using Ubuntu.
カノニカルと選択したサードパーティはUbuntuを使用してあなたの検索ワードを収集して、
あなたに検索結果を提供するために検索ワードを使用します。

By searching in the dash you consent to:
ダッシュによる検索を使用に対してのあなたの同意：

・the collection and use of your search terms and IP address in this way; and
・あなたの検索ワードとIPアドレスのこのような収集と使用、そして

・the storage of your search terms and IP address
by Canonical and such selected third parties (if applicable).
・あなたの検索ワードとIPアドレスをカノニカルと選択したサードパーティへ保管（可能ならば）。

Canonical will only use your search terms and IP address in accordance
with this legal notice and our privacy policy.
カノニカルはあなたの検索ワードとIPアドレスをこの法定通知とカノニカルのプライバシーポリシー
にのっとてのみ使用します。

Please see our privacy policy for further information
about how Canonical protects your personal information.
私たちのプライバシーポリシーに、カノニカルがあなたの個人情報をどのように守るか
についての詳しい情報が書かれています。どうぞご覧ください。

For information on how our selected third parties may use
your information, please see their privacy policies.
どのように選択したサードパーティがあなたの情報を扱うかについての情報は、
それぞれのプライバシーポリシーをご覧ください。

Online Search
オンライン検索

You may restrict your dash so that we don’t send searches to third parties
and you don't receive online search results.
あなたは次のことを制限することができます。私たちが検索をサードパーティに
送信すること、そしてあなたがオンライン検索結果を受け取らないこと。

To do this go to the Privacy panel and toggle the
'Include online search results’option to off.
そのようにするために、プライバシーパネルの「オンライン検索結果を含める」
のオプションをオフにしてください。

The Privacy panel can be found in your System Settings or via a dash search.
プライバシーパネルはあなたのシステム設定またはダッシュの検索によって
見つけることができます。

For a current list of our selected third parties,
please see www.ubuntu.com/privacypolicy/thirdparties.
現在、私たちが選択したサードパーティのリストは次のURLをご覧ください。
www.ubuntu.com/privacypolicy/thirdparties.

Changes
変更

Although most changes are likely to be minor,
Canonical may change this legal notice from time to time,
and at Canonical's sole discretion.
大部分の変更がマイナーになりそうであるが、
カノニカルの自由裁量によって、
カノニカルはこの法定通知を随時変更する。

Please check this page from time to time for any changes
to this legal notice as we will not be able to notify you directly.
私たちは直接お知らすることが出来ないので、この法定通知でどんな変更
も時々お調べください。

How to contact us
私たちへの連絡方法

Please submit any questions or comments about searching in the dash
or this legal notice by contacting us at the following address:
ダッシュによる検索についてや違法な通知に対してのどんな意見や疑問でも
私たちにご連絡ください。
連絡先は次のとおりです：

Canonical Group Ltd, 5th Floor, Blue Fin Building,
110 Southwark Street, London, England, SE1 0SU.

bwm-ng

bwn-ng(Brandwidth Monitor NG(Next Generation))コマンド

説明

ディスクやネットワークの帯域幅をリアルタイムに表示．
軽い，インターフェースの制限が無い．

インストール方法(in Uubuntu)

$ sudo apt-get install bwm-ng

使用方法

$ bwm-ng          # ネットワークIOを表示
$ bwm-ng -i disk  # ディスクIOを表示

起動時に "h" を入力するとヘルプ表示．
最大，平均，合計，更新時間の変更などが表示される．

Ubuntu 14.04.3 LTS 64bit インストール後設定 (かなり適当．依存関係がぐちゃぐちゃかも)

・2015年9月10日にUbuntu12.10から14.04.3 LTSに変更
QtかOpenCVかVLCを入れると再起動後に画面が黒くなる．（原因が分からないので教えてくださるとうれしいです）

参考元: Ubuntu 12.10をインストールした直後に行う設定 ＆ インストールするソフト

[デュアルディスプレイ]

システム設定→ディスプレイ→「複数のディスプレイをミラーする(M)」のチェックを外す→解像度の選択

[HUDのショートカット無効化]

・AltキーでHUDが立ち上がって嫌だ
システム設定→キーボード→ショートカット→Launchers→「HUDを表示するキー」の右をクリック→Deleteキーを入力して「無効化」にする．

[外付けキーボード（HHK）とmozcを使用する]

参考元：Symfowareについての考察blog
ibus-mozcをインストール

$ sudo apt-get install ibus-mozc

再起動→システム設定→「テキスト入力」→「+」をクリックして「日本語（Mozc）」と「英語（US）」を追加．ただし、日本語キーボードの場合は「英語（US）」の代わりに「日本語」を追加．→「次のソースへ切り替え:」をクリックしてキーバインドを入力（キーを押すと割り当てられる）．自分の場合は「Ctrl+Space」→「日本語（Mozc）」をクリックして次の図にある工具をクリック

「キー設定の選択」の「編集...」をクリック→「入力キー」で「Henkan」となってる行をクリック→左下にある「編集」をクリックして「選択されたエントリーを削除」をクリック．これをすべての「Henkan」の行にする．

[ノートパソコン側のCtrlキーの位置の変更]

キーボードレイアウトのオプション→Ctrlキーの位置→「CapsLockをCtrlとして扱う」を選択

Ubuntu13.10にアップデートしたら上記の方法が使えなくなったので追記．

# Ubuntuのバージョン確認方法．
$ lsb_release -a

13.10ならば次の操作を実行する．
参考元: オープンソース試行錯誤

# gnome-tweak-toolのインストール
$ sodo apt-get install gnome-tweak-tool
# gnome-tweak-toolの実行
$ gnome-tweak-tool &

「Typing」→「Ctrlキーの位置」→「Caps LockをCtrlとして扱う」
再起動をする（tweakのメニューが透過になるバグがあるが一応変換はできる）.

他の方法（何かおかしいので非推奨）．
参考元：Ubuntu13.10でcapslockをctrlへ変更する

$ xmodmap -pke > ".xmodmap"

.xmodmapを編集する。

//　次を
keycode  37 = Control_L	NoSymbol Control_L
keycode  66 = Eisu_toggle Caps_Lock Eisu_toggle Caps_Lock
//　次に変更
keycode 37 = Caps_Lock NoSymbol Caps_Lock
keycode 66 = Control_L NoSymbol Control_L

// 最後の行に次を追加
clear Lock
add Control = Control_L 

次のコマンドを実行。

xmodmap .xmodmap

[Dashのオンライン検索を使用しない]

システム設定→プライバシー→「オンライン検索結果を含める」をオフ→「アクティビティの記録」をオフ

13.10からは次のように変更。
システム設定→セキュリティとプライバシー→検索→「オンラインの検索結果を含める」をオフ

[ディレクトリ名を日本語から英語に変更する]

$ env LANGUAGE=C LC_MESSAGES=C xdg-user-dirs-gtk-update

「Dont't ask me this again」を選択→「Update Names」を選択

[Google Chromeのインストール]

13.10からは次のコマンドを実行する。

sudo apt-get install chromium-browser

13.10以前は次を実行する。
参考元

$ 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
・「ブックマークバーを常に表示する」を選択
・コンテンツの設定→現在地の「すべてのサイトに対して自分の物理的な現在地の追跡を許可しない」を選択
・コンテンツの設定→メディアの「カメラやマイクへのアクセスをサイトに許可しない」を選択
・ブックマークバーにあるアプリアイコンを消す　ブックマークバーで右クリック→「アプリのショートカットを表示」をクリック

・「Weblioポップアップ英和辞典」を入れる（Chrome上で英単語をCtrlを押しながらマウスオーバすると日本語訳がでる）→「設定」をクリック→「拡張機能」をクリック→「Chrome ウェブストアを閲覧」をクリック→左上の検索バーで「Weblio」と入リョウク→「Weblioポップアップ英和辞典」の右の「+CHROMEに追加」をクリック→拡張機能のところに戻り「オプション」をクリック→「英単語にマウスカーソルをあわせ、[Ctrl]キーを押してポップアップ *1」をチェックして下にある「保存」をクリック

[Google ChromeのFlashプラグインのインストール]

Chromeで「chrome://flash/」を検索するとflashがインストールされていないと出たのでflashをインストール．
参考元

$ sudo apt-get install pepperflashplugin-nonfree

[プロンプトを変更]

デフォルトのプロンプト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

・markdown-modeを使用する
参考元：emacs に markdown-mode をインストールする-どせいけいさんき
Emacs上で「C-c C-c p」と入力するとブラウザ上に表示される．このとき，markdownがtextからhtmlに変換している．

$ sudo apt-get install emacs-goodies-el markdown

また，.emacs.d/init.el に次を追加

(setq auto-mode-alist 
	(cons '("\\.mk?d$" . markdown-mode) auto-mode-alist))
(add-hook 'markdown-mode-hook 'flyspell-mode)

・ispellの設定
参考元：ispell で No word lists can be found for the language "ja_JP" - mooz deceives you

$ sudo apt-get install aspell-en
$ echo "lang en_US" > ~/.aspell.conf

[Gnome Terminalのプロフィル設定]

[ubuntu restricted extras]

$ sudo apt-get install ubuntu-restricted-extras

[Oracle Javaをインストール]

$ sudo add-apt-repository ppa:webupd8team/java
$ sudo apt-get update
$ sudo apt-get install oracle-java9-installer

[Topcoder Areanaをインストール]

TopCoderのホームページ→「O(n)」のタブをクリック→「LOAD COMPETITION ARENA」を選択してダウンロード

・Arenaの起動

javaws ContestAppletProd.jnlp

・Arenaの設定
参考元: 闇ゼミ::TopCoder

・フォントはデフォルトよりも「Arial」の方が見やすいので変更
「Options」→「Setup user preferences」→「Problems/Messages」→「Font」と「Fixed Width Font」を「Arial」に変更．「Size」を「14」に変更．

[gnuplotのインストール]

$ sudo apt-get install gnuplot
// Terminal type set to Unknownと表示されてplot出来ないので
// gnuplot-x11をインストール
$ sudo apt-get install gnuplot-x11

[LaTeXのインストール]

$ sudo apt-get install texlive-lang-cjk
$ sudo apt-get install xdvik-ja
// txfonts.styを使用するため
$ sudo apt-get install texlive-fonts-recommended

[Boostのインストール]

$ sudo apt-get install libboost-dev

[Ruby/Tk]

$ sudo apt-get install libtcltk-ruby

[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`

[Ipeインストール]

図などの描画ソフト（慣れると使いやすい）．
Ipe(software) Wiki

$ sudo apt-get install ipe

[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

[R言語]

$ sudo apt-get install r-base

[Python3]

UbuntuにはPythonとPython3がデフォルトで入っている．
実行するときやモジュールをインストールするときにはどれを選択するのか注意．

$ sudo apt-get install python3-scipy # 高水準の科学技術計算
$ sudo apt-get install python3-numpy # NumPy \subseteq SciPy
$ sudo apt-get install ipython3 # 対話的に実行するためのシェル（デフォルトよりも強力）

[GLPK（GNU Linear Programming Kit）]

$ sudo apt-get install glpk-doc glpk-utils

ただし，C言語やC++言語の中からライブラリ（glpk.h）として呼び出すためには次をインストールする必要がある．

$ sudo apt-get install libglpk-dev

ライブラリのドキュメントはglpk.pdf．場所はfindコマンドで次のように探すと良いかも．

$ find / -name glpk.pdf 2>/dev/null

[Gurobi Optimization（2015年9月2日）]

Gurobiは数理最適化ソルバー．
　・日本語による説明：Gurobi 計算サーバ | 製品情報 | 株式会社オクトーバー・スカイ
　・参考図書：あたらしい数理最適化: Python言語とGurobiで解く
　・インストールの参考元：Python + Gurobi による科学技術計算環境の構築
　・インストールの参考元：Ubuntu 14.10 に gurobi 6.0.0 をインストールする
アカデミックライセンスとして使用．

1. GUROBIの右上にある「Register」でアカウント作成
2.「Account Type:」の「Academic」を選択 → *が付いている箇所を入力して「Access Now」をクリック
3. 2番で登録したメールを確認 → リンクをクリック　→　パスワードを設定　→　右上にある「Login」からログイン
4. 右上にある「Get Gurobi」をクリック　→　「Gurobi Optimizer」をクリック　→　「README」で「Linux 64」を選択して「Download」をクリック
5. gurobix.x.x_linux64.tar.gzをダウンロードしたディレクトリにいく．

$ tar -xzvf gurobix.x.x_linux64.tar.gz
$ cd gurobixxx/linux64

quickstart_linux.pdfか「quickstart_linux/index.html」に従ってインストール（後者で進む）．
6. 「Software Installation Guide」をクリック　→　「/opt」に「gurobixxx」を移動

$ sudo mv gurobixxx /opt

7, 「.bashrc」ファイルに次を追加して再起動．一行目の「/gurobi600」は自分の場合に変更

export GUROBI_HOME="/opt/gurobi600/linux64"
export PATH="${PATH}:${GUROBI_HOME}/bin"
export LD_LIBRARY_PATH="${LD_LIBRARY_PATH}:${GUROBI_HOME}/lib"

8. アカデミックライセンスを取得する．4番のWebページで「Academic Licenses」をクリック　→　2つのチェックボックスをチェックする　→　「Request License」をクリック
9. セットアップをする

$ sudo python /opt/gurobi600/linux64/setup.py install

10. ホームディレクトリで8番で取得したアカデミックライセンスを実行

$ cd ~
$ grbgetkey xxxxxx-xxxx-xxxxxx-xxxx

＊上のコマンドはアカデミックドメイン内で行わないと実行出来ません

[CGSuite (Combinatorial Game Suite)]

組合せゲーム理論を研究するためのオープンソースプログラム．
CGSuite
「左上のDownload」をクリック→「Linux」をクリックしてダウンロード→cgsuite-1.0.shのあるディレクトリへ移動

$ chmod +x cgsuite-1.0.sh
$ ./cgsuite-1.0.sh

後は，ウィザードにしたがってインストール．
OracleのJavaはダウンロードされているが実行されない方はopenjdkをインストールすると実行されます．（理由は分からない）

$ sudo apt-get install openjdk-7-jdk

[デフォルトの句読点の変更 mozcの導入]

Ubuntu13.10からはデフォルトでインストール済み（Ubuntu14.04からmozcがデフォルトで入っていないので注意）
すべての設定→テキスト入力→日本語(Mozc)を選択→右下にある次のような工具のアイコンをクリック．

一般→句読点→「，．」を選択．

13.10前は次のように変更．
「、　。」から「，　．」にデフォルトでの変更．
「わからん」さんのホームページを参考

$ sudo apt-get install mozc-server mozc-utils-gui ibus-mozc

再起動．

$ ibus-setup &

「インプットメソッド」→「インプットメソッドの選択」→「日本語」→「Mozc」を選択→インプットメソッドの「日本語ーMozc」を選択→「上へ(U)」で一番上に→「日本語ーMozc」を選択→「設定」を選択→句読点を変更

・ショートカットキーの取り消し

$ ibus-setup &

一般→キーボードショートカット→「切り替え」の「...」をクリック→「Alt」とモディファイされているキーボードショットカットを選択して削除
一般→キーボードショットカット→「次のインプットメソッド:」を削除

・Emacsにmozc

$ sudo apt-get install emacs-mozc emacs-mozc-bin 

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)

;; default-input-method := japanese-moz
;; 最後に追加する
(setq default-input-method "japanese-mozc")

「C-\」で日本語（mozc）の切り替えをする．
「C-\」を入力すると toggle-input-method関数が実行され，変数 default-input-method が指す input method のトルグを切り替える．しかし，デフォルトでは変数の値は「japanese」となっている（確認方法は「M-x describe-variable (RET) default-input-method」）．これを「japanese-mozc」に変更する（上のソースコードの最後）．
参考元：DDSKK を Emacs の Input Method とする

• • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • -

UbuntuとWindowsのマルチブート環境の時

[マルチブート環境や仮想マシン上の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

ルータを変えた時にネットワークが接続できない場合の設定方法

参考元: studio program
ルータ側でMACアドレスによる認証をしており，クライアント側でDHCPによるIPアドレスを取得するときにはクライアント側で次の設定が必要になった．

管理者権限でdhclient.confを開く。

$ sudo emacs /etc/dhcp/dhclient.conf

次を追加する。

interface "eth0"
{
    send dhcp-client-identifier=1:自分のMACアドレス;
}

CUDAのインストール方法

OS: Ubuntu13.10
GPU: NVIDIA GeForce GTX780
CUDA: cuda-6.0

・参考元： Ubuntu 12.10にCUDA 5.0を入れてみた
・参考元： cuda 6.0をubuntu serverに導入する

1.CUDA DownloadsのLinuxを選択する．DistributionをUbuntu13.04のx86 64bitのRUNをインストールする．

2.ファイルの権限を変更する

$ chmod 755 cuda_6.0.37_linux_64.run

3.Xサーバを落とす

$ sudo service lightdm stop

3.仮想ターミナルを開く Ctrl+Alt+F1

4. ドライバをインストールする

$ sudo ./cuda_6.0.37_linux_64.run -silent -driver

4-1. 4のドライバが曖昧．ここらへんの順番が曖昧．
NVIDIAドライバのダウンロード
オプション1でドライバを検索してインストール．

4-2. 権限を変更して実行

$ chmod 755 NVIDIA-Linux-x86_64-340.24.run
$ sudo ./NVIDIA-Linux-x86_64-349.24.run

5.Xサーバを再起動

$ sudo service lightdm start

6.Toolkitとサンプルのインストール（ドライバのところはNo）

$ sudo ./cuda_6.0.37_linux_64.run

7. パスの設定（.bashrc）

export PATH=$PATH:/usr/local/cuda-6.0/bin
export LD_LIBRARY_PATH=$LD_LIBRARY_PATH:/usr/local/cuda-6.0/lib64:/usr/local/cuda-6.0/lib

8.サンプルに必要なライブラリ

$ sudo apt-get install freeglut3-dev build-essential libx11-dev libxmu-dev libxi-dev libgl1-mesa-glx libglu1-mesa libglu1-mesa-dev

9.サンプルのmake(bin/x86_64/linux/releaseに実行ファイルができる)

$ cd NVIDIA_CUDA-6.0_Samples
$ make

C言語，C++言語 コーディング規約

C言語とC++言語を使用している．
ファイル名などの命名規則や，コーディング規約が自分なりに統一出来てないので統一する．

いろいろな流派や思想などがあるみたいなので，偉人が考えたものを疑わずに使用する．
（宗教戦争は避ける）
C言語とC++言語の参考元は次を使用．
競合する部分はGoogleのC++スタイルガイドを優先．

[C言語]
Linux kernel coding style

[C++言語]
Google C++スタイルガイド 日本語訳

参考元の部分に書かれている以外での補足．

• Emacsで行末の空白を強調表示する方法．

  ;; 行末の空白を強調表示
  (setq-default show-trailing-whitespace t)
  (set-face-background 'trailing-whitespace "#b14770")
  



• C++言語で書かれたソースコードの拡張子cppはWindowsのみ．拡張子はccにする．


• インクルードガードは「#pragma once」を使用する．


• googleはインデントを2^1，linusさんはインデントを2^3と言ってます．なので，私は2^2にします．

Codeforces #200 Div2

A. Magnets

シミュレーション。

#include <iostream>

using namespace std;

int main()
{
    int n, inp, ans = 0;
    bool plus = false;

    cin >> n >> inp;

    if (inp == 10) 
        plus = true;

    for (int i = 0; i < n - 1; i++) {
        cin >> inp;

        if (plus && inp != 10) {
            ans++;
            plus = false;
        }
        else if (!plus && inp != 1) {
            ans++;
            plus = true;
        }
    }

    cout << ans + 1 << endl;

    return 0;
}

B.Simple Molecules
ノード１、２の辺の本数をo1
ノード２、３の辺の本数をo2
ノード３、１の辺の本数をo3
と置くと、次の連立方程式が成り立つ。
・o1 + o3 = a
・o1 + o2 = b
・o2 + o3 = c

式を変形すると、
・2 * o1 = a + b - c
・2 * o2 = -a + b + c
・2 * o3 = a - b + c

#include <iostream>

using namespace std;

int main()
{
    int a, b, c;

    cin >> a >> b >> c;
    
    int o1, o2, o3;
    bool flag = true;

    if ((a + b - c) % 2 == 0 && (a + b - c) / 2 >= 0)
        o1 = (a + b - c) / 2;
    else
        flag = false;

    if ((-a + b + c) % 2 == 0 && (-a + b + c) / 2 >= 0)
        o2 = (-a + b + c) / 2;
    else
        flag = false;

    if ((a - b + c) % 2 == 0 && (a - b + c) / 2 >= 0)
        o3 = (a - b + c) / 2;
    else
        flag = false;


    if (flag) {
        cout << o1 << " " << o2 << " " << o3 << endl;
    }
    else 
        cout << "Impossible" << endl;
    
    return 0;
}

C. Rational Resistance
・直列接続の場合
R = y/x + 1
= (x + y) / x
・並列接続の場合
R = 1 / (y/x + 1)
= y / (x + y)

解説に、Calkin-Wilf treeという木が紹介されていた。
Calkin-Wilf treeとは、
・木の頂点が正の有理数への全単射となっている
・木の根は１
・頂点a/bの子はa/(a+b)と(a+b)/bの二分木
・すべての正の有理数は木の中のひとつの頂点となる

Calkin-Wilf treeの頂点a/bの高さを求める問題。

・a < bの場合
a'/b'の子はa'/(a'+ b')または(a'+ b')/b'なので、
a/bの親はa/(b - a)となる。

・a > bの場合
a/bの親は(a - b)/bとなる。

・aが１の場合
上のa

#include <iostream>

using namespace std;

typedef long long ll;

int main()
{
    ll a, b;
    ll ans = 0;

    cin >> a >> b;

    while (true) {
        if (a == 1) {
            ans += b;
            break;
        }
        if (b == 1) {
            ans += a;
            break;
        }

        if (a < b) {
            ans += (b / a);
            b = b % a;
        }
        else if (a > b) {
            ans += (a / b);
            a = a % b;
        }
    }
    cout << ans << endl;
    
    return 0;
}

D. Alternating Current

糸がからまった時にこのようにやります。
（後で書く）

#include <iostream>
#include <stack>

using namespace std;

int main()
{
    string inp;
    stack<char> st;

    cin >> inp;

    for (int i = 0; i < inp.size(); i++) {
        if (st.empty() || st.top() !=  inp[i])
            st.push(inp[i]);
        else
            st.pop();
    }
    if (st.empty())
        cout << "Yes" << endl;
    else
        cout << "No" << endl;

    return 0;
}

分割数

[参考元]
・秋葉拓哉,岩田陽一,北川宜稔「プログラミングコンテストチャレンジブック第2版」株式会社マイナビ、2010,pp.66-67
・分割数-Wikipedia
・動的計画法

蟻本の「分割数」が理解するのが難しかったのでメモ。

蟻本の「分割数」の問題文は
n個の互いに区別できない品物を、m個以下に分割する方法の総数を求め、Mで割った余りを答えなさい。
蟻本より

この問題文を別の言い方で表すと、「自然数nをその順番の違いを除いてm以下の和で表す方法の総数を求め、Mで割った余りを答えなさい。」となる。これを、p(n, m)と表す。

例）
n = 4, m = 3の場合を考える。品物を○、分割を|で表す。
○と｜の列が蟻本の問題文の解釈、下の列が別の言い方で表した場合。

○　｜　○　｜　○○
１　＋　１　＋　２

となる。
ただし、次の分け方は下の分け方と同じである。

○　｜　○○　｜　○
１　＋　２　　＋　１

[１]　p(n, m)を深さ優先探索で求める。

p(n', m')はp(n', m' - 1)とp(n' - m', m')の和として表せる。
・p(n', m' - 1)はn'をm'-1以下の和で表した場合の総数。すなわち、n'を表すのにm'を使わなかった場合。
・p(n' - m', m')はnを表すのに一つのm'を使った場合の総数。すなわち、n'を表すのにm'を使った場合。

ただし、p(0, m')=1、p(n',1)=1である。
また、mの値が減少していくように探索しているので、1+1+2や1+2+1などを2+1+1と一通りで数える。

#include <iostream>

using namespace std;

const int MAX_N = 1000;
const int MAX_M = 1000;

int n, m, M;

// 深さ優先探索
int p(int n, int m)
{
    int ret;

    if(n == 0 || m == 1)
        return 1;

    ret = p(n, m - 1);
    if(n >= m)
        ret += p(n - m, m);

    return ret;
}

void solve()
{
    cout << p(n, m) % M << endl;
    
}

int main()
{
    cin >> n >> m >> M;
    solve();

    return 0;
}

[２]メモ化をする

大きなnに対しては、p(n, m)が何度か呼ばれていることが分かる。
なので、引数の組(n, m)に対してメモ化を行う。
main関数は省略

#include <iostream>
#include <cstring>

using namespace std;

const int MAX_N = 1000;
const int MAX_M = 1000;

int n, m, M;
int memo[MAX_N + 1][MAX_M + 1]; // メモ化

int p(int n, int m)
{
    int ret;

    if (memo[n][m] >= 0)
        return memo[n][m];

    if(n == 0 || m == 1)
        return 1;

    ret = p(n, m - 1);
    if(n >= m)
        ret += p(n - m, m);

    return memo[n][m] = ret;
}

void solve()
{
    memset(memo, -1, sizeof(memo));
    cout << p(n, m) % M << endl;
}

[３]動的計画法

[２]のメモ化を動的計画法に持ち込む。
※蟻本ではdp[i][j] := jのi分割の総数としているが、
上の[２]に合わせるためにdp[i][j] := iのj分割の総数とした。
初期化の部分は[２]と対応をとりやすいように冗長に書いた。

#include <iostream>
#include <cstring>

using namespace std;

const int MAX_N = 1000;
const int MAX_M = 1000;

int n, m, M;
int dp[MAX_N + 1][MAX_M + 1]; // dp

void solve()
{
    for (int i = 0; i <= m; i++)
        dp[0][i] = 1;
    for (int i = 0; i <= n; i++)
        dp[i][1] = 1;

    for (int i = 0; i <= n; i++)
        for (int j = 1; j <= m; j++) {
            if (i >= j) 
                dp[i][j] = (dp[i][j - 1] + dp[i - j][j]) % M;
            else
                dp[i][j] = dp[i][j - 1];
        }
    
    cout << dp[n][m] << endl;
}

ACPC2013 Day3

Problem C: Problem C: Mysterious Operator

＋演算子の規則は、
a1とa2をaの上位桁と下位桁としたとき、
次の規則を満たすものである。

a1 = x - y ・・・（１）
a2 = x + y ・・・（２）

（１）、（２）から

2x = a1 + a2
2y = a2 - a1

となるから、aの桁の分け方が決まり、xとyがある条件を満たせば、
そのaの桁の分け方でのxとyの組の個数は一意に定まる。
ここで、条件とは
・x >= 0
・y >= 0
・xは偶数
・yは偶数
・a1の桁数とa2の桁数の和はaの桁数と同じ

#include <iostream>
#include <cmath>

using namespace std;

int main()
{
    int a, cnt = 0, len;
    
    cin >> a;

    len = (int)log10(a) + 1;
        
    for (int i = 1; i <= len; i++) {
        int l = a / pow(10, i);
        int r = a - (l * pow(10, i));
            
        if ((l + r) % 2 != 0 || (r - l) % 2 != 0)
            continue;
        if ((l + r) / 2 < 0 || (r - l) / 2 < 0)
            continue;
        if (l != 0 && r != 0 && (int)log10(l) + (int)log10(r) + 2 != len) 
            continue;

        cnt++;
    }
    cout << cnt << endl;

    return 0;
}