ABC202 D 解答
D - aab aba baa（966）
問題
問題文
A 個の a と B 個の b からなる長さ A+B の文字列のうち、辞書順で K 番目のものを求めてください。
制約
1 ≤ A, B ≤ 30
A 個の a と B 個の b からなる長さ A + B の文字列の総数を S 個とおいたとき、1 ≤ K ≤ S
入力は全て整数である。
考察
辞書順の問題です。
ABCのD問題ですので、「全部調べる」という方法では正解できません。A,Bが30まであるみたいですので、合わせて60個ですね。それを、並び替える組み合わせは
60! / (30!*30!) = 60_C_30 ≃ 10^17
らしいです。さすがに厳しいですね。
ですので、今回は先頭から効率よく決めていきましょう。例も用いて考えていきます。
例）5 2 17
です。
aaaaa
bb
を並び替えたときの17番目の数です。総数は21あるそうです。
さて、まずは仮に先頭を a と仮定してみましょう。
仮定：a
残り： aaaa bb
ですね。この残りで表現できるものを辞書順に全部書き出してみましょう。
１ a : aaaabb
２ a : aaabab
３ a : aaabba
４ a : aabaab
５ a : aababa
６ a : aabbaa
７ a : abaaab
８ a : abaaba
９ a : ababaa
１０ a : abbaaa
１１ a : baaaab
１２ a : baaaba
１３ a : baabaa
１４ a : babaaa
１５ a : bbaaaa
この15通りです。ただし、今回欲しいのは20番目の数です。例の通り一文字目が a ですと20番目の数は残念ながら現れません。ということで、一文字目は b でなくてはいけません。
また、一文字目が b で始まる文字列は先ほどの15番目の文字列の次にきますので、残りをどんなに早い順番で並べても16番目からとなってしまいます。15個分先を越されてしまったわけです（この計算に関しては後述します）。
決定 ：b
残り：aaaaa b
現在：15番目まで予約済み
ですので、カウントは16からスタートです。先ほど決定した b の次に a を仮定してみましょう。
決定：b
仮定：a
残り：aaaa b
現在：15番目まで予約済み
１６ b：a：aaab
１７ b：a：aaba
１８ b：a：abaa
１９ b：a：baaa
この４通りです。ですが、見てみると目標としていた17は超えてしまっています。今は a と仮定していますが、上と同様に２番目を b としてしまった場合にはその文字列は１９番目より後から始まります。通り過ぎてしまいましたね。
ですので、２文字目は a で決定されます。ただしこのとき、先ほどと違うのは予約番号に変更はないということです。ここに注意です。
どんどん行きましょう。３文字目です。同様にaと置いてみます。
決定：ba
仮定：a
残り：aaa b
現在：15番目まで予約済み
１６ ba：a：aab
１７ ba：a：aba
１８ ba：a：baa
これも先ほどと同じですね。a で固定しましょう。そして4文字目です。
決定：baa
仮定：a
残り：a b
現在：15番目まで予約済み
１６ baa：a：ab
１７ baa：a：ba
今回はぴったりですね。ここです。なのですが、実装の都合上これも超えてしまったとしてしまいます。5文字目です。
決定：baaa
仮定：a
残り：b
現在：15番目まで予約済み
１６ baaa：a：b
今度は届きませんでしたね。ですので、1文字目と同じようにaを固定しましょう。予約番号も16になりました。
決定：baaab
仮定：a
残り：
現在：16番目まで予約済み
１7 baaab：a：
またぴったしです。これも前と同じように超えたとしてaを固定しましょう。さて、７文字目です。と言いたのですが、もうa も bも残っていません。ということで、現在決定されている
baaba
が晴れて17番目の文字列となるわけです。今回は先に b がなくなりましたが、もしa が先になくなった場合には残りは全部bで埋めてあげれば大丈夫です。
このように1文字ずつ先頭から決定していくと答えが求まります。決定の仕方をまとめますと、
予約番号＋残りの組み合わせ数が
１）K以上だったら（Kを含む）
a を決定する（予約番号はそのまま）
２）K未満だったら
b を決定する（予約番号を進める）
*）どちらかが0であるならば別の方を決定させる
これをaとbを全部並べ終わるまで行うと答えが求まります。
さて、説明を避けてきましたが
残りの組み合わせ数
についてです。これは
同じものを含む順列
というやつですね。高校数学ではお世話になりました。全てを区別できるものとして考えて、区別できないものの組み合わせ数で割ることにより求めることが可能です。式としては
(A+B)! / A! * B! = (A+B)_C_A
で求めることができます（冒頭にも書きましたね）。今回は a を決定した残りで計算しますので、 A-1 になることを忘れないようにしましょう。
以上を実装してあげればACがもらえます。
なのですが、実装において少し注意です。
上記の組み合わせの計算を愚直に実装してあげるとオーバーフローもしくは割り算の小数点以下の切り捨てが発生してしまいます。ですので、組み合わせを実装する際には分母、分子ともに小さいほうから順に計算しましょう。例を示します。
8_C_4 = 8*7*6*5 / (4 * 3 * 2 * 1) = 70
１）5 / 1
２）5 * 6 / (1 * 2) = 5 * 3 / 1
３）5 * 3 * 7 / (1 * 3) = 5 * 7 / 1
４）5 * 7 * 8 / (1 * 4 ) = 70 / 1 = 70
となって、都度割り算をしているのに必ず割り切ることができます。試しに逆からやってみましょう。
１）8 / 4 = 2 / 1
２）2 * 7 / (1 * 3)
となり、早くも割り切れなくなります。小さいほうからやるのが非常に重要です。
先にの方法にこの組み合わせ数を求める計算を合わせてあげることで無事ACがいただけます。実装に移ります。
実装
#include <bits/stdc++.h> #define rep(i,n) for(int i=0;i<n;++i) #define reps(i,s,n) for(int i=s;i<n;++i)
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
ll perm(ll a, ll b)
{
ll res = 1;
for (ll i = 1; i <= a; ++i)
{
res *= b + i;
res /= i;
}
return res;
}
int main()
{
int a, b;
ll k;
cin >> a >> b >> k;
ll now = 0;
string ans = "";
while (a+b > 0)
{
if (a == 0)
{
ans += 'b';
--b;
continue;
}
else if (b == 0)
{
ans += 'a';
--a;
continue;
}
ll next = perm((ll)a - 1, (ll)b);
if (now + next < k)
{
--b;
now += next;
ans += 'b';
}
else if (now + next >= k)
{
--a;
ans += 'a';
}
}
cout << ans << endl;
return 0;
}あとがき
小さいほうから計算すると割り切れることに関する説明です。
これは”必ず”割り切ることができます。それは分母が１から始まっていることが要因です。数字の列を考えていきますと、ある数を約数に持つ数ってその数だけ離れた場所に出現しますよね。例えば２でしたら、２、４、６のように２個だけ離れたところです。出現間隔が２とでも言いましょうか（間に１つの違う数字が入る）。コンビネーションの計算では小さい順に行うと、分母に２が出現するタイミングでは分子には２つの連続した整数がおかれています。つまり２を約数に持つ数が必ずいるということです。
これって、３、４、...でも同じことが言えるんです。ですので、小さい順に計算することで必ず割り切って計算することが可能となります。
私はコンテスト中にこの計算に結構てこずりました。いつもはmodで計算することが多く、ライブライにおんぶにだっこですので、このあたりの細かな気遣いとでも言いましょうか、が疎かになっていました。でもこれで、ちゃんと覚えました。次は大丈夫だと思います。
また、そもそもこれってオーバーフローが怖いから都度割りたいという話ですので、オーバーフローしなければいい話なのです。ということで、pythonなどの多倍長整数を使うというのも非常に賢い方法だと思います。
コンテスト中はミスなく速くACすることがなによりの正義となりますからね。
本問題よりもそこそこに難しいですが、辞書順の問題が最近のABCで出てましたので紹介します。この問題が解けて余裕のある方はぜひともこちらの問題にも挑戦してみてはいかがでしょうか。難しいですよ。
解説もありますよ
この記事が気に入ったらサポートをしてみませんか？