AtCoder - AtCoder Beginner Contest 066 (11) を解いてみた
ABC 040 D問題に使われるアルゴリズム要素は組み合わせ、繰り返し２乗法、階乗のmod逆元、（＋累積和的な処理？）です。組み合わせ(nCr)については、以前動的計画法によるアルゴリズムを紹介しましたが
nantonaku-shiawase.hatenablog.com
AtCoderではこれでもまだ処理が遅くACが取れませんでした。
組み合わせ
繰り返し２乗法や階乗のmod逆元については、他でもいろいろ解説があるので言及しません。しかし、組み合わせの処理にてなぜそれらを使わなければいけないか書いておきます。
組み合わせを階乗の式で表す
Rubyとかだと配列クラス(Array)に#combinationメソッドが用意されておりすぐに求められるのですが、競技プログラミングの場合これでは遅すぎます。いったん組み合わせ(Combination)がどのような式で構成されていたか確認してみましょう。
組み合わせの式
以下のようなものになります、nの階乗をrの階乗と(n-r)の階乗で割ったものでした
- 参考：組合せ
この、階乗の数値が巨大なものになってもすばやく計算する方法が繰り返し２乗法で、巨大な階乗の逆数を求める方法が階乗の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)だったら簡単なのだが、１個重複があるので3通り | {1}の要素は明らかに２回数えられている(=選び方が一意ではない) |
| 2 | 4つのカードから2つを選ぶ組み合わせ(= 4C2 = 6)だったら簡単なのだが、１個重複があるので5通り | {1, 3}の要素は明らかに２回数えられている(=選び方が一意ではない) |
| 3 | 4つのカードから3つを選ぶ組み合わせ(= 4C3 = 4)だったら簡単なのだが、重複はないので 4通り | N/A |
| 4 | 4つのカードから4つを選ぶ組み合わせ(= 4C4 = 1)だったら簡単なのだが、重複はないので 1通り | N/A |
上記から、n+1 C r から重複分を除けば答えになりそうだとわかる（※問題出されたときにわかるかと言われると、う〜ん…）
重複を取り除くパターン
数列 が以下のように与えられるとする、赤字が重複
| index | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|---|
| 1 | 2 | 3 | 4 | 5 | 3 | 6 |
ここから要素を１つだけ取得して並べるやり方は明らかすぎるので考えない、要素を２つ取得して並べる方法を樹形図にしてみた
- この図から、重複したものを選び出す場合の数は
となることがわかる（※重複した要素の外にある３つの値{1,2,6}から1つを選び出す場合の数。3を選ぶことは確定しているので1つを選び出す場合の数となる。）
*1:modular exponentiation = 冪剰余
AWS Glue上でboto3を使ってみる
Clojure小ネタ
Clojure小ネタ
Clojureのテストはrepl.itというサイトでWEB上で試せる
repl.it - Online REPL, Compiler & IDE
ハッシュマップの型
- {:key "value"} のような形のハッシュマップは、内部ではPersistentHashMapやPersistentArrayMap, PersistentTreeMapのような型を持ちます。
Clojure 1.8.0 Java HotSpot(TM) 64-Bit Server VM 1.8.0_91-b14 (def m {:no "1" :name "山田" :tel "xxx-xxx-xxxx"}) => #'user/m (println m) {:no 1, :name 山田, :tel xxx-xxx-xxxx} => nil (println (type m)) clojure.lang.PersistentArrayMap => nil
マップの操作
- キー/バリューの取り出し
- keys, vals が使える
(vals m) => ("1" "山田" "xxx-xxx-xxxx") (keys m) => (:no :name :tel)
- 順序を変えた取り出し
(map (fn [key] (key m)) [:no :name :tel]) => ("1" "山田" "xxx-xxx-xxxx") (map (fn [key] (key m)) [:tel :name :no]) => ("xxx-xxx-xxxx" "山田" "1")
- キーの削除
- dissoc を使う
(dissoc m :no) => {:name "山田", :tel "xxx-xxx-xxxx"}
- 複数キーの削除
apply を使うとうまくいくapply無しでも動きました、何かと勘違いしていた？
(dissoc m [:no :name]) => {:tel "xxx-xxx-xxxx"}
