AtCoder Beginner Contest 025 D : 25個の整数

abc025.contest.atcoder.jp

当初の方針

分からない・・・。
全体の数(0の数の階乗)からルール違反のものを引いていくのかな。
でも重複があるし、それを取り除けなさそう・・・。

諦め

解説をみて

1から置いていく、という発想が大事だったっぽい。
すでにビットが立っているものは今より小さい数ということを頭に入れて、
矛盾が生じるケースになってないかチェックして
遷移していけばいい。
入力のときすでに置いてあるやつ => 置く場所が決まっている
ということ。

トポロジカル順序は立っているビットの数が小さい順(大きい順)
なぜなら今置こうとする数 = popcount(bits) + 1だから

もらうDPが苦手なので配るDPにしたのだけれど、
MLE & TLEをもらってしまった・・・。
実装がTreeSetだからlog Nかかってしまうし、場所も取る。
O(1)で立っているビットの数が小さい順にループする
みたいなことできなかったっけ・・・?

Submission #984345 - AtCoder Beginner Contest 025 | AtCoder

もらうDP(メモ化再帰)を書いてAC。

Submission #984370 - AtCoder Beginner Contest 025 | AtCoder

O(1)で立っているビットの数が小さい順にループする

探していたものがこれだった

Generating Binary Permutations in Popcount Order - Alex Bowe

これで配るDPでACできる。

Submission #984397 - AtCoder Beginner Contest 025 | AtCoder