ABC041

バチャコン3回目です。初めてbitDPの問題に触れました。

A - 添字

提出コード
今回のA~Cはかなりシンプルでした。
A問題は、素直に文字列sのi番目の文字を出力すれば良いです。配列の最初が0になっていることだけ気を付ければ大丈夫です。

B - 直方体

提出コード
long long型で計算していき、一つの処理ごとにで割ったあまりをとれば良いです。

C - 背の順

提出コード
ソートの問題です。出席番号もセットで記録しておきたいので、pairを使うと楽です。

D - 徒競走

提出コード(時間外)
ということでD問題です。
とりあえず、部分点のテストケースならば、全探索が間に合いそうだったので全探索だけ書いておきました。
入力例3からもわかるように、満点解法は全探索を使わないことが明らかだったので、お手上げでした。
前から順番にうさぎの番号を決めていくときに、すでに決め終えたウサギの番号の集合をビットで表すと、うまくいきます(bitDPです)。
1の位から順にウサギの1番から割り振っていきます(最大16桁になります)。1をすでに並べ終えているとし、0がまだ並べ終えてないとします。例えば、
10011
は、1・2・5番目のウサギを並べ終えた状態です。
次に並べたいウサギの番号をjとし、現在のbitの状態をiとするときに、今の状態がどんな条件を満たしているとjのウサギを最後尾に並べることができるか、というと、

• iに含まれるウサギの中に、jより後ろにいるべきウサギが存在しない

という条件を満たすとき、並べることができます。
この条件を満たすとき、
dp[i+(1<<j)]+=dp[i]
となります。
また、dp[0]=1です。
あとはこれを数が少ない方から順に繰り返していけば答えがもとまります。
bitを使う方法は思い浮かびましたが、それとDPを繋げる発想がありませんでした。