なんとな~くしあわせ?の日記

「そしてそれゆえ、知識そのものが力である」 (Nam et ipsa scientia potestas est.) 〜 フランシス・ベーコン

AtCoder - AtCoder Beginner Contest 066 (11) を解いてみた

ABC 040 D問題に使われるアルゴリズム要素は組み合わせ、繰り返し2乗法、階乗のmod逆元、(+累積和的な処理?)です。組み合わせ(nCr)については、以前動的計画法によるアルゴリズムを紹介しましたが

nantonaku-shiawase.hatenablog.com

AtCoderではこれでもまだ処理が遅くACが取れませんでした。

組み合わせ

繰り返し2乗法や階乗のmod逆元については、他でもいろいろ解説があるので言及しません。しかし、組み合わせの処理にてなぜそれらを使わなければいけないか書いておきます。

組み合わせを階乗の式で表す

Rubyとかだと配列クラス(Array)に#combinationメソッドが用意されておりすぐに求められるのですが、競技プログラミングの場合これでは遅すぎます。いったん組み合わせ(Combination)がどのような式で構成されていたか確認してみましょう。

組み合わせの式

以下のようなものになります、nの階乗をrの階乗と(n-r)の階乗で割ったものでした
{}_n \mathrm{C}_r = \frac{n!}{r!(n-r)!}

この、階乗の数値が巨大なものになってもすばやく計算する方法が繰り返し2乗法で、巨大な階乗の逆数を求める方法が階乗のmod逆元と呼ばれているようです。

英語で調べると、これらはFast modular exponentiation*1とかmodular inversesという名前で紹介されている感じです。

これらを覚えると、AtCoder Beginner Contest 021 (D - 多重ループ) も解けます、これは嬉しい。

ABC 066 (11) 、解説の解説

AtCoder Beginner Contest 066 (D - 11)

問題の考察ヒント

問題文から

数の種類が n 種で、項が n + 1 項あるので、必ず同じ数の項が複数存在します。
また、すべての数が 1 度以上現れるという制約から、同じ数である項はちょうど 1 組であることが分かります。

これがヒントになるようだ

考察

簡単な例
  • 入力値(1 だけ重複している)
3
1 2 1 3
  • 部分列を作ったときの状況

部分列の要素数n 状況 重複を見つける
1 4つのカードから1つを選ぶ組み合わせ(= 4C1 = 4)だったら簡単なのだが、1個重複があるので3通り {1}の要素は明らかに2回数えられている(=選び方が一意ではない)
2 4つのカードから2つを選ぶ組み合わせ(= 4C2 = 6)だったら簡単なのだが、1個重複があるので5通り {1, 3}の要素は明らかに2回数えられている(=選び方が一意ではない)
3 4つのカードから3つを選ぶ組み合わせ(= 4C3 = 4)だったら簡単なのだが、重複はないので 4通り N/A
4 4つのカードから4つを選ぶ組み合わせ(= 4C4 = 1)だったら簡単なのだが、重複はないので 1通り N/A

上記から、n+1 C r から重複分を除けば答えになりそうだとわかる(※問題出されたときにわかるかと言われると、う〜ん…)

重複を取り除くパターン

数列 a_n が以下のように与えられるとする、赤字が重複

index 0 1 2 3 4 5 6
1 2 3 4 5 3 6

ここから要素を1つだけ取得して並べるやり方は明らかすぎるので考えない、要素を2つ取得して並べる方法を樹形図にしてみた

f:id:panzer-jagdironscrap1:20180610122107p:plain

  • この図から、重複したものを選び出す場合の数は
    • {}_3 C _1 となることがわかる(※重複した要素の外にある3つの値{1,2,6}から1つを選び出す場合の数。3を選ぶことは確定しているので1つを選び出す場合の数となる。)
  • ここから一般化すると、組み合わせの式は
    • "重複した要素の外にある要素数" から "並べる部分列の要素数 - 1"
    • とりあえず考察要素に関してはこれで終わりで、後は考察した組み合わせの式をより早いオーダーで実行しなければいけません。

*1:modular exponentiation = 冪剰余