D - Handstand 2
分かったら簡単なんだけど…
何を足すか?を考える
考察(自分の場合)
AとBを決めるのか…
全ての組み合わせを全列挙していたら間に合わないので、Aだけ全て試して、それに対応するBを計算を使って頑張って求めていった
Aを決めた時、Bの先頭文字topと後尾の文字bottomは計算できる(to_stringで変換するとよさそう…)
N=751823とします
先頭がtopで、後尾がbottomな数字は、桁数がNの桁数未満であれば内側はフリーになる(000~999のようにできる)ので、10の中身の桁数乗、みたいにまとめて計算することができる
例:20003 とか 29993 とか 23とか 343 とか (1桁の場合は分けて考えた…)
桁数がNの桁数と同じになった時に作れる文字の数は、先頭の数字がNの先頭の数字より大きい/同じ/小さいか、後尾の数字がNの後尾の数字より大きい/以下かで場合分けができる
先頭が小さい…299994(自由) 逆に、先頭が大きいと不可能(既に越しているので)
先頭が等しくて、
後尾が以下…最大で7「5182」3とか7「5182」1までいける
後尾が大きい…最大で7「5181」6とか7「5181」9までいける
こんな感じで気合で怒涛の場合分けをして、計算で求めます
いい解法
1~Nまで走らせながら「count[i][j]…先頭がiで、後尾がjである数字の数」をカウントしていく。
そのあと、さっき用意したcountを使って、Aに対してのBの数を数えればいい…
楽
足すものの共通点は何…?というのをちゃんと考えていたら思いついたかもしれないけど…