競技プログラミング練習記 No.35【ABC173参加】

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

[ABC173](https://atcoder.jp/contests/abc173)に参加しました。
4完です！

|問題|時間|アルゴリズム|実行時間
|:-:|:-:|:-:|:-:|
| A |  1min |-| 7ms|
| B |  2min |std::map|18ms|
| C | 26min |bit全探索| 7ms|
| D | 16min |完全二分木|49ms|

Eは解けそうで解けなかったです。しっかり場合分けをする問題でした。
悔しい。復習します。

## A - Payment
```c++
  int a;
  cin >> a;
  cout << (1000 - (a % 1000)) % 1000;
```
1000円札で払った時のお釣りを計算する問題です。
`(1000 - (a % 1000))`で計算できるのですが、お釣りが0円になるときにバグるので`% 1000`で調整しています。

## B - 	Judge Status Summary
``` c++
  int n;
  cin >> n;

  map<string, int> ans;
  for(int i = 0; i < n; ++i)
  {
    string s;
    cin >> s;
    ans[s]++;
  }
  cout << "AC x " << ans["AC"] << endl;
  cout << "WA x " << ans["WA"] << endl;
  cout << "TLE x " << ans["TLE"] << endl;
  cout << "RE x " << ans["RE"] << endl;
```
連想配列を使って解きました。

## C - 	H and V
``` c++
  int h, w, k;
  cin >> h >> w >> k;
  string c[6];
  for(int i = 0; i < h; ++i)
  {
    cin >> c[i];
  }

  int all_blacks = 0;
  vector<int> h_num(h, 0);
  vector<int> w_num(w, 0);
  for(int i = 0; i < h; ++i) {
    for(int j = 0; j < w; ++j) {
      if (c[i][j] == '#') {
        h_num[i]++;
        all_blacks++;
      }
    }
  }
  for(int i = 0; i < w; ++i) {
    for(int j = 0; j < h; ++j) {
      if (c[j][i] == '#') w_num[i]++;
    }
  }

  int ans = 0;
  int mask = 1 << (h + w);
  while(mask--, mask >= 0)
  {
    int h_mask = mask >> w;
    int w_mask = (mask & 0b111111);

    int h_hidden_num = 0;
    int w_hidden_num = 0;
    for(int i = 0; i < h; ++i) {
      if (( h_mask & (1 << i) ) > 0) h_hidden_num += h_num[i];
    }

    for(int i = 0; i < w; ++i) {
      if (( w_mask & (1 << i) ) > 0) w_hidden_num += w_num[i];
    }

    int rest_num = all_blacks - h_hidden_num - w_hidden_num;
    for(int i = 0; i < h; ++i)
    {
      if ( (h_mask & (1 << i) ) == 0) continue;
      for(int j = 0; j < w; ++j)
      {
        if ( (w_mask &  (1 << j) ) == 0) continue;
        rest_num += (c[i][j] == '#');
      }
    }
    ans += (rest_num == k);
  }
  cout << ans;
```
（よくわからなかったので）全探索しました。
制約から、bit全探索が使えますね。

各列と各行に含まれる`#`の数をそれぞれ計算して記憶しておきます。

`mask`は、
・`1~w`桁が各列を塗るかどうか
・`w+1~w+h`桁が各行を塗るかどうか
を示しています。

また、
`[塗られていない黒の数] =
[全体の黒の数]
 - [塗った列に含まれていた黒の数] - [塗った行に含まれていた黒の数]
 + [塗った行と列の両方に含まれている黒の数]`
です。包除原理というやつですね。
ですが、こんなややこしいやり方をしなくても、「塗られていなければ個数を追加」という解き方にすればシンプルでスマートに解けましたね。
なぜ思いつかなかったのか。反省。

実行速度が遅いかなと思っていたら早かったので、制約に助けられました。

## D - Chat in a Circle


``` c++
  int n;
  cin >> n;
  vector<ll> a(n);
  for(int i = 0; i < n; ++i)
  {
    cin >> a[i];
  }
  sort(a.begin(), a.end(), greater<ll>());

  ll ans = a[0];
  int add_cnt = 1;
  int index = 1;
  while(add_cnt < n - 1)
  {
    ans += a[index];
    add_cnt++;
    if (add_cnt < n - 1)
    {
      ans += a[index];
      add_cnt++;
    }
    index++;
  }
  cout << ans;
```
この問題はグラフに帰着できます。グラフの中でも[完全二分木](https://www.google.com/search?q=%E5%AE%8C%E5%85%A8%E4%BA%8C%E5%88%86%E6%9C%A8)を使います。
手元で試していたら思いつきました。

まず降順にソートして、一番大きい数を「取り除きます」。

残った要素を大きい順に使い、完全二分木を作ります。
新しい要素を木に追加するとき、加えられる中で一番大きな要素を親とします。
ちなみにできるグラフは[二分ヒープ](https://www.google.com/search?q=%E4%BA%8C%E5%88%86%E3%83%92%E3%83%BC%E3%83%97&oq=%E4%BA%8C%E5%88%86%E3%83%92%E3%83%BC%E3%83%97)でもありますね。
できた完全二分木の根について、初めに取り除いた数字を根の親にします。

このようにしてできたグラフを見ると、「各要素の親」の総和が求める答えになっていることがわかります。

上のプログラムは素の総和を求めるものになっています。

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