トップ 差分 一覧 ソース 検索 ヘルプ RSS ログイン

AtCoder Beginner Contest 066

[競技プログラミング,競プロ解説]

AtCoder Beginer Contest 066 - D

  解説

問題文から

 数の種類が 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 から重複分を除けば答えになりそうだとわかる
  • いかにして重複分を除くか
    • そこは解説を見れば明確、与えられる数列に対して重複は1種類2要素なのでその条件で例示を行いパターンを読み解く

重複を取り除くパターン

数列 a%5Fn が以下のように与えられるとする、太字が重複

index 0 1 2 3 4 5 6
1 2 3 4 5 3 6
  • ここから要素を1つだけ取得して並べるやり方は明らかすぎるので考えない、要素を2つ取得して並べる方法を樹形図にしてみた
  • この図から、重複したものを選び出す場合の数は
    • %7B%7D%5F3+C+%5F1+ となることがわかる(※重複した要素の外にある3つの値{1,2,6}から1つを選び出す場合の数。3を選ぶことは確定しているので1つを選び出す場合の数となる。)
  • ここから一般化すると、組み合わせの式は
    • "重複した要素の外にある要素数" から "並べる部分列の要素数 - 1"

とりあえず考察要素に関してはこれで終わりで、後は考察した組み合わせの式をより早いオーダーで実行しなければいけません。

計算量を減らす

  • どうやらどちらのコードもnCr(nCk)の計算を何らかの方法で計算量を削減している
;; 逆関数(f^-1のこと)
Function inverse (n)

;; 階乗
Function factorial (n)

;; 組み合わせ
Function choose(n, k)

abc066.png
お名前: コメント: