ABC 165 C - Many Requirements

atcoder.jp

毎回至らなさしか感じていないが圧倒的にこなしてる数が足りていないので粛々と向き合い続けるしかない. 道具としては一度くらいは触ったことがあるものでもセンスが良いほうでもないので応用が効かず解法を覚えていくしかないように思う.とはいえまだまだやれることは多い.

初手の方針

全列挙しても間に合うことは条件から明らかだった.1以上M以下の全ての数字についてbit全探索してbitがN立っているものを抽出するというかなり強引な方法を取ったが出力例2と一致せず.条件は で(1,1,1)みたいなパターンが考慮できていないことに気づいた.ここでbit全探索は捨てたがforループを10週する以外の方法が思い浮かばず.

正答

Submission #12677663 - AtCoder Beginner Contest 165

深さ優先探索で数列を列挙する.こういう使い方もできるのね,,,まだまだ使いこなせてない. 難しかったのが長さが未定の2次元vector vector<vector<ll>> vv; のつくり方,入れ子になっているvector<ll>についてはN桁なので長さNで良いが数列の組み合わせがいくつある確定できず苦労した.解説を見ると実は予め決められるようだが本番中はそこまで考察を進めることができなかった.先に長さを決定する方法以外にも深さ優先探索であれば深さ方向にN桁の数値が1つずつ確定していくので,別途vector<ll> vを用意して桁数がNに到達したらvv.push_back(v)としていけば長さが未定のまま全ての組み合わせを洗い出すことができる.

以下のように後ろの桁(深いほう)から先に走査していくので上記のようなことが可能.幅優先探索だと3桁目を走査する前に2桁目が上書きされてしまうのでこの方法は採用できない.

1 1 1 
1 1 2 
1 1 3 
1 1 4 
1 2 2 
1 2 3 
1 2 4 
1 3 3 
1 3 4 
1 4 4 
2 2 2 
2 2 3 
2 2 4 
2 3 3 
2 3 4 
2 4 4 
3 3 3 
3 3 4 
3 4 4 
4 4 4