競技プログラミング練習記 No.40【エイシング プログラミング コンテスト 2020】

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

[エイシング プログラミング コンテスト 2020](https://atcoder.jp/contests/aising2020)に参加しました。
3完です！
D問題はコンテスト終了後に解きました。

|問題|時間|アルゴリズム|実行時間
|:-:|:-:|:-:|:-:|
| A |  2min |-| 6ms|
| B |  1min |-| 6ms|
| C |  8min |ヒストグラム| 37ms|
| D | - |mod| 146ms|


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

D問題
ボトルネックになっている処理をみつけてそこだけやる問題でした。
おもしろかったです。解けていませんが。。。

解き方はわかっていたのにREが出てコンテスト中に通せませんでした。

REはほとんが配列外参照か0除算が原因です。
今回も[%= 0] をしていたのが原因でした。
手ごたえはあったので、次回以降に期待です。

## A - Number of Multiples

```c++
  int l, r, d;
  cin >> l >> r >> d;
  cout << r / d - (l-1) / d;
```
「`R`以下の整数のうち`d`の倍数のもの」から「`L`未満の整数のうち`d`の倍数のもの」を引けば答えになりますね。
`(R - L) / d` でも出せそうですが、境界値でうまくいかないので注意です。

## B - An Odd Problem

``` c++
  int n;
  cin >> n;
  vector<int> a(n);
  int ans = 0;
  for(int i = 1; i <= n; ++i)
  {
    cin >> a[i];
    ans += ((i * a[i]) & 1);
  }
  cout << ans;
```
奇数同士を掛け合わせると奇数になりますね。
今回はそれを利用して、`i * a[i]`が奇数の場合、求める状態だといえます。
その個数を数えて答えです。

## C - 	XYZ Triplets

``` c++
  int n;
  cin >> n;
  vector<int> hist(n + 1, 0);
  for(int x = 1; x*x < n; ++x)
  {
    int x2 = x * x;
    for(int y = 1; y*y < n; ++y)
    {
      int y2 = y * y;
      int xy = x * y;
      if (x2 + y2 + xy > n) break;
      for(int z = 1; z*z < n; ++z)
      {
        int sum = x2 + y2 + z*z + xy + (x + y)*z;
        if (sum > n) break;
        hist[sum]++;
      }
    }
  }
  for(int i = 1; i <= n; ++i)
  {
    cout << hist[i] << endl;
  }
```
問題文にある`f(1), f(2) ... f(N)`を直接求めるのは大変です。
ここは逆に考えます。
`x^2 + y^2 + z^2 + xy + yz + zx` を先に計算して、出た数値をヒストグラムとしてカウントします。
計算結果が`10`になったら `f(10)`を1つ増やす、
計算結果が`12`になったら `f(12)`を1つ増やす、、、
というふうにして全探索をすると答えがわかります。

ちなみに、制約から`x,y,z`は最大でも100未満であることがわかるため、この全探索ができます。


## D - Anything Goes to Zero

``` c++
// a^n % mod を計算する O(log n)
ll powmod(ll a, ll n, ll mod) {
  ll ret = 1;
  while (n > 0) {
    if (n % 2 == 1) { ret = ret * a % mod; }
    a = a * a % mod;
    n /= 2;
  }
  return ret;
}

int calc(ll num, int depth)
{
  if (num == 0LL) return depth;

  int p_count = __builtin_popcount(num);
  return calc(ll(num % p_count), depth + 1);
}

void solve()
{
  ll n;
  string s;
  cin >> n >> s;

  ll p_count = 0;
  for(int i = 0; i < n; ++i) p_count += (s[i] == '1');
  ll rem_p1 = 0;
  ll rem_m1 = 0;

  for(int i = 1; i <= n; ++i)
  {
    if (s[n - i] == '1')
    {
      rem_p1 += powmod(2LL, i - 1, p_count + 1);
      rem_p1 %= (p_count + 1);

      if (p_count > 1) // popcount == 1 のとき [%= 0] になるので回避
      {
        rem_m1 += powmod(2LL, i - 1, p_count - 1);
        rem_m1 %= (p_count - 1);
      }
    }
  }

  for(int i = 0; i < n; ++i)
  {
    if (s[i] == '1')
    {
      if (p_count == 1)
      {
        cout << 0 << endl;
        continue;
      }
      ll rem = rem_m1 - powmod(2, n - i - 1, p_count - 1);
      rem = (rem + (p_count - 1)) % (p_count - 1);
      cout << calc(rem, 1) << endl;
    }
    else if (s[i] == '0')
    {
      if (p_count == 0)
      {
        cout << 1 << endl;
      }
      else
      {      
        ll rem = rem_p1 + powmod(2, n - i - 1, p_count + 1);
        rem = rem % (p_count + 1);
        cout << calc(rem, 1) << endl;
      }
    }
  }
}
```
mod計算を繰り返す問題です。入力値がとても大きいですね。

ここで、入力値の`popcount` を`P`とすると、`P`は最大でも200000です。
入力値は最大で`2^200000`ですが、1回目のmodを挟むと、最大でも`199999`です。
つまり、`int`の範囲内に収まります。そうなれば普通に計算できますね。

そこで、1回目のmodを考えます。
問題設定より、modをとる数は`P+1`または`P-1`の2通りですね。
前処理として、この2通りを入力値に対して計算します。
この値を`rem_p1, rem_m1`とします。

ここで、入力値の`i`番目のbitを0->1にした数値は `入力値 + 2^(n-i-1)` ですね。
このmodは `rem_p1 + 2^(n-i-1) mod P+1` で求まります。
mod の性質より、 `(rem_p1 mod P+1) + (2^(n-i-1) mod P+1) mod P+1` ですね。

入力値の`i`番目のbitを1->0にした場合のmodも同様に求められます。

この処理ができれば、`2^200000`あった入力値は`199999`以下に減ります。
ここまでくれば、dfsなどでそのまま計算して答えがわかります。
`2^(n-i-1) mod P+1` に時間がかかり、`O(N logN)`で求まります。



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