Lazy Faith

# [Lazy Faith](https://atcoder.jp/contests/abc119/tasks/abc119_d)

## コンテスト中の考察

- 愚直にやると$O(N^2)$とかになって死ぬ。
- 見るべき箇所は、xの近くだとわかる。近くってのをもっと考えると、大きく分けて以下の3パターンに分けられる
  1. x以下で一番近い神社と寺がひとつずつあるときのコスト
  2. x以上で一番近い神社と寺がひとつずつあるときのコスト
  3. xの左右で一番近い神社と寺がひとつずつあるときのコスト
- あとはどうやって調べるか...単調性があるから二分探索でいけそう
- x以上の数値は`lower_bound`でOK。x以下の数値はどうしようか。自分で実装するか...
- 二分探索実装しきれずに時間切れ。


## 解法

- 以下の3パターンについて調べる。
- パターン1は、x以下で一番近い神社と寺がひとつずつあるときのコスト
- パターン2は、xの左右で一番近い神社と寺がひとつずつあるときのコスト
- パターン3は、x以上で一番近い神社と寺がひとつずつあるときのコスト
- それぞれの近いやつは二分探索で求める。計算量は$O(Qlog(max(A, B))$。多分


![lazy_faith_1.png](https://qiita-image-store.s3.amazonaws.com/0/218584/3544c063-7ec4-752f-66db-cdd43abc459a.png)



## [コード（これ、番兵をうまく使いこなせてないらしい）](https://atcoder.jp/contests/abc119/submissions/4391534)
- これは「番兵使うと便利だよ」って言われて自分なりに番兵を使ってみたところ、中途半端な使い方をしてしまった結果生成されたコード
- 番兵の本領を発揮できてない。

```cpp
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define all(v) (v).begin(), (v).end()
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a = b; return 1; } return 0; }

const int INF = 1e18;

int A, B, Q;
vector<int> s, t;

int solve(int x) {
  // Right, Leftはxより右にあるか左にあるか
  // abs取るのは、値が見つからなかったときの処理をINFで統一させたいから(-INFあるとめんどい）
  int sRight = abs(*lower_bound(all(s), x));
  int sLeft = abs(*(upper_bound(all(s), x) - 1));
  int tRight = abs(*lower_bound(all(t), x));
  int tLeft = abs(*(upper_bound(all(t), x) - 1));

  int ret = INF;

  // (s, t) -> (t, s) -> x
  if (sLeft != INF and tLeft != INF) {
    chmin(ret, abs(x - min(sLeft, tLeft)));
  } 

  // s -> x -> t {
  if (sLeft != INF and tRight != INF) {
    chmin(ret, min(abs(x - sLeft), abs(x - tRight)) + abs(sLeft - tRight));
  }

  // t -> x -> s {
  if (tLeft != INF and sRight != INF) {
    chmin(ret, min(abs(x - tLeft), abs(x - sRight)) + abs(tLeft - sRight));
  }

  // x -> (s, t) -> (t, s)
  if (sRight != INF and tRight != INF) {
    chmin(ret, abs(max(sRight, tRight) - x));
  }

  return ret;
}

signed main() {
  cin >> A >> B >> Q;
  s.resize(A);
  t.resize(B);
  for (int i = 0; i < A; i++) {
    cin >> s[i];
  }
  for (int i = 0; i < B; i++) {
    cin >> t[i];
  }

  // 番兵を設置すると値が見つからなかったときの処理が楽になる
  s.push_back(INF);
  s.push_back(-INF);
  t.push_back(INF);
  t.push_back(-INF);
  sort(all(t));
  sort(all(s));

  while (Q--) {
    int x;
    cin >> x;
    int ans = solve(x);
    cout << solve(x) << endl;
  }

  return 0;
}
```



## [コード（番兵をうまく使ったコード）](https://atcoder.jp/contests/abc119/submissions/4404600)

- 番兵をうまく使うと、面倒な条件分岐を書かなくてよくなる。
- いい感じの区間が見つからない場合は`[s, t]`の区間が`[-INF, 3]`とかになるので必然的に距離が大きくなる。それより小さい距離は確実に存在するので、`[-INF, 3]`みたいな区間が使用されることはない（なんかうまいこと説明できないな）

```cpp
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define all(v) (v).begin(), (v).end()

template<class T>bool chmin(T &a, const T &b) { if (b<a) { a = b; return 1; } return 0; }

const int INF = 1e18;

int A, B, Q;
vector<int> s, t;

int solve(int x) {
  // Right, Leftはxより右にあるか左にあるか
  int sRight = *lower_bound(all(s), x);
  int sLeft = *(upper_bound(all(s), x) - 1);
  int tRight = *lower_bound(all(t), x);
  int tLeft = *(upper_bound(all(t), x) - 1);

  int ret = INF;

  // (s, t) -> (t, s) -> x
  chmin(ret, abs(min(sLeft, tLeft) - x));

  // s -> x -> t
  chmin(ret, abs(tRight - sLeft) + abs(min(x - sLeft, tRight - x)));

  // t -> x -> s
  chmin(ret, abs(sRight - tLeft) + abs(min(x - tLeft, sRight - x)));

  // x -> (s, t) -> (t, s)
  chmin(ret, abs(max(tRight, sRight) - x));

  return ret;
}

signed main() {
  cin >> A >> B >> Q;
  s.resize(A);
  t.resize(B);
  for (int i = 0; i < A; i++) {
    cin >> s[i];
  }
  for (int i = 0; i < B; i++) {
    cin >> t[i];
  }

  // 番兵を設置すると値が見つからなかったときの処理が楽になる
  s.push_back(INF);
  s.push_back(-INF);
  t.push_back(INF);
  t.push_back(-INF);
  sort(all(t));
  sort(all(s));

  while (Q--) {
    int x;
    cin >> x;
    int ans = solve(x);
    cout << solve(x) << endl;
  }

  return 0;
}
```

### 番兵を使ったコードで混乱したこと

- コードの式をパッと見ると、`INF - INF + hoge`みたいなことが起こって正しい結果が求められないのではないか？？？と思った。よくよくみるとそんなことが怒らないことはわかるけど、ぱっと見わかんない
- つまり、INF, -INFがあるとなんか頭ぶっ壊れるって感じになってた。
- 結論としては、計算では「(x以上のやつ) - (x以下のやつ)​」をしている。なので、変なことは起こらない。
- コードの式ばかりを眺めていたので、その式がどういう意味だったかを忘れていたために頭がぶっ壊れていた。
- 式の意味も意識できるといいな。





## bound系の使い方

- bound系の使い方何回やっても忘れるのでメモ
- key以下の最大値を簡単に求められるのは知らなかった
- 前後に番兵として`INF`、`-INF`を挟むことで処理が楽になることがある。番兵を挟まないと`itr != v.end()`みたいなことを書かないといけない（ちょっとだるい）

| やりたいこと                                      | コード                                                       |
| ------------------------------------------------- | ------------------------------------------------------------ |
| key**以上**の最小値を指すイテレータを取得する     | `lower_bound(begin, end, key)`                               |
| key**より大きい**最小値を指すイテレータを取得する | `upper_bound(begin, end, key)`                               |
| key**以下**の最大値を指すイテレータを取得する     | `upper_bound(begin, end, key) - 1`。番兵として前後に`-INF, INF`を挟むとバグらない |



## 僕が本番中にやりたかったこと

- [提出したコード](https://atcoder.jp/contests/abc119/submissions/4392054)

- 二分探索の実装が苦手すぎてコンテスト中に実装し終わらなかった
- x以下の値を求める二分探索が標準で存在しないので自分で書こうとしていた。
- 最初は`(l, r]`で実装しようとしてたけど無理だった。結局`[l, r)`だと実装できた。両方の半開区間について考えてみれば早く実装できたのかなー？

```cpp
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define all(v) (v).begin(), (v).end()
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a = b; return 1; } return 0; }

const int INF = 1e18;

int A, B, Q;
vector<int> s, t;

// 配列からkey以下の値で最も大きい数値がある場所のインデックスを返す
int bin(vector<int> &v, int key) {
   auto check = [&](int mid) -> bool {
      return v[mid] <= key;
   };

    // [l, r)
   int l = 0;
   int r = v.size();

   while (r - l > 1) {
      int mid = (l + r) / 2;
      if (check(mid)) {
         l = mid;
      } else {
         r = mid;
      }
   }

   return l;
}

int solve(int x) {
  // Right, Leftはxより右にあるか左にあるか
  // abs取るのは、値が見つからなかったときの処理をINFで統一させたいから(-INFあるとめんどい）
  int sRight = abs(*lower_bound(all(s), x));
  int sLeft = s[bin(s, x)];
  int tRight = abs(*lower_bound(all(t), x));
  int tLeft = t[bin(t, x)];

  int ret = INF;

  // (s, t) -> x -> (t, s)
  if (sLeft != INF and tLeft != INF) {
    chmin(ret, abs(x - min(sLeft, tLeft)));
  } 

  // s -> x -> t {
  if (sLeft != INF and tRight != INF) {
    chmin(ret, min(abs(x - sLeft), abs(x - tRight)) + abs(sLeft - tRight));
  }

  // t -> x -> s {
  if (tLeft != INF and sRight != INF) {
    chmin(ret, min(abs(x - tLeft), abs(x - sRight)) + abs(tLeft - sRight));
  }

  // x -> (s, t) -> (t, s)
  if (sRight != INF and tRight != INF) {
    chmin(ret, abs(max(sRight, tRight) - x));
  }

  return ret;
}

signed main() {
  cin >> A >> B >> Q;
  s.resize(A);
  t.resize(B);
  for (int i = 0; i < A; i++) {
    cin >> s[i];
  }
  for (int i = 0; i < B; i++) {
    cin >> t[i];
  }

  // 番兵を設置すると値が見つからなかったときの処理が楽になる
  s.push_back(INF);
  s.push_back(-INF);
  t.push_back(INF);
  t.push_back(-INF);
  sort(all(t));
  sort(all(s));

  while (Q--) {
    int x;
    cin >> x;
    int ans = solve(x);
    cout << ans << endl;
  }

  return 0;
}
```



## 要点

- 二分探索は`[l, r)`と`(l, r]`両方について考えるといい？
  - 素早く実装する方法がまだ掴めてないからよくわからん
  - とりあえず両方考えると良さそう
- 番兵を使うと条件分岐がいらなくなったりするっぽい？
  - 初めて番兵を使ったのでこれが基本的な番兵の使い方なのかよくわかってない
- 式の意味を考える
  - コードの式ばかりを眺めてると、何が起きてるのかわからずに頭がぶっ壊れる
  - どういう意味の式だったかを思い出すと解決しそう（たぶん）



## メモ

- [けんちょんさんの記事](http://drken1215.hatenablog.com/entry/2019/02/24/230900)