Ubuntu16.04 でのアクセスポイント化

OSでUbuntu16.04を使用しているパソコンをアクセスポイントとして使用する方法を紹介します.Ubuntu16.04から設定が簡単になっています.

用途

無線LAN内蔵でLANポートがあるノートPCをアクセスポイントとして利用できます.
ホテルや家などで有線LANをノートPCで利用しているときに,他の無線機器をネットワークに接続したいけどルータが無い場合があります.そのような時にノートPCをアクセスポイントとして利用すれば他の無線機器もネットワークを使用することができます.
f:id:tatanaideyo:20170716085028p:plain

アクセスポイントにする方法

手順1
デスクトップ右上にあるネットワークのアイコンをクリックして,「Wi-Fiを有効にする(W)」をクリックしてチェックを外す.
f:id:tatanaideyo:20170716065918p:plain:w340

手順2
「接続を編集する...」をクリックしてネットワーク接続の設定を開く.
f:id:tatanaideyo:20170716065937p:plain:w150

手順3
「Add」をクリックして,接続の種類として「Wi-Fi」を選び「作成...」をクリック.
f:id:tatanaideyo:20170716071643p:plain:w400

手順4
「モード(O):」で「Hotspot」を選択.
SSID(I):」にネットワーク名を入力する(SSIDはアクセスポイントの名前で,クライアント側でアクセスポイントを探すときに使用).
* SSIDは誰からも見ることが出来るので適切に決める
f:id:tatanaideyo:20170716071452p:plain:w200

手順5
Wi-Fi セキュリティ」タブを選択して,「セキュリティ(E):」として「WPA & WPA2 Personal」を選択.
「パスワード(P):」に適切なパスワードを入力して「保存(S)」をクリック.
* 安全上,パスワードには複雑で長いものに決める
f:id:tatanaideyo:20170716072806p:plain:w200

手順6
デスクトップ右上にあるネットワークのアイコンをクリックして,「Wi-Fiを有効にする(W)」をクリックしてチェックを付ける.
f:id:tatanaideyo:20170716073513p:plain:w340

K問題:Black and White Boxes

1. 概要

これは Competitive Programming (その2) Advent Calendar 2016 - Adventar の22日目の記事です.

今年のACM-ICPC 2016アジア地区つくば大会のK問題で組合せゲーム理論に関する問題が出題されました.この問題を通して組合せゲーム理論の紹介をします (考察が中途半端になってしまいました)
2017年1月5日に追記・修正しました.

解説等は公開されています.

natsugiriさんの分かりやすい解説があります .
ACM-ICPC 2016 Asia Tsukuba Regional, K 解法 - でも今日はSRMあるから

組合せゲーム理論の参考書として次の本を参考にしました.

組合せゲーム理論入門 ?勝利の方程式?

組合せゲーム理論入門 ?勝利の方程式?

1.1 [問題] Black and White Boxes (BWB)

アリスとボブの2人で行うゲーム.

  1. 直立に積み重なった箱の山がいくつかある.各々の箱は同じ大きさで白色か黒色に塗られている.
  2. アリスとボブが交互に手を打つ.先手のプレイヤーは公平に無作為に選ばれる.
  3. アリスの手番:1つの山から黒色の箱を1つ選び,その箱とその上にあるすべての箱を取り除く.
  4. ボブの手番:1つの山から白色の箱を1つ選び,その箱とその上にあるすべての箱を取り除く.

自分の手番で手を打つことができなければそのプレイヤーの負け.

どのプレイヤーが先手でも先手勝ち,または,どのプレイヤーが後手でも後手勝ちとなる初期局面のことを公平な初期局面という.n個の山が与えられる.その中からいくつかの山を選び初期局面とする.公平な初期局面の中ですべての山の箱の数の和が最大となるものを求めそのときの箱の数を答えよ.

  • 制約:n <= 40. 各々の山に含まれる箱の数 <= 40

1.2 [山の表記方法]

今後,この問題を短くBWBゲームと呼ぶことにします.
説明の為に一つの山を文字列として表します.Bを黒色の箱,Wを白色の箱として,文字列の左から右に向かって山の下から上に対応しているとします.便宜上,箱がない山を _ (アンダーバー) で表します.また,複数の山からなる局面を . (ピリオド)で区切ることにします.

例:1つの山)
 WBBW は下から白色,黒色,黒色,白色の四つの箱からなる一つの山

例:複数の山)

  • WBBW.WB は二つの山からなる局面で1番目の山はWBBW,2番目の山はWB
  • WW._.W.B は三つの山からなる局面で1番目の山はWW,2番めの山は空,3番目の山はW,4番目の山はB

2. 組合せゲーム理論とは?

組合せゲーム理論(combinatorial game theory)とは組合せゲームを解析する理論です.組合せゲームは大雑把にいうと二人有限確定完全情報ゲームです.

  • 二人:二人のプレイヤーが交互に手を打つゲーム
  • 有限:有限の手数で終了する
  • 確定:偶然に左右される要素がない
  • 完全情報:対局者はゲームの局面についての情報をすべて知っている

組合せとついているのは経済学などで現れるゲーム理論と区別するためです.BWBゲームは組合せゲームになります.

2.1 [対局者]

慣習として組合せゲームの二人の対局者を左と右と呼びます.BWBゲームではアリスとボブをそれぞれ左と右と呼ぶことにします..どちらの対局者が先手番となるかが重要なときには左,右ではなくアリスとボブと呼ぶそうです.ここでは慣習にしたがい左と右と呼ぶことにします.
一般的には最後の手を打った対局者が勝ちとなりそのようなゲームを正規形 (normal play) と呼びます.BWBゲームは打つ手が存在しない対局者の負けなので正規形です.逆に,最後の手を打った対局者が負けとなるゲームを逆形 (misere play) と呼びます.逆形のゲームは正規形のゲームと比べると解析が難しくなります.

2.2 [選択肢(option)]

与えられたゲームの局面に対して左が手を打って得られる局面をその局面の左選択肢 (left option) と呼びます.同様に,右が打って得られる局面を右選択肢 (right option) と呼びます.また,それぞれを区別しない場合はその局面の選択肢と呼ぶことにします.
ゲームの局面を頂点として左選択肢をその頂点の左下,右選択肢をその頂点の右下にくるように配置して得られる根付き木をゲーム木 (game tree) と呼びます.一般的なゲーム木とは異なるので注意してください.一般的なゲーム木では左選択肢と右選択肢が異なる高さで交互に現れますが,ここで扱うゲーム木は同じ高さに左選択肢と右選択肢が現れる可能性があります.

例:WBBWのゲーム木 )
WBBWというゲームに対して,左(アリス)は下から2番目の箱を選ぶか,下から3番目の箱を選ぶかの2つがあります.各々の手に対する左選択肢はWBとWでWBBWの左下に配置します.
f:id:tatanaideyo:20161222091102p:plain


3. 組合せゲームとは?

ゲームの局面をゲームと呼ぶことにします.先ほどのゲーム木の各々の頂点がそれぞれゲームになります.

3.1 [組合せゲーム]

[定義:ゲーム (の局面)]
ゲーム (の局面)  G G = \{\mathscr{g}^L \mid \mathscr{g}^R\} とする.
ただし, \mathscr{g}^L \mathscr{g}^R はそれぞれ左選択肢の集合と右選択肢の集合とする.

また, G^L, G^R でそれぞれ  \mathscr{g}^L, \mathscr{g}^R の要素の代表を表すことにします.

例:ゲーム (の局面) WBBW )
  WBBW = \{WB, W \mid WBB, \_\}
ここで,左選択肢の集合と右選択肢の集合はそれぞれ,  \mathscr{g}^L = \{WB, W\} \mathscr{g}^R = \{WBB, \_\} になります.通常,左選択肢の集合と右選択肢の集合は集合なので「{} 」(ブレース)で選択肢を囲みますが簡略化のために省略して表記します.


余談ですが,左選択肢と右選択肢が等しいゲームを不偏 (impartial)ゲームと言います.また,不偏ゲームでないゲームのことを非不偏 (partizan) ゲームと言います.今回のBWBゲームは非不偏ゲームですが,左も右も色に関わらずどの箱も取り除くことができるとルールを変えたゲームは不偏ゲームでニムと呼ばれる有名なゲームになります.
すべての不偏ゲームはニムと等価 (グランディー数が存在)であるという美しい結果が知られています.一般に,非不偏ゲームは不偏ゲームよりも解析が難しいです.
Advent Calendarの12日目のzukky162さんの記事で「グランディ数」について書かれているので興味のある方はどうぞ.
zukky162.hatenablog.com

3.2 [帰結類 (outcome class)]

組合せゲームでは,与えられたゲーム (の局面)に対して各々の対局者が最善の手を打った場合にどの対局者が勝つのかに興味があります.最善の手とは勝つことができるならそのような勝つことのできる手を打ち,勝つことができないならただ手を打つことです.
ゲーム (の局面)  G が与えられ  G からゲームを行ったときに起きうる結果は次の4通りです.この起きうる結果のことを帰結類 (outcome class) と呼びます.行いたいことは初期局面 (ゲーム) が与えられたときにそのゲームの帰結類を求めることです.

表1. 帰結類
帰結類 名称 定義
 \mathscr{N} ファジー 先手番(Next : 次)の対局者が必ず勝つ
 \mathscr{P} 後手番(Previous : 直前)の対局者が必ず勝つ
 \mathscr{L} どちらが先手番でも左(Left)が勝つ
 \mathscr{R} どちらが先手番でも右(Right)が必ず勝つ

すべてのゲーム (の局面) は  \mathscr{N}, \mathscr{P}, \mathscr{L}, \mathscr{R} の帰結類のちょうど1つに属します.ここで, \mathscr{N}, \mathscr{P} に属するゲーム (の局面) をそれぞれ  \mathscr{N}局面, \mathscr{P}局面と呼ぶことにします.
ゲーム  G の帰結類はゲーム木を見ることで分かります.ゲーム木の葉はその局面で選択肢が無いので後手勝ちとなります.すなわち葉は  \mathscr{P} 局面です.葉から順番に次の表にしたがって帰結類を決定していきます.

表2. 選択肢と帰結類の関係
 \exists G^R \in \mathscr{R} \cup \mathscr{P}  \forall G^R \in \mathscr{L} \cup \mathscr{N}
 \exists G^L \in \mathscr{L} \cup \mathscr{P}
 \mathscr{N}
 \mathscr{L}
 \forall G^L \in \mathscr{R} \cup \mathscr{N}
 \mathscr{R}
 \mathscr{P}

この表の見方は,例えば  G \mathscr{N} 局面(2行2列)となるのは,「 \exists G^L \in \mathscr{L} \cup \mathscr{P}」と「 \exists G^R \in \mathscr{R} \cup \mathscr{P}」が成り立つ場合です.すなわち,先手勝ちとなるのは,左が先手番のときに左勝ち (左の選択肢に左勝ちまたは後手勝ちとなる手が存在する),右が先手番のときに右勝ち(右の選択肢に右勝ちまたは先手勝ちとなる手が存在する)となることです.
また,左選択肢が存在しない場合「 \forall G^L \in \mathscr{R} \cup \mathscr{N}」は成り立ちます.同様に,右選択肢が存在しない場合「 \forall G^R \in \mathscr{L} \cup \mathscr{N}」は成り立ちます.このことからも葉の帰結類が \mathscr{P}となることが分かります.

例:ゲーム WBBWの帰結類 )
WBBWに対して表2を適用した結果が下のゲーム木(頂点に帰結類を表示)になります.WBBWの帰結類は \mathscr{R} となるので,どちらが先手番でも右が必ず勝ちます.
f:id:tatanaideyo:20161222093423p:plain


4. ゲームの代数

ここまでで,初期局面の帰結類はゲーム木が分かれば決定することができるということを見てきました.しかし,一般的にゲーム木を知るというのは時間がかかるので他の方法で簡単に帰結類が決定できれば嬉しいです.
ここでは,帰結類を決定するのに役立つゲームの道具について見ていきます.

4.1 [ゲームの直和]

お互いに独立なゲーム  G, H の直和  G + Hを定義します.お互いに独立なゲームとは片方のゲームに手を打っても片方のゲームに影響を与えない2つのゲームです.
例えば,2つの山 WBBW.BW からなるBWBゲームを考えます.対局者は1番目の山WBBWに手を打つとします.このとき,2番目の山はBWのままで影響がありません.同様に,2番目の山に手を打っても1番目の山には影響がありません.したがって,ゲームWBBW とBWはお互いに独立なゲームとなります.BWBゲームでは各々の山をゲームとしたとき,山同士はお互いに独立となっています.
ゲームの直和とは直和成分  G, H を並べて1つのゲーム  G + H としたものです.対局者はどの直和成分にも手を打つことができます.これをきちんと定義したものが次になります.

[定義:ゲームの直和]
ゲーム  G H の直和  G + H
  \{\mathscr{g}^L + H, G + \mathscr{h}^L \mid \mathscr{g}^R + H, G + \mathscr{h}^R \}
とする.
ただし,選択肢の集合  \mathscr{g} とゲーム G の直和  \mathscr{g} + G を,
  \bigcup_{X \in \mathscr{g}} X + G
とする.

上の定義からゲームの直和  G + H もゲームです .また,選択肢の集合の和集合を簡略化のために「,」(カンマ)で表記します.
各々の直和成分の帰結類が分かっているときにそれらの直和が簡単に分かると嬉しいのですがBWBゲームでは簡単に分かります.すなわち,各々の山の帰結類が分かっているときに,それらの山からなるゲームの帰結類も簡単に分かります.このことについてはゲームの値で見ていきます.

例:ゲームWBBW, BWの直和)
互いに独立なゲームを
  G = WBBW  = \{WB, W \mid WBB, \_\}
  H = BW  = \{\_ \mid B\}
とする.
各々の左選択肢の集合と右選択肢の集合は次の通りになる.
  \mathscr{g}^L = \{WB, W\}, \mathscr{g}^R = \{WBB, \_\}
  \mathscr{h}^L = \{\_\}, \mathscr{h}^R = \{B\}
このとき,
  \mathscr{g}^L + H = \{WB + BW, W + BW\}
  G + \mathscr{h}^L = \{WBBW + \_\}

  \mathscr{g}^R + H = \{WBB + BW, \_ + BW\}
  G + \mathscr{h}^R + H = \{WBBW + B\}
となる.
したがって  G H の直和は
  G + H = \{WB + BW, W + BW, WBBW + \_ \mid WBB + BW, \_ + BW, WBBW + B\}
となる.

4.2 [ゲームの(符号)の反転]

ゲームの符号の反転は再帰的にゲームの対局者の役割を入れ替えます.

[定義:ゲームの(符号)の反転]
ゲーム  G の符号の反転  -G
  \left\{-\mathscr{g}^R \mid -\mathscr{g}^L\right\}
とする.
ただし,
  -\mathscr{g}^R = \bigcup_{G^R \in \mathscr{g}^R} \left\{-G^R\right\}
  -\mathscr{g}^L = \bigcup_{G^L \in \mathscr{g}^L} \left\{-G^L\right\}
とする.

例:ゲームWBBWの反転 )
始めに, \_ = \{ \mid \} から  -\_ = \{ \mid \} = \_ である.
WBBWのゲーム木と上の定義によって再帰的に反転させた-WBBWのゲーム木は次の通りである.左がWBBWのゲーム木,右上が反転させた-WBBWのゲーム木,右下がゲーム木の形とBWBゲームのルールから考察したときのゲーム.

f:id:tatanaideyo:20161222091102p:plain:w300 f:id:tatanaideyo:20161222095514p:plain

-WBBWのゲーム木を見てBWBゲームのルールを思い返すと, \{\_ \mid \} となるゲームは B になります. -WBBWのゲーム木で-WをBに交換します.次に, \{\_ \mid B\} となるゲームは BW となるので,-WB を BW に交換します.次に, \{\_ \mid BW, B\} となるゲームは BWW なので -WBB を BWW に交換します.最後に, \{BWW, \_ \mid B, BW\} となるゲームは BWWB なので -WBBW をBWWB に交換します.
すなわち,-WBBW は BWWB となります.BWBゲームではゲームの反転は黒箱を白箱に,白箱を黒箱にを入れ替えたゲームになります.

4.3 [ゲームの等価性]

2つのゲームが等しいことを次のように定義します.

[定義:ゲームの等価性]
ゲーム  G H の等価性  G = H
 すべてのゲーム  X に対して,  G + X H + X が同じ帰結類に属する
こととする.

この定義からゲームが等価であることを判定するのは大変そうです.そこで,判定しやすい同値な定義を紹介します.その前に特別なゲームに名前を付けます.

[定義:零ゲーム]
 0 = \{ \mid \} とする.

上の定義は左選択肢と右選択肢のないゲームの名前を0とするということを表しています.0は選択肢が無いので  \mathscr{P} 局面です.帰結類のところで帰結類  \mathscr{P}の名称を零としましたがこれは次の定理によるものです.

[定理: \mathscr{P}局面と零ゲームの等価性]
ゲーム G \mathscr{P}局面  \Leftrightarrow  G = 0


任意のゲーム  G, H に対して次の表のことが成り立ちます.

表3. ゲームの比較と帰結類
 G > 0  \Leftrightarrow  G は左の勝ち  G > H  \Leftrightarrow  G - H は左の勝ち
 G = 0  \Leftrightarrow  G は後手番の勝ち  G = H  \Leftrightarrow  G - H は後手番の勝ち
 G < 0  \Leftrightarrow  G は右の勝ち  G < H  \Leftrightarrow  G - H は右の勝ち
 G \parallel 0  \Leftrightarrow  G は先手番の勝ち  G \parallel H  \Leftrightarrow  G - H は先手番の勝ち

ここで, G \ge 0 G > 0 または  G = 0 です.すなわち,ゲーム G において左が後手番で勝つことを表しています.同様に, G \le 0 G < 0 または  G = 0 でゲーム G において右が後手番で勝つことを表しています.また, G - H が先手番の勝ちならば  G \ge H でも  G \le H でもないので, G H は比較不能であるとして  G \parallel H と表します.
 \ge \le はゲームの全体上で半順序となります.また,二項演算を  + G の逆元を  -G単位元を0 (零ゲーム) とするとゲームの全体上で可換群となります.
ゲームの等価性の定義に従って  G = H を示すよりも, G - H というゲームにおいて後手勝ちとなることを示す方が簡単です.

例:ゲームBの反転 )
表3を使うとゲームBの反転ゲームが分かります.
 G = B  = \{\_ \mid  \},  H = W  = \{  \mid \_\} とする.
ゲームB.W ( G + H) は後手勝ちのゲームなので, G + H = 0
すなわち, H = -G となるので,ゲームBの反転ゲームはWとなる.

4.3 [ゲームの標準形 (canonical form)]

4.2では帰結類の観点からゲーム木の形が異なっていても等しいゲームというものを定義しました.もちろんゲーム木が同じであれば帰結類も等しくなります.ここでは,帰結類を保ちながらゲーム木を小さくする方法を紹介します.初めにその方法を2つ紹介します.

[定義:劣位な選択肢]
ゲーム  G = \{L_1, L_2, \ldots \mid R_1, R_2, \ldots \}

左選択肢において, L_i \ge L_j のとき, L_j を劣位な選択肢と呼ぶ.
右選択肢において, R_i \le R_j のとき, R_j を劣位な選択肢と呼ぶ.

劣位な選択肢の除去はその手よりも良い手があるならば良い手を選択するので選ばないという直感的な操作になります.

例:劣位な選択肢の除去 )
ゲームWBBW  = \{WB, W \mid WBB, \_\} に対して劣位な選択肢の除去を行います.

  • WB  \ge W : WB - W = WB + B において左が後手勝ちになる
  • WBB  \le _ : WBB - 0 = WBB において右が後手勝ちになる

したがって,左選択肢の W と右選択肢の _ は劣位な選択肢となります.ゲームWBBW において劣位な選択肢の除去を行ったゲームは
  \{WB \mid WBB\}
となります.

次に打消し可能な選択肢を紹介します.打消し可能な選択肢は重要なのですがBWBゲームでは使わないので定義だけ行います.

[定義:打消し可能な選択肢]
ゲーム  G = \{L_1, L_2, \ldots \mid R_1, R_2, \ldots \}

左選択肢  L_i のある右選択肢  L_i^R に対して, G \ge L_i^R が成り立つとき,  L_i を打消し可能な選択肢と呼ぶ.
右選択肢  R_i のある左選択肢  R_i^L に対して, G \le R_i^L が成り立つとき,  R_i を打消し可能な選択肢と呼ぶ.

打消し可能な選択肢  L_1 のある右選択肢が  L_1^R = \{L'_1, L'_2, \ldots, \mid \ldots \} のとき,
  \{L'_1, L'_2, \ldots, L_2, \ldots \mid R_1, R_2, \ldots\}
 L_1 の短絡と呼ぶ.
打消し可能な選択肢  R_1 のある左選択肢が  R_1^L = \{\ldots, \mid R'_1, R'_2, \ldots \} のとき,
  \{L_1, L_2, \ldots  \mid R'_1, R'_2, \ldots, R_2, \ldots \}
 R_1 の短絡と呼ぶ.


上の2つの操作を行ってゲーム木を小さくします.

[定義:ゲームの標準形 (canonical form)]
ゲーム  G の全局面に対して次の2つの操作

  1. 劣位な選択肢の除去
  2. 打消し可能な選択肢の短絡

を行うことによって得られるゲームを  G の標準形(canonical form)と呼ぶ.

ゲームの標準形とゲームの等価性には次の関係があります.

[定理:ゲームの標準形と等価性の関係]
ゲーム  G, H

 G, H は標準形かつ  G = H  \Leftrightarrow  G H は同型

 G H のゲーム木が根付き木として同じ形をしているとき  G H は同型であるとします.
すべてのゲーム  G の標準形は操作の順序に関わらず一意に定まります.また,標準形はゲームの等価性を保つものの中で最小のゲーム木となります.ゲームの標準形を考えることによってゲームの解析の見通しが良くなります.


5. ゲームの値

組合せゲーム理論ではいくつかの重要なゲームの標準形に名前を付けています.先ほど  \{ \mid \} という形のゲームに0という名前をつけました.これらの重要なゲームに対する名前をゲームの値と呼ぶことにします.
ほとんどのゲームの値に対して,その帰結類,ゲームの値同士の直和やその帰結類を求めることは簡単ではありません.しかし,BWBゲームで現れる全てのゲームには数という値がついておりこれらの計算が簡単にできます.

[定義:整数]
正整数  n に対して,
  n = \{n - 1 \mid \}
  -n = \{ \mid 1 - n\}
とする.
ただし, 0 = \{ \mid \}

これらは, \{n - 1 \mid \} という形をしたゲームに値 n を割り当てるということに注意してください.
例えば, 1 = \{0 \mid \} = \{\{ \mid \} \mid \},  -2 = \{ \mid -1\} = \{ \mid \{ \mid 0\}\} = \{ \mid \{ \mid \{ \mid \}\}\} を表しています.

f:id:tatanaideyo:20170105001104p:plain:w400

例:ゲームB, WW)
ゲームの定義に従ってゲームBとWWを表します.ここで, \_ = \{ \mid \} = 0 だったことに注意してください.
  B = \{\_ \mid \} = \{0 \mid \} = 1
  WW = \{ \mid W, \_\} = \{ \mid W\} = \{ \mid \{ \mid \_\}\} = \{ \mid \{ \mid 0\}\} = -2

WWの左から2つ目の等号では  W < \_ から劣位な選択肢の除去を行っています.
ここで,Bのゲーム木の形と1のゲーム木は等しいので  B = 1 となります.同様に,WWのゲーム木と-2のゲーム木は等しいので  WW = -2 となります.帰納的に, n個の黒箱からなる山のゲームの値は  n n個の白箱からなるゲームの値は  -n となります.

整数という名前から次のことが成り立ちます.

[定理:ゲームの値が整数のゲーム]
ゲーム A, B, C とそれぞれの整数のゲームの値を  a, b, c \in \mathbb{Z}_{+}

  •  A + B = C  \Leftrightarrow  a + b = c
  •  A \ge B  \Leftrightarrow  a \ge b
  •  A \le B  \Leftrightarrow  a \le b

上の定理では整数の値が付いたゲーム同士の直和は整数同士の和,比較も整数の比較で行えるということです.
上の定理と表3から,  B = 1 > 0 なのでBは左勝ち, WW = -2 < 0 なのでWWは右勝ちのゲームとなります.


次に,他のゲームの値である2進有理数を定義します.

[定義:2進有理数]
整数  j > 0,奇数  m に対して,
  \frac{m}{2^j} = \left\{ \frac{m - 1}{2^j}  \mid \frac{m + 1}{2^j} \right\}
とする.
先ほどの整数と同様に,2進有理数の値が付いたゲーム同士の直和は2進有理数同士の和,比較も2進有理数の比較で行えます.
有限のゲーム木に対応する数は整数と2進有理数のみですが,有限でないゲーム木にまで拡大すると,実数,順序数およびそのほかの数を含む超現実数(surreal number) が得られます.
今回のBWBゲームでは有限のゲーム木のみを扱うので,整数と2進有理数のことを数と呼ぶことにします.


6. BWBゲームの解法

6.1 [BWBゲームのゲームの値]

BWBゲームで現れるすべてのゲームの値は数になります.初めに,BWBゲームに数を割当てる方法を天下り的に説明します.

 n 個の箱からなる1つの山のゲームの値を求めます.この値は数 (整数または2進有理数) となります.

1山のゲームの値の割当て方
入力:  n個の箱からなる1つの山  G.山の下から連続する同じ色の箱の数を  m
出力:  G の数  val

val = 0  // Gのゲームの値 (数)

if (G の一番下の箱の色が黒)
    val = m;
else // G の一番下の箱の色が白
    val = -m;
    
for (i = 1; i <= n - m; ++i) {
    if (下から m + i 番目の箱の色が黒)
        val += 1.0 / pow(2, i);   // 1 / 2^i を加える
    else if (下から m + i 番目の箱の色が白)
        val -= 1.0 / pow(2, i);    // - 1 / 2^i を加える
}

return val;

例:ゲームBBBWBBWの値)
ゲーム BBBWBBWの値は次のようになります. n = 7, m = 3 です.
 BBBWBBW =  3 + \left(-\frac{1}{2}\right) + \frac{1}{4} + \frac{1}{8} + \left(-\frac{1}{16}\right) = \frac{45}{16}

例:ゲームWWBWWの値)
ゲーム WWBWWの値は次のようになります. n = 5, m = 2 です.
 WWBWW =  -2 + \frac{1}{2} + \left(-\frac{1}{4}\right) + \left(-\frac{1}{8}\right) = -\frac{15}{8}

複数の山からなるゲームはそれぞれのゲームの直和になるのですが,ゲームの値が数ならばその加算,減算を行うことで簡単に計算が出来ます.

例:2つの山からなるBBBWBBW.WWBWWのゲームの値)
 BBBWBBW + WWBWW  = \frac{45}{16} + \left(-\frac{15}{8}\right) = -\frac{547}{360}
このゲームの値は負になるので,表3から右勝ちのゲームとなります.

例:3つの山からなるB.WB.WBのゲームの値)
 B + WB + WB =  \left(1\right) + \left((-1) + \frac{1}{2}\right) + \left((-1) + \frac{1}{2}\right)
       =  \left(1\right) + \left(-\frac{1}{2}\right) + \left(-\frac{1}{2}\right) = 0
このゲームの値は0になるので後手勝ちのゲームとなります.


ここまでは天下り的にBWBゲームに対して値を割当ててきましたが,どのように考察すればよいのかについてここでは説明していきます.そのために,次の定理を利用します.

[定理:ゲームが数となるための条件]
ゲーム  G のすべての左選択肢  G^L と右選択肢  G^R が数であり,かつ  G^L < G^R が成り立つならば, G \mathscr{g}^L < x < \mathscr{g}^R を満たす最も簡単な数  x である.

ここで, \mathscr{g}^L は左選択肢の最大値, \mathscr{g}^R は右選択肢の最小値とする.

ここで,選択肢がすべて数ならば劣位な選択肢の除去から左選択肢と右選択肢の個数はそれぞれ1個以下になります.上の定理にある最も簡単な数とは次の通りです.

[定義:最も簡単な数]
 x^L < x^R に対して, x^L < x < x^R を満たす最も簡単な数  x とは,次のどちらかによって定まる数

  1.  x^L < x < x^R を満たす整数  n が存在するならば, x はそのような  n の中で最も絶対値の小さい整数
  2. 1が成り立たない場合, x x^L < \frac{i}{2^j} < x^R の中で  j が最小となる2進有理数

ゲームBBBWBBWの値を上の定理を用いて求めてみます.下の箱から1個づつ加えていきながら値を求めていきます.
Step 1. ゲームBBB
第5章の整数から BBB =  3

Step 2. ゲームBBBW
 BBBW  = \{BB, B, \_ \mid BBB\} = \{2, 1, 0 \mid 3\} = \{2 \mid 3\}
 2 < 3 なので上の定理を用いて  2 < x < 3 を満たす最も簡単な数  x を求めます.
 x は最も簡単な数の定義の条件2から  \frac{5}{2} となります.
したがって,BBBW =  \frac{5}{2}

Step 3. ゲームBBBWB
 BBBWB  = \{BBBW, BB, B, \_ \mid BBB\} = \left\{\frac{5}{2}, 2, 1, 0 \mid 3 \right\} = \left\{\frac{5}{2} \mid 3\right\}
同様に, \frac{5}{2} < x < 3 を満たす最も簡単な数  x \frac{11}{4} なので,
 BBBWB =  \frac{11}{4}

Step 4. ゲームBBBWBB
 BBBWBB  = \{BBBWB, BBBW, BB, B, \_ \mid BBB\} = \left\{\frac{11}{4}, \frac{5}{2}, 2, 1, 0 \mid 3 \right\} = \left\{\frac{11}{4} \mid 3\right\}
同様に, \frac{11}{4} < x < 3 を満たす最も簡単な数  x \frac{23}{8} なので,
 BBBWBB =  \frac{23}{8}

Step 5. ゲームBBBWBBW
 BBBWBBW  = \{BBBWB, BBBW, BB, B, \_ \mid BBBWBB, BBB\} = \left\{\frac{11}{4}, \frac{5}{2}, 2, 1, 0 \mid \frac{23}{8}, 3 \right\} = \left\{\frac{11}{4} \mid \frac{23}{8} \right\}
同様に, \frac{11}{4} < x < \frac{23}{8} を満たす最も簡単な数  x \frac{23}{8} なので,
 BBBWBBW =  \frac{45}{16}

 i - 1 番目のステップで得られるゲームを  G_{i-1} = \{x_{i-1}^L \mid x_{i-1}^R\} としてそのゲームの値を  x_{i - 1} とします.また,山の下から連続する同じ色の箱の数を  m とします.
上の考察から  i 番目のステップで得られるゲーム  G_{i} の値  x_i を求めます.
・下から  m + i 番目の箱が黒色の場合
  G_{i} = \{x_{i-1}^L, x_{i-1} \mid x_{i-1}^R\} = \{x_{i-1} \mid x_{i-1}^R\}
・下から  m + i 番目の箱が白色の場合
  G_{i} = \{x_{i-1}^L \mid x_{i-1}, x_{i-1}^R\} = \{x_{i-1}^L \mid x_{i-1}\}
 m + i 番目の箱が黒色なら  x_{i-1} < x_{i} < x_{i-1}^R を満たす最も簡単な数,白色なら   x_{i-1}^L < x_{i} < x_{i-1} を満たす最も簡単な数となります.これは,それぞれ  x_{i-1} \frac{1}{2^i} -\frac{1}{2^i} を加えることに等しくなります.

6.2 [BWBゲームの解法]

数をゲームの値として持つゲームの帰結類は表3から  \mathscr{P}, \mathscr{L}, \mathscr{R} のいづれかになり, \mathscr{N} 局面になることはありません.したがって,公平な初期局面とは \mathscr{P} 局面に対応するので,いくつかの山を選びそのゲームの値の和が0となるものの中で箱の数の和が最大となるものを選ぶという問題となります.BWBゲームを定式化すると次の通りです.

BWBゲームの解法
 i \in \{1, \ldots, n\} 番目の山の箱の数  l(i),ゲームの値 (整数または2進有理数)  s(i) \in \mathbb{Q}

最大化:  \sum_{i \in X} l(i)
 制約:  \sum_{i \in X} s(i) = 0
      X \subseteq \{1, \ldots, n\}

 l(i) は山に含まれる箱の数を数えるだけなので簡単にできます.また, s(i) は 6.1 のアルゴリズムを用いて計算できます.このとき, s(i) の値は数 (整数または2進有理数) となるので有理数型か倍精度浮動小数点型で値を保持します.この前処理には高々  40 \times n の計算時間しかかかりません.
 \sum_{i \in X} s(i) = 0 は部分和問題で  n \le 40 なので半分全列挙で  O(n 2^{n/2}) の計算時間で求めることができます.蟻本のpp.147にナップサック問題を半分全列挙で解いているのでそれを参考にすると良いと思います.

例:B.W.WB.WB)
各々の山の  s(i) l(i) を求めます.

  1. B:  s(1) = 1,  l(1) = 1
  2. W :  s(2) = -1,  l(2) = 1
  3. WB:  s(3) = -\frac{1}{2},  l(3) = 2
  4. WB:  s(4) = -\frac{1}{2},  l(4) = 2

 \mathscr{P} 局面となる組合せは  X_1 = \{1, 2\}, X_2 = \{1, 3, 4\} です.このとき, X_1 の箱の数の和は2, X_2 の箱の数の和は4 となるので最大となる選び方は  X_2 で4です.


例:B.W.WB.WB.BWW.BWW)
各々の山の  s(i) l(i) を求めます.

  1. B:  s(1) = 1,  l(1) = 1
  2. W :  s(2) = -1,  l(2) = 1
  3. WB:  s(3) = -\frac{1}{2},  l(3) = 2
  4. WB:  s(4) = -\frac{1}{2},  l(4) = 2
  5. BWW:  s(5) = \frac{1}{4},  l(5) = 3
  6. BWW:  s(6) = \frac{1}{4},  l(6) = 3

 \mathscr{P} 局面となる組合せで箱の数が最大となる選び方は  X = \{1, 2, 3, 5, 6\} で箱の数の和は 10です.

6.3 [BWBゲームについて]

natsugiriさんのブログにも書かれていますが,BWBゲームは枝分かれのないLR-ハッケンブッシュというゲームになります.また,今回説明したゲームの値の割当て方はヴァンルード(Thea van Roode) によるものです.このことは,参考資料「組合せゲーム理論入門」のpp.137-138に書かれています.
始めの方でBWBゲームを左と右が同じ選択肢を持つことができると変更したゲームはニムというゲームになり解析が簡単になると言いましたが,左と右の打つ手を次のように変更したゲームはどうなるでしょうか.

  • アリスの手番:1つの山から黒色の箱を1つ選び,その箱とその上または下にあるすべての箱を取り除く.
  • ボブの手番:1つの山から白色の箱を1つ選び,その箱とその上または下にあるすべての箱を取り除く.

このゲームはドミノ倒しというゲームになります.残念なことに,ドミノ倒しのすべてのゲームはBWBゲームのように値が数になるとは限りません.ただ,次のようにいろいろな名前の付いたゲームの値が現れ楽しいゲームとなっています (組合せゲーム理論入門 pp.134-136).

  • BBBBBBBB  = 8
  • BBBBWWWW  = \pm 3
  • BW  = *
  • BWWB =  = \uparrow
  • BWBWBWBWB =  = \frac{1}{16}
  • BWBWBWBW =  = *4

最後はグランディ数です.

7. まとめ (感想)

読んでくださって有難うございました.さらっと書いてさらっと投稿しようと思ったのですが長ったらくなってしまいました.また大事な部分の考察が間に合わずに中途半端な記事になってしまったことを反省します.
追記・修正したのでとりあえずは完成となります.

明日の担当はhama_duさんの「(\(⁰⊖⁰)/)(\(⁰⊖⁰)/)(\(⁰⊖⁰)/)(\(⁰⊖⁰)/) |_|_|_|」とkenkooooさんの「Mi_Sawa さんに刺されない✨最大フロー🎀💕」です.
hama_duさんの記事は一体何が書かれるのかタイトルから想像出来ないので楽しみです.kenkooooさんは刺されないか心配です.

8. ソースコード

#include <bits/stdc++.h>

using namespace std;

class BlackAndWhiteBoxes {
public:
    BlackAndWhiteBoxes(int n) : n(n), pile(n, make_pair(0.0, 0)) {}
    void Input();
    int MaximumBoxes();
private:
    int n; // 山の数
    vector<pair<double, int>> pile; // pile[i] := i番目の山のゲームの値,箱の数

    double GameValue(const string p);
};

double BlackAndWhiteBoxes::GameValue(const string p) {
    int idx = 1;
    while (idx < p.size() && p[0] == p[idx])
        ++idx;

    double v = (p[0] == 'B' ? idx : -idx);
    for (double two_pow = 2.0; idx < p.size(); two_pow *= 2.0, ++idx)
        v += (p[idx] == 'B' ? 1.0 / two_pow : -1.0 / two_pow);

    return v;
}

void BlackAndWhiteBoxes::Input() {
    string p;
    for (int i = 0; i < n; ++i) {
        cin >> p;
        pile[i] = make_pair(GameValue(p), p.size());
    }
}

int BlackAndWhiteBoxes::MaximumBoxes() {
    const int n1 = n / 2, INF = 40 * 100;
    vector<pair<double, int>> vl(1 << n1, make_pair(0.0, 0));
    for (int i = 0; i < 1 << n1; ++i) {
        for (int j = 0; j < n1; ++j)
            if (i >> j &1) {
                vl[i].first += pile[j].first;
                vl[i].second += pile[j].second;
            }
    }

    sort(vl.begin(), vl.end());

    int max_size = 0;
    for (int i = 0; i < 1 << (n - n1); ++i) {
        double sum_v = 0.0;
        int sum_len = 0;

        for (int j = 0;  j < n - n1; ++j)
            if (i >> j & 1) {
                sum_v += pile[n1 + j].first;
                sum_len += pile[n1 + j].second;
            }

        auto it = lower_bound(vl.begin(), vl.end(), make_pair(-sum_v, INF));
        if (it != vl.begin())
            --it;

        if (max_size < it->second + sum_len && it->first == -sum_v)
            max_size = it->second + sum_len;
    }

    return max_size;
}

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);

    int n;

    cin >> n;
    BlackAndWhiteBoxes bwb(n);
    bwb.Input();

    cout << bwb.MaximumBoxes() << endl;

    return 0;
}

Tournamentの最小道被覆問題 (Minimum Path Cover Problem)

情報工学工房の問題で面白かったのでまとめます.
 POJ : 1776 -- Task Sequences

問題(意訳)

単純有向グラフ G=(V, A) が与えられる.ただし,Gの任意の2頂点  u, v \in V (u \neq v) に対して, (u, v) \in A または  (v, u) \in A を満たす(どちらも満たさない場合はない).
Gの最小道被覆 (Minimum Path Cover) を求めよ.

入力は |V| \times |V| の隣接行列で与えられる.成分(i, j)は0か1で,頂点iとjの間に弧があれば1,無ければ0である.

  • 制約: 1 \le |V| \le 1,000
方針

いくつか用語の説明をします.
[最小道被覆(Minimum Path Cover)]
G = (V, A) の道被覆(Path Cover)とは点素パスの集合PでVの各頂点がPに属するちょうど1つの道に属するという性質を満たすもの.
点素パスとは頂点の重複がない道.

[Tournament]
有向グラフがTournamentであるとは無向完全グラフのすべての辺に向き付けをおこなったもの.
Tournament (graph theory) - Wikipedia

一般グラフの最小道被覆問題はNP困難なのですがTournamentでは多項式時間アルゴリズムが存在します.また,この問題で与えられるグラフはTournamentの拡大グラフなので解くことができます.競技プログラミングではDAGの最小道被覆問題を解くアルゴリズムがよく知られていると思います.

この問題で与えられるグラフの両方向に弧が存在する頂点間に対して,どちらか片方のみに弧があると考えてtournamentとして考えます.tournamentに対して次の定理が成り立つのでそれを用いて問題を解きます.

[定理 (Redei 1934)]
Tournamentにはハミルトン路が存在する

証明
頂点数に関する帰納法で証明を行う.
(基底段階 |V| = 1, 2)
グラフを全て列挙することによって正しさが確認できる.
(帰納段階)
 |V| = kで成り立つと仮定してk+1の場合を証明する.
任意の頂点数k+1のTournament G=(A,V)を考える.
任意に頂点  v_{k+1} を取り除いたグラフ G'を考えるとG'は頂点数kなので帰納法の仮定からハミルトン路  P'=(v_1, v_2, ..., v_k) が存在する.
Pに  v_{k+1} を加えてGのハミルトン路Pを構成する.
 1.  (v_{k+1}, v_1) \in A の場合
  P'の先頭に  v_{k+1} を加えて  P = v_{k+1} P' とする.
 2.  (v_k, v_{k+1}) \in A の場合
  P'の後ろに  v_{k+1} を加えて  P = P' v_{k+1} とする.
 3. それ以外
  P'の先頭から添字の最も小さい頂点で  v_{k+1} からの弧が存在する頂点を  v_{cur} とする.
  仮定から 2 < k かつ  (v_{k+1}, v_k) \in A であるからそのような頂点は存在する.
  このとき, v_{cur} の選び方から  (v_{cur-1}, v_{k+1}) \in Aである(最小性論法).
  したがって, P = v_1, ..., v_{cur-1}, v_{k+1}, v_{cur}, ..., v_k とする. □

f:id:tatanaideyo:20161022144840p:plain:w1000
最小道被覆問題はパスの数の最小化でしたのでハミルトン路が存在すればそれが最適解となります.したがって,アルゴリズムとしては上の証明のように頂点を1つずつハミルトン路を保つように加えていきます.
計算時間は  O(|V|^2) です.より高速なアルゴリズムとして Bar-NoyとNor(1990)の  O(|V| \log|V|) のものが存在します(未読).

ソースコード
#include <iostream>
#include <vector>

using namespace std;

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);

    int n;
    string s;

    while (cin >> n) {
        cin.ignore();

        // Input Graph
        vector<vector<bool> > g(n, vector<bool>(n, false));
        for (int i = 0; i < n; ++i) {
            getline(cin, s);
            for (int j = 0; j < n; ++j) {
                if (s[j << 1] == '1')
                    g[i][j] = true;
            }
        }

        // Find a hamiltonian path in a like tournament g
        // n == 1
        if (n == 1) {
            cout << "1\n1\n1\n";
            continue;
        }

        // 2 <= n
        vector<int> next(n, -1);
        int head = 0, tail = 0;

        // add v in a path (head -> ... -> tail)
        for (int v = 1; v < n; ++v) {
            if (g[v][head]) { // v -> head -> ... -> tail
                next[v] = head;
                head = v;
            }
            else if (g[tail][v]) { // head -> ... -> tail -> v
                next[tail] = v;
                tail = v;
            }
            else { // head -> ... -> v_cur-1 -> v -> v_cur -> ... -> tail
                for (int cur = head; ; cur = next[cur]) {
                    if (g[cur][v] && g[v][next[cur]]) {
                        next[v] = next[cur];
                        next[cur] = v;
                        break;
                    }
                }
            }
        }

        // Output
        cout << "1\n" << n << '\n';
        for (int cur = head; cur != -1; cur = next[cur])
            cout << cur + 1 << (cur == tail ? '\n' : ' ');
    }

    return 0;
}

デュアルブートの不具合:Ubuntu16.04とWindows10

WindowsUbuntuデュアルブートで利用しているのですが,Ubuntuが立ち上がらなくなるという不具合があったので対処しました.

環境

 ・/dev/sda1:Microsoft Windows回復環境(システム)
 ・/dev/sda2:EFI システム
 ・/dev/sda3:Microsoft予約
 ・/dev/sda4:NTFS (Windows)
 ・/dev/sda5:Linux Swap
 ・/dev/sda6:Ext4 (Linux)

現象

BIOSの起動方法で「UEFI起動」を有効にするとWindows10,無効にするとUbuntuが立ち上がるようになっています.デフォルトでUbuntuが立ち上がるようにしていたのですが黒い画面の左上に「-」と表示されて立ち上がりませんでした.
BIOSの画面も選択できないのですがUbuntuのLIVE DVDから起動して「UEFI起動」を有効にしてWindows10を利用することは出来ました.
この現象の前にWindowsを1週間ほど利用していました.

原因

LIVE DVDから/dev/sda6をいろいろ見たのですがデータは壊れてなさそうです.
確かな原因は分からないのですが,可能性がありそうなのがWindows10のUniversary Updateの影響でUbuntuブートローダがおかしくなったのではないかと思います.飽くまでも推測です.
[参考元]

解決方法

Ubuntuブートローダであるgrubをインストール.
初めにUbuntuのLIVE DVDを起動.そして,端末を起動して次のコマンドを入力.
(#以降はコメント)

$ sudo mount /dev/sda6 /mnt # 自分のUbuntuは/dev/sda6に入っているのでマウントする
$ sudo grub-install /dev/sda --root-directory=/mnt --force # grubをインストール
$ sudo umount /dev/sda6 # アマウント

次に,再起動を行い/dev/sda6を起動(再起動させるとブートローダが自動で立ち上がる).
端末を起動して次のコマンドを入力.

$ sudo grub-install /dev/sda --root-directory=/mnt --force

[参考元]

ABC #042,ARC #058

ARC#058に参加しました.
ABC#042はA問題からD問題,ARC#058はC問題からF問題です.

[Problem A. 和風いろはちゃんイージー]

方針

昇順にソートして小さい方から5,5,7と等しいかを調べる.

ソースコード
#include <bits/stdc++.h>

using namespace std;

typedef long long  ll;

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);

    vector<int> abc(3);
    for (int i = 0; i < 3; ++i)
        cin >> abc[i];
    sort(abc.begin(), abc.end());

    if (abc[0] == 5 && abc[1] == 5 && abc[2] == 7)
        cout << "YES\n";
    else
        cout << "NO\n";

    return 0;
}

[Problem B. 文字列大好きいろはちゃんイージー]

方針

N個の文字列を昇順にソートして小さい文字列から連結していく.

ソースコード
#include <bits/stdc++.h>

using namespace std;

typedef long long  ll;

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);

    int n, l;

    cin >> n >> l;
    vector<string> s(n);
    for (int i = 0; i < n; ++i)
        cin >> s[i];

    sort(s.begin(), s.end());

    for (auto x : s)
        cout << x;
    cout << endl;

    return 0;
}

[Problem C. こだわり者いろはちゃん]

方針

支払う金額をN円から始めて各桁に D_1, \ldots, D_kを含まなくなるまで1円づつ増やし確認する.Kは9以下かつ \{D_1, \ldots, D_k\} \neq \{1, 2, 3, 4, 5, 6, 7, 8, 9\}なのでこの手続きはいつか停止する.また,支払う金額は高々100Nである(各桁に使える数がD'とするとNより1桁大きくて各桁がD'の数は条件を満たす).したがって,計算時間は O(N \log N)

ソースコード
#include <bits/stdc++.h>

using namespace std;

typedef long long  ll;

bool Check(int ans, const vector<int> &d) {
    while (ans) {
        int n = ans % 10;
        for (auto dd : d)
            if (dd == n)
                return true;
        ans /= 10;
    }

    return false;
}

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);

    int n, k;

    cin >> n >> k;
    vector<int> d(k);
    for (int i = 0; i < k; ++i)
        cin >> d[i];

    int ans = n;
    while (Check(ans, d))
        ++ans;

    cout << ans << endl;

    return 0;
}

[Problem D. いろはちゃんとマス目]

方針

SからGへの単調な経路数で灰色の部分を通らない経路数はいくつかを考える.
SからGへの経路は赤枠のいづれかのマスを必ず通る.3行4列のマスから右に移動して3行5列のマスからGまで移動する経路数は,
 (Sから(3,4)までの経路数)×((3,5)からGまでの経路数)
となる.
障害物が無い場合の経路数は組合せ数を用いて計算することができる.横W'マス,縦H'マスの場合は {W'+H'-2 \choose W'-1}となる.後は,同様に赤色の枠の部分の各々に対して経路数を計算した総和が答えになる.
ただし,H-A通りに対して組合せ数を計算するとTLEになるので前もって計算する.したがって,計算時間は  O( (H + W) \log(H + W)) である.

f:id:tatanaideyo:20160724025429p:plain

ソースコード
#include <bits/stdc++.h>

using namespace std;

typedef long long  ll;
const ll MOD = 1000000007;

// a, bの最大公約数と, ax+by=gcd(a, b)となるx,yを求める
ll Extgcd(ll a, ll b, ll &x, ll &y) {
    ll g = a;
    if(b != 0) {
        g = Extgcd(b, a % b, y, x);
        y -= (a / b) * x;
    }
    else {
        x = 1;
        y = 0;
    }

    return g;
}

// ax = gcd(a, m) (mod m) となるxを求める
// a, m が互いに素ならば関数値はmod m でのaの逆数となる
ll ModInverse(ll a, ll m)
{
    ll x, y;
    Extgcd(a, m, x, y);
    return (x % m + m) % m;
}

const int MAX_N = 2 * 100010;
vector<ll> fact(MAX_N), rfact(MAX_N);
void Init() {
    fact[0] = rfact[0] = 1;
    for (int i = 1; i < MAX_N; ++i) {
        fact[i] = (fact[i - 1] * i) % MOD;
        rfact[i] = (rfact[i - 1] * ModInverse(i, MOD)) % MOD;
    }
}

inline ll Combination(ll n, ll k) {
    return ((fact[n] * rfact[n - k]) % MOD) * rfact[k] % MOD;
}

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);

    Init();

    ll h, w, a, b;

    cin >> h >> w >> a >> b;
    ll ans = 0;
    for (int i = 1; i <= h - a; ++i) {
        ll l1 = Combination(i + b - 2, min((ll)i - 1, b - 1));
        ll l2 = Combination(h - i + w - b - 1, min(w - b - 1, h - i));
        ans = (ans + (l1 * l2) % MOD) % MOD;
    }

    cout << ans << endl;

    return 0;
}

[Problem E. ]

方針

[Problem F. ]

方針

まとめ

EとFは後でまとめる.
問題は面白かった.

Ubuntu 16.04 LTS 64bit インストール後設定

システムの設定

[外付けキーボード(HHK)]

「システム設定」→「テキスト入力」→「日本語」を選択して「-」をクリック→「+」をクリックして「英語(US)」を追加→「次のソースへ切り替え:」と「前のソースへの切り替え:」を選択してDelete

[句読点の変換]

Dashで「mozc」と入力して「Mozcの設定」を選択→句読点「,.」に変更

[ノートPC側でCapsLockをCtrlに変更]
# gnome-tweak-toolのインストール
$ sudo apt-get install gnome-tweak-tool
# gnome-tweak-toolの実行
$ gnome-tweak-tool &

「Typing」→「Ctrlキーの位置」→「Caps LockをCtrlとして扱う」
再起動をする.

[ファイルとアプリケーションの利用状況を記録しない]

「システム設定」→「セキュリティとプライバシー」→「ファイルとアプリケーション」タブを選択→「ファイルとアプリケーションの利用状況を記録」を「オフ」に変更

[ディレクトリ名を日本語から英語に変更する]
$ env LANGUAGE=C LC_MESSAGES=C xdg-user-dirs-gtk-update

「Don't ask me this again」をチェック→「Update Names」をクリック

[プロンプトを変更]

powerlineを入れると見やすく設定できる.
f:id:tatanaideyo:20170202163156p:plain
デフォルトのプロンプトPS1では階層が深くなるにつれて見えにくくなるので変更
./bashrcの「PS1=」右辺の「w」を「W」に変更.これによって,カレントディレクトリが絶対パス表示ではなく現在のディレクトリに変更される.

アプリケーションのインストール

[Dropbox]

Dropboxのサイトで「Ubuntu(.deb) 64bit」をダウンロード→ファイルをクリック→「Ubuntu Software」が立ち上がるので「インストール(I)」をクリック

[Chromeのインストールと設定]
$ sudo apt-get install chromium-browser #chromeのインストール

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

$ sudo apt-get install pepperflashplugin-nonfree

Chromeの右上の f:id:tatanaideyo:20160509223628p:plain:w15 をクリック→「設定(S)」をクリックして設定

  • 「デザイン」の「ホームボタンを表示する」と「ブックマークバーを常に表示する」をチェック
  • 左上の f:id:tatanaideyo:20160509224103p:plain:w40 を右クリック→「アプリのショートカットを表示」のチェックを外す
  • 「ダウンロード」の「ダウンロード前に各ファイルの保存場所を確認する」をチェック

拡張機能を入れる.wget http://ftp.de.debian.org/debian/pool/contrib/m/msttcorefonts/ttf-mscorefonts-installer_3.6_all.deb

  • Weblioポップアップ英和辞典」を追加
[powerlineのインストール]

GNOME端末の見た目をハイカラにする.

$ sudo apt-get install powerline

「/usr/share/doc/powerline/README.Debian」に設定方法が書かれている
bashを利用しているので「~/.bashrc」に「./usr/share/powerline/bindings/bash/powerline.sh」を追加

設定ファイルは「~/.config/」内に設定ファイルを入れる(知り合いから貰ったので非公開).

[Emacs24のインストール]

Emacsはspacemacsを利用.次のgithubのInstallを参考にインストール (手順を忘れたので詳細は次にインストールするときに).
https://github.com/syl20bnr/spacemacs

[gcc]

g++の常に使うオプションのalias.

alias gpp="g++ -std=c++11 -Wall -O2" # .bashrcに追記する
[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
[Ipeのインストール]

図などの描画ソフト(Ipe (software) - Wikipedia).

$ sudo apt-get install ipe

cgalのプラグインを追加.凸法やアレンジメントなどができる.

$ sudo apt-get install libcgal-ipelets
[gnuplotのインストール]

グラフの描画ソフト

$ sudo apt-get install gnuplot5
$ sudo apt-get install gnuplot5-x11
[ttf-mscorefonts-installerに関するエラー]

2017/1/18 : ttf-mscorefonts-installerのインストールエラーに対する対応策

$ sudo apt-get remove ttf-mscorefonts-installer
$ wget http://ftp.de.debian.org/debian/pool/contrib/m/msttcorefonts/ttf-mscorefonts-installer_3.6_all.deb
$ sudo dpkg -i ttf-mscorefonts-installer_3.6_all.deb

参考元upgrade - ttf-mscorefonts-installer tries to install in 16.04 - Ask Ubuntu


[CPLEX]

IBM ILOG CPLEX は数理計画法のソルバー.
アカデミック・学生は無料でインストール可能 .
大学のメディアサーバからインストール (他の方法でダウンロード場所を見つけるのは困難).

$ chmod +x cplex_studio127.linux-x86-64.bin # 実行権限を付加
$ sudo ./cplex_studio127.linux-x86-64.bin # インストーラを実行 (いくつかの質問に答える)

「.bashrc」に次を追加

## for CPLEX
export PATH=$PATH:/opt/ibm/ILOG/CPLEX_Studio127/cplex/bin/x86-64_linux/
## for oplrun
export LD_LIBRARY_PATH=/opt/ibm/ILOG/CPLEX_Studio127/opl/bin/x86-64_linux/

「source .bashrc」で「.bashrc」を再読み込み
参考元:CPLEX のインストール - PukiWiki

[Gephiのインストール]

グラフ可視化のソフト (普段はGraphvisを使っているが楽しそうなのでインストール)
Gephi - The Open Graph Viz Platform からGephiをダウンロード.

$ tar -xzvf gephi-0.9.1-linux.tar.gz # 解凍 0.9.1はバージョン
$ ./gephi-0.9.1/bin/gephi # Gephiの実行

実行するにはJava7かJava8が必要みたいです.
自分の環境ではJava9がデフォルトで選択されているので変更します.

$ sudo update-alternatives --config java # java8を選択
$ sudo update-alternatives --config javac # java8を選択

TODO : 設定ファイルで指定できるように模索中

2017年2月9日 : 描画出来ない
「./gephi-0.9.1/etc/gephi.conf」に「export LIBGL_ALWAYS_SOFTWARE=1」を追加
参考元:Gephi crashes when trying to open a graph on linux · Issue #1192 · gephi/gephi · GitHub

TODO : アンチエイリアスの設定ができない

[Anaconda4.20]

PythonとScience系のパッケージをまとめたもの.
Download Anaconda Now! | Continuum
Python 3.5 version 64-BIT INSTALLER」をダウンロード.

$ chmod +x Anaconda3-4.2.0-Linux-x86_64.sh # ファイルを実行可能に
$ ./Anaconda3-4.2.0-Linux-x86_64.sh # Installerを実行

参考元:Anaconda を利用した Python のインストール (Ubuntu Linux) – Python でデータサイエンス


[CGALのインストール]

計算幾何学のライブラリのインストールとデモと実行方法.
CGALのインストール.

$ sudo apt-get install libcgal-dev  # cgalのインストール
$ sudo apt-get install libcgal-demo # demoのインストール

デモの実行.
デモとExampleはdemo.tar.gzとexamples.tar.gzという圧縮ファイルで提供されいているので解凍して実行.

$ dpkg -L libcgal-demo # デモとExampleがインストールされている場所を検索
$ cp /usr/share/doc/libcgal11v5/demo.tar.gz . # 適当な場所で実行するためにコピー
$ tar -xzvf demo.tar.gz # 解凍
$ cd demo # demoディレクトリ内にいろいろなdemoがある

いくつかのデモにはサードパーティのライブラリが必要になるので逐次インストール.

  • AABB_tree
$ sudo apt-get install cmake libqglviewer-dev # 必要なライブラリ
$ cmake .

NOTICE: This demo requires QGLViewer, Qt5, and will not be compiled.と出力されて実行できない(Ubuntu16.04なら出来たのに orz).
CGAL installation + CGAL and QT5 - Stack Overflow
次をインストールすると上のエラーが消えた.

$ sudo apt-get install qtscript5-dev libqt5opengl5-dev libqt5svg5-dev

プログラムの実行.

$ cgal_create_CMakeLists -s hoge # hogeという実行ファイルが生成される
$ ./hoge # hogeの実行

TCO 2016 Round 1A Div1

寝過ごして参加できなかったので復習しました.

[Easy 250: EllysTimeMachine ]

問題

アナログ時計の現在の時刻が"HH:MM"の形式で与えられる.HHは短針が表す時間,MMは長針が表す分を表している.ただし,

  • HH  \in \{01, 02, 03, 04, 05, 06, 07, 08, 09, 10, 11, 12\}
  • MM  \in \{00, 05, 10, 15, 20, 25, 30, 40, 45, 50, 55\}

の値をとる.
短針と長針の向きを交換したときの現在の時刻を答えよ.ただし,HHとMMはそれぞれ上の取りうる値に近い値にする(進める方向).

方針

問題文通りにシミュレーションをします.一つ一つステップに従って愚直に実装します.詰まりそうな部分は上手くまとめようとせずに書きます.

ソースコード
#include <bits/stdc++.h>

using namespace std;

typedef long long  ll;

class EllysTimeMachine {
public:
	string getTime(string time) {
            int hh = (int)(time[0] - '0') * 10 + (int)(time[1] - '0');
            int mm = (int)(time[3] - '0') * 10 + (int)(time[4] - '0');
            string res;

            if (mm == 0)
                res = "12";
            else {
                if (mm < 50)
                    res = "0" + to_string(mm / 5);
                else
                    res = to_string(mm / 5);
            }

            res += ":";
            if (hh == 12)
                res += "00";
            else if (hh == 1)
                res += "05";
            else
                res += to_string(hh * 5);

            return res;
	}
};

[Med 500: EllysSocks ]

問題

各々の靴下のサイズを表す配列Sが与えられる.この中でP個の靴下の組を求める.ただし,選んだ各々の靴下の組のサイズの差の絶対値の最大値を最小化する組合せを求め,その時の最小値を答えよ.

制約
  •  2 \le |S| \le 1,000
  •  1 \le S_i \le 1,000,000,000
  •  1 \le P \le |S|/2
方針

蟻本の「最小値の最大化(pp.131-132)」と同様な考え方で二分探索法を用いて解きます.
靴下の組の差がd以下になるようにたくさの靴下の組を選んだときにP個以上選べるかを考えます.このとき,dの値で二分探索を行います.先ほどの条件を満たすならばdの値の小さい部分を探し,満たさないなら大きな部分を探します.
次に,どのように条件を判定するのかを考えます.まず,選ぶべきペアはソートしたときに隣り合う靴下同士を選ぶ方が差の絶対値が小さくなります.また,(a, b, c) がサイズの小さい順にソートされているとしたときに,(a, b) が選べるならば (b, c) を選ぶよりも (a, b) を選んだ方が残りの部分で選べる靴下の組の数が増える可能性があります.したがって,靴下のサイズでソートしたときに,小さい順から貪欲的に隣り合う靴下との差の絶対値がd以下なら選ぶとして組を作っていきます.そして,選んだ組の数がP個以上ならtrueを返し,それ以外ならfalseと返すことによって判定することが出来ます.

ソースコード
#include <bits/stdc++.h>

using namespace std;

typedef long long  ll;

class EllysSocks {
public:
	int getDifference(vector <int> S, int P) {
            const int n = S.size();
            sort(S.begin(), S.end());

            int lb = -1, ub = 1000000000;
            while (ub - lb > 1) {
                int mid = (lb + ub) * 0.5;

                int num = 0, idx = 0;
                while (idx + 1 < n) {
                    if (S[idx + 1] - S[idx] <= mid) {
                        ++num;
                        ++idx;
                    }
                    ++idx;
                }

                if (P <= num)
                    ub = mid;
                else
                    lb = mid;
            }

            return ub;
      }
};

[Hard 1000: EllysTree ]

問題

ラベル付されたN+1頂点の根付き木が与えられる.それぞれのラベルは0からNであり,根のラベルは0である.
頂点u,vに対して,uがvの先祖またはvがuの先祖ならuとvの間を移動することが出来る.ただし,既に訪れた頂点には移動できない.
今,根にいるとしてすべての頂点にちょうど1回訪れるような移動順序を答えよ.ただし,そのような移動順序が複数あるならば辞書式順序で最小のものを答えよ.また,すべての頂点をちょうど1回訪れるような移動順序が存在しないなら空集合を返せ.

制約
  •  1 \le N \le 100
方針

解法が思いつかなかったのでmayokoさんの解法を参考にしました.
2016 TCO Algorithm Round 1A hard: EllysTree - mayoko’s diary

まず全探索することを考えます.現在いる頂点から訪れることが出来て,まだ訪れていない各々の頂点に対して次に訪れるとして再帰的に探索をします.途中で,現在いる頂点から訪れることが出来る頂点が存在しないならこのような移動順序は存在しません.このような全探索を行うと計算時間はO(N!)となり解くことができません.
ここで,求める解が辞書式順序の上で最小となるものを見つけることに注目します.すなわち,次に訪れる頂点の候補としてu, v(u, v)があり,uの後の移動順序がL,vの後の移動順序がL'としたときに, L'< L であっても uL < vL' となります.これは,距離の総和の最小化などでは成り立ちません.
したがって,次に訪れることが出来る頂点の中でラベルの小さい頂点uを優先的に探索を行います.uを訪れた後で残りの頂点を訪れることができるのならuを選びます.
次に,頂点uを訪れた後で残りの頂点を訪れることが出来るのかの判定部分を考えます.ここからは自分の中でよく分かっていないのでmayokoさんのブログをご覧ください.ここからはより支離滅裂です.
頂点uが訪れることが出来る頂点はuの部分木と根からuへのパスの頂点になります.ここで,このような移動することが出来るに注目して構成したグラフを考えます.先ほどの判定部分はこのグラフ上でuを始点としたハミルトン路が存在するかの問題に等しくなります.一般のグラフではハミルトン路の存在判定はNP完全になりますが,先ほどのように構成されたグラフでは効率的に解けるかは分かりません.ここらへんはもう少し考えてみます.

まとめ