ICPC 2019 国内予選 の問題F (AOJ:1637) について考えてみたよ、というか、色んな人の色んな解法を聞いて面白かったので自分なりにまとめてみました。

こういう問題です。『無向グラフが与えられます。頂点を押すと、その頂点と他の全ての頂点の接続関係が反転します。辺で繋がってたところは辺が消え、繋がってなかったところには辺が生えます。この操作を繰り返して全域木が作れますか。作れるならコスト最小のものを。』

脱線

ところで、こういう頂点の周りの辺を反転する操作は Seidel のスイッチング と呼ばれていて、元々は楕円幾何学という数学の問題を解くための道具として研究され始めたようです。

• J. H. van Lint and J. J. Seidel, "Equilateral Point Sets in Elliptic Geometry"

Equilateral Point Set というのは多分どの2点間の距離も等しいような点集合ということで、2次元ユークリッド平面上だったら正三角形の頂点3点がEquilateralだし、3次元ユークリッド空間なら正四面体で4点かな？楕円幾何学という曲がった空間だともっと大きな点集合がEquilateralになり得るのですが、さて実際のところ、r次元の空間で最大何点がEquilateralになるのだろうか、求めたい、というお話だったそうです。

なぜグラフが出てくるかというと、この幾何の問題は行列にエンコードすることができて、n*n行列に対してある操作を繰り返した結果の行列の固有値がある条件を満たせばEquilateral、みたいになるのですが、その行列をグラフの隣接行列として解釈すると、行列操作がグラフのSeidelのスイッチングに対応するのだとか（よくわかってないのであやふやなコメントです。）

というわけでこの論文では、7次元のEquilateral setを求めるために、7頂点グラフを反転させまくって作れる同値類を列挙して(page 339-340)楽しんでいました。楽しそうですね。

Seidel Switching で検索してみると、最近は スペクトラルグラフ理論 やグラフスペクトル理論と呼ばれる系のお話でよく参照されているようです。グラフを隣接行列という行列の形で表現してみたり、最近バズっていた記事で行列冪乗と最短路計算を結びつけたりみたいな話がありますけど、せっかく行列という線形代数っぽいものを持ち出すのだからもっと線形代数っぽい話をしようというのがスペクトラルグラフ理論で、具体的には、隣接行列などのグラフから作れる行列の固有値からグラフの性質を探る理論です。行列の掛け算くらいならまだしも、固有値なんてグラフ的に何か意味がある値になるんでしょうか。気になった方は、ir5さんによる「スペクトラルグラフ理論入門」というスライドなどお勧めです。

Seidel switching は、「特定の形のグラフに適用すると、固有値は変わらないが元のグラフと同型ではないグラフを作る」という道具としてよく言及されています。固有値が完全にグラフの形を語り切っているわけではなく抽象していることの証明として使われているわけですね。

以上の話はアルゴリズムと言うよりはグラフ理論寄りの話でしたが、

• A. Ehrenfeucht, J. Hage, T. Harju, and G. Rozenberg, "Complexity Issues in Switching of Graphs"

という研究などは、スイッチングで到達できる範囲内に条件を満たすグラフがあるかの判定問題の解き方や計算複雑性の考察をしています。目標のグラフに次数が低いノードが必ずあるならば多項式時間で見つけられる、などの、下の"方針A"で書いてあるような話も触れられています。

だいぶ脱線してしまいました。問題を解きましょう。

純粋関数型データ構造

• 作者: Chris Okasaki,稲葉一浩,遠藤侑介
• 出版社/メーカー: KADOKAWA
• 発売日: 2017/04/28
• メディア: 単行本
• この商品を含むブログ (1件) を見る

こういう本を翻訳しました。発売中です。よろしくお願いします。

この本は名前にある通りデータ構造の本なんですが、中でも、「永続データ構造」と言われる種類のデータ構造に特化して、それだけを丸々一冊扱っています。Topcoderなどで永続データ構造が活躍する問題というのは、まだまだ中々マイナーですが、これから流行るといいなあと思っておりいます。qnighyさんの記事

http://qnighy.hatenablog.com/entry/2012/12/02/032851

でいくつか例題が紹介されていました。

さて、この本、面白いんですが、本の中のサンプルコードは全て Standard ML というプログラミング言語で書かれています。正直なところ馴染みのない方も多いのではないでしょうか。というわけでこの記事では、C++ や Java に慣れている人向けに、ものすごく大雑把に Standard ML を紹介します。

データ構造に興味はあるけど知らないプログラミング言語で書いてあると読めるかどうかわからない･･･という方が読んでみる助けになれば幸いです。擬似コードを読むような気分で本のサンプルコードを違和感なく読めるいうところが目標です。この記事を読んでも Standard ML を書けるようにはならないと思います。

実行環境

「読めればよい」が目標なので実行する必要はない気もしますが、一応。

• SML/NJ http://www.smlnj.org/
• SML# http://www.pllab.riec.tohoku.ac.jp/smlsharp/ja/

などが人気のある処理系です。

関数定義と呼び出し

例として

fun norm x y = x*x + y*y

これがC言語でいうところの

int norm(int x, int y) {
  return x*x + y*y;
}

に当たります。つまり、fun というキーワードを使って

fun 関数名 引数1 引数2 引数3 ... = 関数本体

と書いてあるのが関数宣言です。引数の周りに括弧やコンマがないのが特徴的ですね。関数を呼び出すときも同じく括弧やコンマはつけずに

norm 1 2

とかやれば 5 になります。普通の演算子よりも関数呼び出しの方が結合が強いので、

norm 1 2 + 3

は (norm 1 2) + 3 と同じ意味で、8 です。26にしたい時は足し算の方に括弧をつけて norm 1 (2 + 3) とします。

こういう構文になっているのには「カリー化」などの理由があるんですが、純粋関数型データ構造の本を読む分には特に関係がないので、そういう風習なのだと割り切って読むとよいと思います。

変数/定数定義

val というキーワードで宣言します。

val pi = 3.14

関数の中でローカル変数を定義するときは let ～ in ～ end と書きます。

fun average x y z =
  let val s = x + y + z in
    s div 3 
  end

"let val s = ... in ～" というのは、 "～ という式の中では s を ... とする" みたいな英語的気分です。

この本は永続データ構造の本なので、一度作った値は絶対に壊しません。つまり、一度宣言した変数に別の値を後から再代入したりしません。なので、変数は val で初期値を指定して宣言するだけで、代入をする構文とかは出てきません。

型の定義（ツリー構造の定義）

こういうことを言うともしかしたら Standard ML 好きな人に怒られたりするかもしれないんですが、私の中では(Standard) MLというのは、ツリー構造の操作に特化した最強ツリー処理専用言語です。大抵の強まったデータ構造というのは工夫して構築されたツリー構造なわけで、だからこそデータ構造の解説書である本書では、最強のツリー処理言語であるMLが選ばれているわけです。

たとえば、整数値を格納する赤黒木の定義はこんな感じ。

datatype Rbtree = E
                | R of Rbtree * int * Rbtree
                | B of Rbtree * int * Rbtree

datatype というキーワードで新しい型を定義するんですが、新しい型というのは要するに、新しい種類の木を定義しています。ここで定義されている木にはEとRとBという三種類のノードがあると言っています。

Eノードには子供がない、つまり葉ノードですね。RやBノードには左の子と、格納しているint値と、右の子があります。こういう三種類のノードでできているツリー構造というのに Rbtree という名前をつけて定義しているわけです。

datatype 型の名前 = ノードのラベル1 of (そのノードの持つ情報(子ノードとか) * ... )
                  | ノードのラベル2 of (そのノードの持つ情報(子ノードとか) * ... )
                  | ...

という形で、何種類かノードがあるツリー構造の型を宣言します。この型の具体的な値を作るときには、こんな風に、今度は括弧とコンマで子などの情報を指定して

R (B (E,12,E), 34, E)

こうします。R や B や E のことを構築子（コンストラクタ）と呼びます。C++やJavaのコンストラクタとある意味同じで、ツリーのノードというオブジェクトを作る関数というわけです。

パターンマッチ（ツリー構造の操作）

ツリー構造を走査して操作する関数というのは大抵、ノードの種類ごとに場合が分かれて処理しつつ再帰していくことになります。この時に、「どのラベルのノードなのかの判定・分岐」と、「分岐したあとのノードの内部情報を変数におく」を一度に書ける構文が、パターンマッチです。

fun count_red E = 0
  | count_red (B (left, _, right)) = count_red left + count_red right
  | count_red (R (left, _, right)) = 1 + count_red left + count_red right

これは赤黒木の中の赤のノードの個数を数える関数。Eの場合、Bの場合、Rの場合に分岐しつつ、左の子や右の子を表すフィールドを変数にしてから関数本体へ突入しています。ノードの中でも要らない情報（この場合ノードに入っているint値）のところは _ と書いておくと無視できます。

パターンは多段に重ねることもできて

fun foo (R (R (_, _, _), _, _)) = ...
  | foo _ = ...

とすれば、「左の子もRであるようなRノードとそれ以外」 という分岐になります。このパターンマッチによって、ツリーで作るデータ構造の操作がとても簡潔に表現できます。

http://shuns.sblo.jp/article/28490553.html

という記事に赤黒木の再平衡の実装の例があります。（こちらの記事は Haskell という言語を使っているのですが、まあだいたい Standard ML でも同じです。）

asパターン

パターンマッチで分解して中のノードのラベルとかは調べたいんだけど、変数におくのは分解しないでそのノードを指したい、といった時に出てくるのが as パターンです。

fun foo (R (left as R (_, _, _), _, right)) = ...
  | foo _ = ...

「左の子もRであるようなRノード」が渡されたときに最初の分岐に行くのは先程の例と変わりませんが、同時に、そのRであるような左の子をleftという変数で指しています。

多相型

さっきの赤黒木だとintしかツリーに持たせられませんでしたが、場合によって格納する型を変えたいですよね。C++でいうtemplate、JavaでいうGenericsです。Standard ML では多相型といいます。C++やJavaだとRbtree<T>みたいな、型名の後に<>という尖った括弧でパラメタ型Tを書きますが、Standard ML だと、型名の前にポンとパラメタ型を書きます。

datatype 'a Rbtree = E
                   | R of 'a Rbtree * 'a * 'a Rbtree
                   | B of 'a Rbtree * 'a * 'a Rbtree

'a という ' のついたのがパラメタ型で、"int Rbtree" ならintが入る赤黒木に、"string Rbtree"なら文字列が入る赤黒木の型になるわけですね。

'a という表記はASCIIの範囲でソースコードを記述するための仮の姿で、実は、Standard ML使いにはこれはギリシャ文字の α という文字に見えています。というわけで本に書くときは全部こういうのは

datatype α Rbtree = E
                   | R of α Rbtree * α * α Rbtree
                   | B of α Rbtree * α * α Rbtree

と書いてあります。

リスト

リストというのは子が１つしかないノードが繋がっているツリーと考えることができます。CやJavaでは配列が言語に組み込みのデータ型として基本となっていますが、Standard ML では、リストが標準に用意されていて、基本的なデータ型としてあらゆる場面で使われます。

空のリストを表す [] が葉ノードで、格納した値と次のノードの二つの要素を持つノード :: が、標準のリストの構築子です。

::は便利さを考えて、中置演算子として書けるようになっています。

1 :: 2 :: 3 :: []

と書くと1,2,3というリストになります。

長いリストを書くのに便利なような専用の略記法も用意されていて

[1,2,3]

と書いても同じ意味になります。もちろんのこのリストを表したツリーを処理するときにはパターンマッチが使えて、例えばintのリストの値の総和を取るには

fun sum [] = 0
  | sum (x :: next) = x + sum next

こんな感じ。

シグネチャ・ストラクチャ・ファンクタ

この本、一番最初に出てくるサンプルコードが signature と structure というものをいきなり使っていて仰々しいのですが、あまり身構えずに適当に雰囲気で読み飛ばしましょう。誤解を恐れずにいうと、

• シグネチャはC++でいうとヘッダファイル(hogehoge.h)みたいなもので、型とか関数とかの宣言だけを集めたもの
• ストラクチャはhogehoge.ccファイルみたいなものでシグネチャで宣言したものの具体的な実装

くらいの理解で最初はなんとなく雰囲気で読めると思います。

いや、「ヘッダファイルみたいなもの」は実のところ流石にちょっと適当に言い過ぎました。C++のヘッダで宣言した関数に対して実装は一つしかありませんが、シグネチャに対しては何個も違う実装をすることができます。

• シグネチャはJavaでいうインターフェイスみたいなもの、関数の型の宣言だけ集めたもの
• ストラクチャは具体的なクラスみたいなもので、インターフェイスで宣言した関数の具体的な実装

の方が近いかな。Javaの標準ライブラリにある名前を借りると、Listシグネチャを実装するArrayListストラクチャやLinkedListストラクチャ、みたいな。ただし、Javaのインターフェイスやクラスは一つの型とその複数のメソッドを宣言/定義する物ですが、Standard ML のシグネチャやストラクチャは、複数の型と複数の関数のまとまりを宣言/定義します。

C++でいうとhttp://en.cppreference.com/w/cpp/container/priority_queue:priority_queueが実装にどんなコンテナを使うのか指定できるような感じで、「別のストラクチャをパラメタとして受け取って使うストラクチャ」が作れると便利です。こういうことをするのが functor というキーワードで定義される「ファンクタ」です。

たぶんこの辺りは本の具体的な例を読んでいただいた方が理解しやすそうです。

質問など

ありましたらなんでも http://twitter.com/kinaba まで気軽に投げつけてください。

• 入力
  • 初期燃料 F
  • タスクの集合 T = (d[0],r[0]), (d[1],r[1]), ... (d[N-1],r[N-1])
• 求めるもの
  1. 初期値 f = F
  2. Tから d<=f であるような一組(d,r)を取り除き、f=f-d+r とする
  3. ステップ2を繰り返す
  4. できるだけ多くステップ2を繰り返せるように頑張ったら何回できますか

ACM-ICPC 2013 アジア地区予選会津大会 の問題Iを解いてみたよ。