競技プログラミング練習記 No.43【ABC119練習】

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

[ABC119](https://atcoder.jp/contests/abc119)を解きました。
4完です！

|問題|時間|アルゴリズム|実行時間
|:-:|:-:|:-:|:-:|
| A |  2min |-|  9ms|
| B |  4min |-|  6ms|
| C | 44min |全列挙| 17ms|
| D | 37min |二分探索| 68ms|


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

制約が小さいときは全列挙が選択肢に入ります。

数直線上での位置を探すときは二分探索が使えます。

水色diffの問題が2問ある構成でしたが、どちらも解けました。嬉しい。
しかもD問題について、提出時のC++ (GCC 9.2.1)で解いた人の中で実行速度が2番目に速かったです。嬉しい。



## A - Still TBD

```c++
  string s;
  cin >> s;
  cout << (s[5] == '0' && (s[6] - '0') <= 4 ? "Heisei" : "TBD");
```
年と日は関係なく、月だけ見れば答えがわかりますね。
6,7番目の文字（0-indexだと5,6番目）に月がくるので、その部分を判定します。
`char`型は内部的に文字コードを数値として持っています。
これを利用して、`s[6] - '0'`で文字→数値の変換ができます。

## B - Digital Gifts

``` c++
  int n;
  double x;
  string u;
  cin >> n;
  double ans = 0;
  for(int i = 0; i < n; ++i)
  {
    cin >> x >> u;
    ans += (u == "JPY" ? x : x * 380000.0);
  }
  printf("%.7f\n", ans);
```
JPYだったらそのまま足して、BTCだったらレートをかけましょう。
精度に不安があったのですが、`10^-5`以下の誤差は許容とあったので助かりました。
許容誤差が`10^-9`とかだったら丸め誤差を意識した書き方になっています。

## C -Synthetic Kadomatsu

``` c++
  int n, a, b, c;
  cin >> n >> a >> b >> c;
  vector<int> l(n);
  vector<int> target{a, b, c};
  for(int i = 0; i < n; ++i)
  {
    cin >> l[i];
  }

  sort(l.begin(), l.end());
  sort(target.begin(), target.end());

  int ans = 1 << 30;
  do
  {
    do
    {
      int ti = 0;
      int cost = 0;
      int now_len = 0;
      for(int li = 0; li < n; ++li)
      {
        if(ti >= 3) break;
        now_len += l[li];
        int guchoku_cost = abs(now_len - target[ti]);
        int gattai_cost = (li + 1 < n) ? abs(now_len + l[li + 1] - target[ti]) + 10 : 1000000;

        if (guchoku_cost < gattai_cost)
        {
          cost += guchoku_cost;
          now_len = 0;
          ti++;
        }
        else
        {
          cost += 10;
        }
      }
      if (ti >= 3)
      {
        ans = min(ans, cost);
      }
    } while(next_permutation(l.begin(), l.end()));
  } while(next_permutation(target.begin(), target.end()));
  cout << ans;
```
問題名おもしろいですねw

制約が小さいので全列挙が選択肢に入ります。
今回は(よくわからなかったので)全列挙しました。

作る竹の長さと(`target配列`)、使う竹の順番を決めます(`l`)。
竹を合体させるのと、伸ばす/縮めるのはどちらが先でもいいですね。かかるコストは変わりません。
竹は必ず使うようにしながらコストが少なくなるように作っていって、3本ともできた時点でのコストが答えです。

計算量は`3! * N!`=`O(N!)`です。
`N = [3, 8]`であって、`8! = 40320, 3! = 6` より、
最大でも `3! * 8! = O(10^6)` なので時間内に間に合います。

余談ですが変数名やばいw：`guchoku_cost, gattai_cost`

## D - 	Lazy Faith

``` c++
const ll INF = 1LL << 60;
  int a, b, q;
  cin >> a >> b >> q;
  vector<ll> s(a), t(b);
  for(int i = 0; i < a; ++i) cin >> s[i];
  for(int i = 0; i < b; ++i) cin >> t[i];

  ll x;
  for(int i = 0; i < q; ++i)
  {
    cin >> x;
    int ans = 0;
    auto s_it = lower_bound(s.begin(), s.end(), x);
    auto t_it = lower_bound(t.begin(), t.end(), x);

    ll sr = INF, tr = INF, sl = -INF, tl = -INF;
    if (s_it != s.end()) sr = *s_it;
    if (t_it != t.end()) tr = *t_it;
    if (s_it != s.begin()) { s_it--; sl = *s_it; }
    if (t_it != t.begin()) { t_it--; tl = *t_it; }
    
    ll straight_dist = INF, turn_dist = INF;

    // min( 左直進, 右直進 )
    straight_dist  = abs( min( x - min(sl, tl), max(sr, tr) - x) );

    // t左->s右
    ll dist_tlsr = abs(x - tl + sr - tl);
    // s左->t右
    ll dist_sltr = abs(x - sl + tr - sl);
    // t右->s左
    ll dist_trsl = abs(tr - x + tr - sl);
    // s右->t左
    ll dist_srtl = abs(sr - x + sr - tl);

    turn_dist = min({dist_tlsr, dist_sltr, dist_trsl, dist_srtl});

    cout << min(straight_dist, turn_dist) << endl;
  }
```

入力の`x`にたいして、近くの神社(s) と寺(t) を探す問題です。
数直線上での位置を探すので二分探索が使えますね。

神社と寺を訪れる組み合わせのうち、距離が最小になりうるものは
・左に直進した場合
・右に直進した場合
・右に行って左に行った場合
・左に言って右に行った場合
の合計4通りですね。
さらに`神社→寺`と`寺→神社`の2通りあるので、全部で8通りの組み合わせがありますね。
これら8つのうち最小のものが答えです。

`x`の右側と左側にある神社と寺の位置がわかればこれらの距離もわかります。
符号と、右か左に何もない場合(位置がINFになる場合)に注意です。

ちょっと複雑だったので考えやすい書き方で書きました。
イテレータをインデックスに直して、配列化して、`for`文で回すとシンプルになるんだろうな、って思います。


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