https://atcoder.jp/contests/abc201/tasks/abc201_c
解説
https://atcoder.jp/contests/abc201/submissions/22640379
根性計算、根性場合分けをする問題。
最近あんまり見ていなかったが、今回のように丁寧に場合分けをして解いていくような問題もある。
oの個数をused, xの個数をunused, ?の個数をunknownとして最初に計算しておこう。
答えが見つからないケース
最初に答えが見つからないケースを0で応答しておこう。
- usedが5個以上
- used+unknownが0個 → どうやっても使われている数字が1個以上にできない
実は計算ロジックで0が応答されるようになっていたという場合もよくあるが、
経験的には自明なコーナーケースは過剰であっても排除しておくと事故が少ない。
?の扱いをどうするか
?の扱いが問題になる。
今回は?の種類数は多くないので、?のうち何個をoにして使用するかを全探索しよう。
add個をoにするとすると、oになっている個数はused+add個となる。
これが1～4の場合は暗証番号を作ることができるので、組合せ計算ができる。
この場合にどの数字が選ばれたかというのは組合せ計算には関係がない。
ただ、どの数を?からoにしたかという部分で組み合わせ計算が発生するので、入れ替えによる組合せ計算×C(unknown,add)として計算しておく。
二項係数C(a,b)
自分の実装ではaCb(a,b)というのを用意している。
自分はこれをライブラリ化しているので使うだけ。
今回はパターンも少ないので、こちらも場合分けして事前計算された結果を返すようにしてしまっても問題ない。
公式通り計算してもいいし、AtCoder Libraryにももしかしたらライブラリがあるかもしれない。
ぐぐったら例コードが見つかるかも。
色々頑張る。
oになっている個数で場合分け
後は場合分け。
oになっている個数が分かれば、組合せ数が計算できる。
- oが1個 → 1111みたいなやつが1通り
- oが2個 → 1112みたいなやつが2×4通り（どっちを1個にするかで2通り、置き方が4通り）。1122みたいなやつがC(4,2)通り
- oが3個 → 1123みたいなやつが3×4×3通り（ダブって使う数字をどれにするかで3通りで、置き方がC(4,1)×C(3,1)通り）
- oが4個 → 1234みたいなやつが4!通り（置き方だけ）
string S; //--------------------------------------------------------------------------------------------------- ll solve() { int used = 0, unused = 0, unknown = 0; fore(c, S) { if (c == 'o') used++; else if (c == 'x') unused++; else unknown++; } if (4 < used) return 0; if (used + unknown < 1) return 0; ll res = 0; rep(add, 0, unknown + 1) { if (add + used == 0) continue; if (4 < add + used) continue; int cnt = used + add; if (cnt == 1) res += 1 * aCb(unknown, add); else if (cnt == 2) res += (2 * 4 + aCb(4, 2)) * aCb(unknown, add); else if (cnt == 3) res += 3 * 4 * 3 * aCb(unknown, add); else if (cnt == 4) res += 4 * 3 * 2 * aCb(unknown, add); } return res; } //--------------------------------------------------------------------------------------------------- void _main() { cin >> S; cout << solve() << endl; }
