【競技プログラミング】難問も解ける！Young tableaux及びSkew tableauxのフック長の公式と数え上げ問題への適用
追記
この記事の内容に厳密性を付加した神記事が出てました！
【月刊組合せ論 Natori】EDPC-T Permutation を深掘り【2022 年 9 月号】
目的
最初に競技プログラミングにおいて有用なフック長の公式について説明し、次にそれの一般化と既存の問題の新しい解き方の提案をします
記事中にPermutation (EDPC-T)及びBall Eat Chameleons(AGC 021 E)のネタバレを含みます
公式の証明はしません(難しいので)
質問や訂正等あればコメントかtwitterまでよろしくお願います
ヤング盤(Young tableaux)のフック長の公式
一般にフック長の公式といえばこれで、競技プログラミングの世界でも高度典型として親しまれています
(図 1 ヤング図形とヤング盤)
ヤング図形は上図の様な正方形の集まりで、中に数を書き込む事が出来ます
また、下に行く程横に積まれるマスの数が少なくなります
ヤング図形にあるマスに書かれている数がそれより左上に書かれている数より大きくなるように数を書き込んだ物をヤング盤と言います
標準盤はヤング盤であって、、書かれている数は
ここで、ヤング図形に対して考えられる標準盤を数え上げる公式がフック長の公式です
フック長とは各マスについて、自分を含め右か下にあるマスの数です。(右下にあるマスは考えない事に注意してください)
マスの数の階乗から各マスのフック長を割った物が実はその答えになります
(図 2 各マスのフック長)
カタラン数
"()" , "(())" , "()()"の様に括弧の対応がきちんと取れている様な、'('と')'からなる文字列を括弧列といいます
ただし、")(" , "(()" の様に括弧の対応が取れてない物は括弧列とは呼びません
ここで長さ
- '('と')'はそれぞれ
N K(1\leq K \leq N) K
よって、長さ
これをカタラン数といいます
(図 3 標準盤の数がカタラン数に対応するヤング図形)
Skew tableaux のフック長の公式
これだけでもかなり色々な事が出来そうですが、フック長の公式は更に一般化出来ます
(図 4 Skew tableaux)
Skew tableauxは上図の様にヤング図形から小さいヤング図形を取り除いた様な形をしています
複雑ですが、これについても標準盤の様な物の数を数える事が出来ます
(図 5 操作)
まず、元の Skew tableaux から再帰的に"」"字型の部分を"「"字型に変える事で出来上がる全ての図形に対して(元のヤング図形における)フック長の逆数の積を求め、足し合わせます
ただし重複する図形は一回のみ計算します
これとマスの数の階乗の積が Skew tableaux の標準盤の様な物の数になります
頑張って計算すると図 4 の標準盤の様な物の数は
(図 6 再帰的操作後の図形と各マスのフック長)
一般的な場合においてこの公式の愚直な実装には指数時間かかってしまいますが、特定の状況下ではこれを高速化出来ます
permutation(EDPC - T)
Permutation (EDPC-T)を解くことを考えます
これが Skew tableaux の標準盤の様な物の数え上げに適応出来るのは定義より明らかですが、そのままやると計算量が爆発してしまいます
(図 7 <<<><>><<>に対応する Skew tableaux)
ここでよく観察すると再帰的に操作した後の図形は、左上を削る前のヤング図形に置いて、左下から右上に右または上に進むことでたどり着く経路に相当することが分かります。
よって原始的な DP によって答えを求める事が出来ます
(図 8 削る前のヤング図形)
カタランの台形(Catalan's trapezoids)
- n 個の'('と k 個の')'で文字列を作る
- 但し、途中で')'の数が'('の数より m 個以上多くなる事を許さない
この条件を満たす文字列の数 f(n,k,m)は Skew tableaux の標準盤の様な物の数え上げに帰着出来ますが、高さが 2 であることを利用してシンプルに二項係数の差として表す事が出来ます
これを**カタランの台形(Catalan's trapezoids)**と言います(参考:Catalan's triangle(wikipedia))
練習問題:Ball Eat Chameleons(AGC 021 E)
最後に
かなり濃密な記事になったと自負していますがいかがでしたか？
LGTM などをしてもらえると励みになります