ABC114 参加記録＆解説

CもDも手間取ってしまい54位…

f:id:betrue12:20181202215621p:plain

A - 753

解法

ifや3項演算子などで場合分けしましょう。

ACコード

B - 754

解法

$S$ の長さが短いので、全部試すことができます。文字列から数値への変換は、C++だと stoi などを使うと便利です。

ACコード

C - 755

解法

こういう問題形式を見ると桁DPと思ってしまうのですが、まあ300点問題でそれはないですね…

$1 \le N \lt 10^{9}$ なので、 $N$ 以下の全ての整数を調べることはできません。ただ、 $7, 5, 3$ のみで構成される整数に絞ると候補がぐっと少なくなります。

桁数が $d$ で $7, 5, 3$ からなる整数は $3^{d}$ 個あります。候補となる値の桁数は $N$ が最も大きいときで3～9桁なので、 $3^{3} + 3^{4} + \cdots + 3^{9}$ 個、計算すると $29511$ 個しかありません。これは全探索できますね。

実装においてはまず桁数 $d$ を1つずつ見ていって、それぞれの整数列挙には3進数を用いるとよいです。候補を全て列挙して、「 $N$ 以下か？」「 $7, 5, 3$ が全て使われているか？」をチェックすればよいです。

ACコード

3進数の実装について少し補足します。コード中で trits という変数で書いているのが3進数の値で、列挙される整数（ $7, 5, 3$ からなる $d$ 桁の整数）と1対1対応しています。3進数の各桁の $0, 1, 2$ が $3, 5, 7$ にそれぞれ対応します（int arr[3] = {3, 5, 7}; で表現しています）。

例えば $d = 3$ で $trits = 21$ のとき、 $21 = 2 \times 3^{2} + 1 \times 3^{1} + 0 \times 3^{0}$ であることからこれは3進数表記すると 210 であり、この値は $753$ に対応しています。（桁数が違うと同じ3進数の値でも対応する整数が異なるので注意してください）

D - 756

解法

正整数の約数の個数は、その値の素因数分解と密接に関わっています（参考リンク）。具体的には素因数ごとに個数を数えて、その個数が $n_{1}$ 個、 $n_{2}$ 個、... $n_{k}$ 個だったとすると、約数の個数は $(n_{1}+1) \times (n_{2}+1) \times \cdots \times (n_{k}+1)$ 個になります。

ということで、まずは $N!$ を素因数分解してしまいましょう。 $N \le 100$ なのでそんなに多くの素因数は登場しません。2から最大で97まで、それぞれの素因数ごとに何個含まれているかが計算できます。

小さいほうから $i$ 番目の素因数 $p_{i}$ の個数を $n_{i}$ と書くことにします。例えば小さい値 $N = 5$ で考えると、 $N!=120$ は以下のように素因数分解できます。

$i$	$p_{i}$	$n_{i}$
1	2	3
2	3	1
3	5	1

$N!$ の約数は、これらの素因数 $p_{i}$ それぞれについて「 0個以上 $n_{i}$ 個以下の範囲で、いくつ取るか」を考え、その素因数を全て掛け合わせたものになります。各素因数についての「いくつ取るか」の取り方の組1つが、約数1つに対応します。例えば先程の $N=5$ の例において、「2を2個、3を0個、5を1個」取るとすれば、これは120の約数20に対応します。この20の約数の個数は $(2+1) \times (0+1) \times (1+1) = 6$ 個です。

ということで、各素因数ごとに順番にいくつ取るかを考えていく数え上げDPができます。 $dp \lbrack i \rbrack \lbrack j \rbrack$ を「 $i$ 番目の素因数まで見た時に、それまでの約数の個数が $j$ であるような選び方の個数」とします。このとき $j$ は75の約数だけを考えれば十分です。

遷移は以下のようになります。 $i-1$ 番目の素因数まででできた約数が $d_{1}$ 個で、 $i$ 番目の素因数を $d_{2} - 1$ 個選ぶ、という選び方に対応しています。

75の約数 $d_{1}, d_{2}$ について、 $n_{i} + 1 \ge d_{2}$ であれば $dp \lbrack i-1 \rbrack \lbrack d_{1} \rbrack$ を $dp \lbrack i \rbrack \lbrack d_{1}d_{2} \rbrack$ に加算する。