Tunnel

- [Tunnel](https://onlinejudge.u-aizu.ac.jp/beta/room.html#RitsCamp19Day2/problems/D)(RUPC2019-day2-D)

## コンテスト中の考察（チームでやったやつ）

- とりあえず問題文を把握。そんで、サンプル1になるようなケースを探すけど見つからない。誤読か？となってチームで読み直すけど誤読ではないっぽい
- きゅうりさんが直感的にDPっぽいって言ったけど僕はピンとこず
- とりあえずサンプル1の場合で全探索してみればいいのでは？となった。自分で最適解を見つけられないならコンピュータに見つけてもらおうという発想。
- というわけで全探索。
- そのとき、面積を求める処理がちょっとめんどいのでそれを先に考える。パターンは4つある（書くのだるいので詳細は後述）。そんで、面積を求める処理を関数化しておいた。
- サンプル1の全探索で、答えがサンプル通りになった。全探索っぽいことでできるみたい
- きゅうりさんが「あとはDPするだけ」って言ったのでDPを考えた。
- `dp[index+1][次のy][次の次のy] <- dp[index][現在のy][次のy]`という謎遷移を編み出した。なんか連続する3つのyが関係ある（独立してない）と思ってた。なんか頭おかしいことしてた。
- よくわかんなくなってきゅうりさんに助けを頼んだら、今のyと次のyの遷移だけを考えればいいって教えてもらった。
- `dp[index+1][次のy] <- dp[index][現在のy]`みたいにすればいい。確かに、遷移先には全通りの高さについての最適地が入ってるので、大丈夫になるなぁと思った。
- てな感じでDPを実装した
- 提出する前に見てもらったところ、`dp[155][155]`の部分を指摘された。`dp[155][300`jくらいにした方がいいのでは？っていう感じの指摘。この時は何もわからずに指示通りにした。でも、コンテスト後に考えてみたらyが160とかになる場合もあるんだなぁってなった。yの制約は150までだと勘違いしてた。yは好きな値が取れる。
- DPを修正して提出したらAC。やったぜ！！（ここに書いてないけど、他にもめちゃくちゃバグらせてしまった...）



## 解法

1. `dp[index][y]:= indexまで見て、引く線の高さがyだったときの最小コスト`という状態を保つ。yの大きさを大き目にとって`dp[151][300]`とかにする。DPテーブルは`dp[0][1] = 0`でその他は無限大で初期化する。`dp[0][1] = 0`は初期状態。
2. `dp[i+1][次のy] <- min(dp[i+1][y2], dp[i][y1] + cost)`っていう遷移を作る。y1は棒iを見たときの左側の高さ、y2は棒iを見たときの右側の高さを示す。`cost`は$h_i, y1, y2$に応じた面積になる。
   - `cost`のパターンは以下の4通り。
   - 1つ目はy1, y2の高さがh以下である場合。これは台形の公式でいける
   - 2つ目はy1の高さがh以下でy2の高さがhを超える場合。これは下の三角と上の三角の面積を求める必要がある。両方の３角とも、高さhの時のxの値が必要である。xは赤線の傾きから求めることができる。そんな感じで頑張ると面積を求めることができる
   - 3つ目はy1の高さがh超えてy2の高さがh以下である場合。同上
   - 4つ目はy1の高さがhを超えてy2の高さもy2を超える場合。これは台形の公式でいける。

![tunnel_1.png](https://qiita-image-store.s3.amazonaws.com/0/218584/6014729c-0f1a-e9a2-65fb-1a70d1325c09.png)





## [コード](https://onlinejudge.u-aizu.ac.jp/beta/room.html#RitsCamp19Day2/workspace)

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

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

// h_iと、そのときの左のyと右のyを渡すと面積が返ってくる
double calc(int h, int y1, int y2) {
  if (y1 > h and y2 > h) {
    return fabs(0.5 * (y1 - h + y2 - h));
  }
  if (y1 <= h and y2 <= h) {
    return fabs(0.5 * (h - y1 + h - y2));
  }
  if (y1 <= h and h > y2) {
    double x = 1.0 * (h - y1) / (y2 - y1);
    return fabs(0.5 * ( x * (h - y1) + (1 - x) * (h - y2)));
  } else {
    double x = 1.0 * (h - y1) / (y2 - y1);
    return fabs(0.5 * ( x * (y1 - h) + (1 - x) * (h - y2) ));
  }

}

const double INF = 1e18;
double dp[155][333]; // dp[index][y] := indexまでみて、そのときの線がyだったときの最小コスト

signed main() {
  int n;
  cin >> n;
  vector<int> h(n);
  for (int i = 0; i < n; i++) {
    cin >> h[i];
  }

  // DPテーブルを初期化
  for (int i = 0; i <= n; i++) {
    for (int y = 1; y <= 300; y++) {
      dp[i][y] = INF;
    }
  }
  dp[0][1] = 0;

  // DP
  for (int i = 0; i < n; i++) {
    for (int y1 = 1; y1 <= 300; y1++) { // 左のy
      for (int y2 = 1; y2 <= 300; y2++) { // 右のy
        chmin(dp[i+1][y2], dp[i][y1] + calc(h[i], y1, y2));
      }
    }
  }

  // 最後のyはどれが最適化を選ぶ
  double ans = 1e18;
  for (int i = 1; i <= 300; i++) {
    chmin(ans, dp[n][i]);
  }

  printf("%.10f\n", ans);

  return 0;
}
```



## 要点

- 手元で試して最適な値が出せないときはコンピュータでシミュレーションした方が良いかも
  - 手元で実験してサンプルが合わず、よくわからなくなってた。
  - 普通に全探索すればいいんだけど、なんか思いつかなかった



## メモ

- パターン2, 3の面積を求めるやつ、相似を使った方が楽だったみたい。本番でも相似を使って解いた（僕は傾きを使って求める方法を考えたが、バグってるとめんどいので相似にした）。相似を考えたのは僕じゃなかった。
- 相似、よく知らないのでこの記事では傾きを使って求めるコードにした。そういえば他のチームも相似使って解いてるところあったな
- `dp[i][j]`のjが300くらいでいい証明をスライドでやってたけどよくわかんなかった。