競技プログラミング練習記 No.52【ABC110練習】


初回 -> [はじめに](https://qiita.com/easychoco/items/a9ae28aca97cfe47091f)

[ABC110](https://atcoder.jp/contests/abc110)を解きました。
3完です！
D問題は解説をみて解きました。

|問題|時間|アルゴリズム|実行時間
|:-:|:-:|:-:|:-:|
| A |  1min |-| 10ms|
| B | 18min |-|  7ms|
| C | 12min |文字列変換| 12ms|
| D | - |数え上げ| 12ms|

# まとめ
先にまとめを載せます。これ自体は最後に書いてます。

最大値と最小値を知りたいだけの場合はソートは必要ありません。
`std::max_element()`と`std::min_element()`を使った方が速く処理できます。

D問題解きたかった。
まだ理解しきれてなくて説明難しかったですごめんなさい。。。

## A - Maximize the Formula
```c++
  int a, b, c;
  cin >> a >> b >> c;
  cout << max({a, b, c}) * 10 + (a + b + c) - max({a, b, c});
```
`[一番大きい数字 * 10] + [残りの2つの数字]`
が答えになりますね。
コードはむりやり1行で書いているため分かりにくいかもしれませんが、上で書いたことをやっています。

## B - 1 Dimensional World's Tale
``` c++
  int n, m, nx, ny;
  cin >> n >> m >> nx >> ny;
  vector<int> x(n), y(m);
  for(int i = 0; i < n; ++i) cin >> x[i];
  for(int i = 0; i < m; ++i) cin >> y[i];

  sort(x.begin(), x.end());
  sort(y.begin(), y.end());

  bool ans = true;
  int z = x.back() + 1;
  if (z == nx) z++;

  ans &= (z <= y[0]);
  ans &= (z <= ny);

  cout << (ans ? "No War" : "War");
```
`Z`について、
(1) `数列x`と`X`を基準にして作ったもの
(2) `数列y`と`Y`を基準にして作ったもの
の2通りの作り方がありますね。

条件はそれぞれ
(1) は`数列xの最大の数より大きい` かつ `Xではない` 
(2) は`数列yの最小の数以下` かつ `Y以下`
になります。

この2通りの作り方(条件)を満たす`Z`があれば、答えは`No War`になります。
コードでは(1)でできる最小の`Z`を作り、それが(2)の条件を満たすかを判定しています。
余談ですが、最大値と最小値を知りたいだけの場合はソートは必要ありません。
`std::max_element()`と`std::min_element()`を使った方が速く処理できます。

## C - String Transformation

``` c++
string trans(string s)
{
  string s_tr = string(26, '0');
  string trans_s = "";

  int now = 0;
  for(int i = 0; i < s.length(); ++i)
  {
    int ind = (int)(s[i] - 'a');
    if (s_tr[ind] == '0')
    {
      s_tr[ind] = (char)(now + 'a');
      now++;
    }
    trans_s += s_tr[ind];
  }
  return trans_s;
}

void solve()
{
  string s, t;
  cin >> s >> t;

  cout << (trans(s) == trans(t) ? "Yes" : "No");
}
```
文字列を変換する問題ですね。
2つの文字列に共通の変換をして、同じ文字であれば答えが`Yes`になります。

その変換とは、
・文字列を先頭から見て、新しい文字が出るたびに`a,b,c,...`の順に変換する
・前に出た文字だったら、前に出た時と同じ文字に変換する
というものです。

例えば入力例1について、
`s = azzel`
`t = apple`
ですね。
`s`について、
1文字目の`a`をみて、新しい文字なので`a`に変換します。
2文字目の`z`をみて、新しい文字なので`b`に変換します。
3文字目の`z`をみて、2文字目と同じ文字なので、2文字目と同じ`b`に変換します。
4文字目の`e`をみて、新しい文字なので`c`に変換します。
5文字目の`l`をみて、新しい文字なので`d`に変換します。
これにより`s = abbcd` となります。
`t = apple`についても同じ変換をすると `t = abbcd`となります。
変換後の文字列が同じになったので、この入力例の答えは`Yes`です。


## D - Factorization
こちらのライブラリを使っています。
https://github.com/atcoder/live_library/blob/master/mint.cpp
https://github.com/atcoder/live_library/blob/master/comb.cpp

``` c++
  ll n, m;
  cin >> n >> m;
  if (n == 1 || m == 1)
  {
    cout << 1;
    return;
  }

  map<ll, ll> primes;
  ll factor = 2;
  while(factor * factor <= m)
  {
    if (m % factor == 0)
    {
      primes[factor]++;
      m /= factor;
    }
    else ++factor;
  }
  primes[m]++;

  mint ans = 1;
  for(const auto& p : primes)
  {
    ans *= c(p.second + n - 1, n - 1);
  }
  cout << ans;
```
約数の問題なのでまずは素因巣分解をしましょう。
$M =24 = 2^3 \times 3, N=3$ の時を考えます。
まずは$2^3$について考えます。
$ M^{'} = 8, N = 3$とすると、
`1,1,8`
`1,2,4`
`2,2,2`
を並び替えたものが答えになりますね。
現時点で、数列の`N`個の積は`8`になっています。

出てくる数字はすべて`2`の累乗数なので、指数で考えます。
すると、
`0,0,3`
`0,1,2`
`1,1,1`
になります。
よく見ると各数列の和が`3`になっていますね。この`3`は $8 = 2^3$ の `3` に一致します。
このとき、並べ方は3個のボールと2個の仕切りを並べ替える組み合わせに一致します。
つまり、[重複組み合わせ](https://www.google.com/search?ei=YMMXX-q5OJr6wQPGs6jICQ&q=%E9%87%8D%E8%A4%87%E7%B5%84%E5%90%88%E3%81%9B&oq=chouhukukumiawase)の問題に帰着できます。
これを一般化すると、
$N = n, M = m^a$ のとき、$_n H _a =\ _{n + a - 1} C _{n - 1}$ となります。


続けて $M=24$ について考えます。
$M$ が合成数の時、実は素因数ごとに独立して計算できます。

......もう少し具体的に。
$M^{'} = 2^3$ とした時と同様に $M^{''} = 3$ について考えます。
この組み合わせは
`1,1,3`
を並び替えたものですね。
この数列の`N`個の積は`3`です。

この$M^{''}$の数列の各項と、$M^{'}$で作った数列の各項と掛けることを考えてみます。
すると、できる数列の`N`個の積は`24`になりますね。
また、とりうる組み合わせの数も掛け合わせたものに一致することがわかります。

以上より、求める答えは
$M = p_1^{\ a_1}p_2^{\ a_2}p_3^{\ a_3}p_4^{\ a_4}...$
として、
$\_n H_{a_1} \times \_n H_{a_2} \times \_n H_{a_3} \times \_n H_{a_4} \times ... = \ \_{n + a_1 - 1} C_{n - 1} \ \times \_{n + a_2 - 1} C_{n - 1} \ \times \_{n + a_3 - 1} C_{n - 1} \ \times \_{n + a_4 - 1} C_{n - 1} \ \times ...$
で計算できます。

以上です。ありがとうございました。