AtCoder ABC013 D 阿弥陀 巡回置換

序

　ABC043以降やってればいいんじゃねとかいうのを真にうけてやってるとABC044 C で早速手に負えないものにぶつかり、解法にビット演算についてはABC014Bをやるとよいと書いてある。早速そこに飛びビット演算についてはなるほどとはおもったものの、せっかく ABC014 まで戻ったので、ではそのへんも片付けるかとやってみるとグラフ理論丸出しのABC014 D 閉路にぶつかった。つらい。 しょーがないので今度はグラフ理論の本でも読むかと図書館に行って借りたのがこれ。

グラフ理論の魅惑の世界- 巡回セールスマン問題、四色問題、中国人郵便配達問題・・・

　雨降ってたので立命館はやめて京都右京中央で借りたのだが、歴史はよくわかり基礎的な問題も押さえられるし一般書のわりにバンバン数式が出てくるのだが、やっぱり一般書なので細かいところまではよくわからない。おもしろいのはいいんだが、半分くらい読んでからこれではキリがないとおもい、とりあえずコードにもどるかと、深さ優先探索・幅優先探索をやってみたが全く歯がたたないことがよくわかった。ふむ。やはり地図を作って楽をしないと無理。ということで解法にある LCA をみたのだが、その補助手段としてダブリングというのが出てくる。2ⁿで情報圧縮するよくある手法だが、木の探索にもつかえるのか。ダブリングの例題として ABC013 D があるとどっかに書いてあったので更に ABC013 まで降りてきたのが今回のはじまりだ。順調に AtCoder の沼にはまっている様子がわかる。結局低い番号からナメていくしかなさそうだな。

ダブリング

　単なるアミダくじだが、それをD段重ねたらどうなる？というおもしろい問題だった。適当にアミダくじの結果をD回まわすものを書いてみたら当然のことで TLE(時間超過) である。ここまでは普通で、解法をみるとこのまわすのを圧縮するのにダブリングを使うということだ。ところで解法1として、情報圧縮第一弾として、1-Nまでの配列を用意して、横棒の情報をつかって横棒があるところで番号を入れかえていけばアミダくじの結果の配列ができるというのも気がつかなかったがこれはダブリングの次の方で重要な話題になってくる。

　ダブリングは単純で、2回あとの結果を繰り返すと4回になり8回になりと、2羃回後の結果がすぐわかるのでD回後もその2羃の組み合わせですぐわかるというものだった。自分は一度2羃の結果を入れた配列をつくりそれをつかって引き算していくというやりかたをやったがそれだと600ms台だった。いきなりDを2で割りつつアミダを2羃していくというのでそれが400ms程度まで圧縮できるようだ。

巡回置換

　解法には宿題として「置換・巡回置換・置換の積」というのがある。もっと圧縮できるらしいというので検討に入った。アミダくじの結果のように有限個の数字を入れかえてつくったアナグラムのようなもの(「置換」)は使われている数字の数以下でループする組み合わせの順番があり、それを巡回置換というが、その組み合わせの積の形で表現できるというものだった。こんな単純な入れ替えを数式化したものが、行列式の表現に必須のものだったり、また群論の基礎でもあったりするらしい。現代数学奥が深いな。群論は数学に出てくる構造を抽象化して扱うものとおもってたが、抽象化すると対称ということも議論の範囲に入るので単純な数字の入れ替えが基礎になるということか。

　アミダくじの番号と結果を上下に並べたものがその「置換」そのものになるので、解法1が置換の準備にもなる。そもそもこれをD段重ねるというのも「置換」の世界を無理にお題に仕立てなおしたものだと見れば辻褄があう。のだが、置換の積でなにか処理のしかたがあるのかもしれないがそこはよくわからなかった。巡回置換があると何段あろうがその剰余で何番目か見るだけですむのはすぐわかる事なので、とりあえずアミダの置換から巡回置換の配列をつくってそれを舐めて結果を出すという迂遠なことをやると当然ながらTLEになる。しょうがないので巡回置換をみつけながら結果を入れていくというやりかたをしたら無茶苦茶早くてびっくりした。

　よくわからんのだが、置換の積の処理の仕方も結局は巡回置換の組を並べてそれを端から舐めていって、Dと巡回置換の剰余を出してどうこうしていく、というやりかたなんだろうか。それならこれであってるということなのかな？ よくわからん。

群論入門 対称性をはかる数学 (ブルーバックス)

群論への30講 (数学30講シリーズ)