htkb-proconの日記

初心者がPythonで問題解いた記録

ABC041-D bitDP

D: 徒競走 - AtCoder Beginner Contest 041 | AtCoder

この問題、解説見てもACコード見てもプロい人のブログとか見ても、お願いだから日本語書いて?って感じで困っていたのだけど、このブログの

感覚的には空集合の場合の数から全集合の場合の数へ、集合の数を増やす感じに計算していく。 http://mmxsrup.hatenablog.com/entry/2016/07/03/142548

この文から取っ掛かりが得られたので、海より深く感謝しながら実際に解いてる最中に考えたことを書き残しておきます。


dpの回し方としてはdp[0] = 1空集合)から始め、立ったビットのdpテーブルにビットが立つ前のdpテーブルの値を加算していく流れになるのかな?dp[01] += dp[0], dp[10] += dp[0], dp[11] += dp[01] + dp[10], …こんな感じに。

まず問題をシンプルにするために、bitDPで全ての順列の数をdpテーブルに書き込んでみる。

N = int(input())
bit_max = 1<<N
dp = [0]*(bit_max)
dp[0] = 1

for bitset in range(bit_max):
    for usa_num in range(N):
        usa_bit = 1 << usa_num
        if bitset & usa_bit:
            dp[bitset] += dp[bitset-usa_bit]
print(dp)

このコードに3を与えてみると

[1, 1, 1, 2, 1, 2, 2, 6]

が出力される。3匹の中から3匹を選ぶ順列の数3P3 = 3!/(3-3)! = 6なので合っている。このコードを実行すると、dpテーブルは以下のような遷移をしているはず:

f:id:htkb:20170605211438j:plain

冒頭の問題に戻ると、上の遷移がゴールの早いうさぎ順に順番を決めているとするならば、集合を増やしていく過程で自分よりも先にゴールしたうさぎを全て含まない状態への遷移はありえない。例えば

3 2
2 1
3 1

のテストケース、うさぎが3匹で1のうさぎより2,3のうさぎのほうが早かった場合、1が初めて出てくる集合は{1, 2, 3}しかない。{}から{1}への遷移は、うさぎ1が1等だった場合の順列を数えようとしており、このような条件に合わない遷移を除外する。 f:id:htkb:20170605213734j:plain

んでそれをどう判定すんのか。自分より早いうさぎをあらかじめビット列で取っておき、

(自分より早いうさビット列) & (今のビット列から自分自身を引いたもの) == (自分より早いうさビット列)

というやり方をこのACコードからパクりました考えた。自分より早いうさぎの集合⊆現在の集合になっているかを見ているわけね。

最終的なACコードはこれ:Submission #1333411 - AtCoder Beginner Contest 041 | AtCoder