みんプロ-D「Ears」

- [Ears](https://atcoder.jp/contests/yahoo-procon2019-qual/tasks/yahoo_procon2019_qual_d)

## コンテスト中の考察（解けてない）

- 問題文が複雑だから整理した
- さて、どうしようか。なにもわからないぞ
- 紙で色々実験するか
- 実験してると、偶奇が大事そうだなぁってなる。
- 奇数の個数分だけコストがかかる？偶数の個数分だけコストがかかる？奇数と偶数が切り替わる部分でコストがかかる？
- 0が邪魔なのかなー？
- どれもこれも違う。もう何もわからない。
- 終了



## 解法

<img width="679" alt="ears_1.png" src="https://qiita-image-store.s3.amazonaws.com/0/218584/be14b515-5de8-bb71-5f21-0df2a2ecd584.png">


- スタート地点とゴール地点を決めて適当に線を書くと上記図のようになる。
- これより区間は「1回も通らない区間」「偶数通る区間」「奇数回通る区間」「偶数回通る区間」「1回も通らない区間」の5つに分けられることがわかる
- 全ての区間について全探索すれば解けそう。でも計算量は$O(L^4)$とか$O(N^5)$くらいになって死ぬ（詳しくは知らん）。とにかく愚直にやると死ぬ
- そこで、DPする。DPは全探索の状態をまとめることができる。例えば座標5まで見た時の最小値をまとめる、みたいなかんじ。
- `dp[i][j]: 座標iまで見たとき、区間jの最小コスト`みたいにする。座標は[0, L]のやつ。区間は「1回も通らない」「偶数通る」...とかのやつなので、1~5までの5パターンある。
- 持つ状態はわかったので、あとは頑張って遷移を考える。すると、以下のようになる。コストは後で考える

#### 1回も通らない区間

```
dp[i+1][1] ← dp[i][1] + cost1
```

#### 偶数回通る区間

```
dp[i+1][2] ← dp[i][1] + cost2
		   ← dp[i][2] + cost2
```

#### 奇数回通る区間

```
dp[i+1][3] ← dp[i][1] + cost3
           ← dp[i][2] + cost3
           ← dp[i][3] + cost3
```

#### 偶数回通る区間

```
dp[i+1][4] ← dp[i][1] + cost4
			 ← dp[i][2] + cost4
			 ← dp[i][3] + cost4
			 ← dp[i][4] + cost4
```

#### 1回も通らない区間

```
dp[i+1][5] ← dp[i][1] + cost5
		 ← dp[i][2] + cost5
		 ← dp[i][3] + cost5
		 ← dp[i][4] + cost5
		 ← dp[i][5] + cost5
```

- 次にコストを考える。入力された配列を`v`とする。
- cost1は`v[i]`となる。すぬけくんが1回も通らないので、りんごさんは`v[i]`回操作する必要がある。また、cost5も同様である
- cost2は`v[i]`が0のときは2、そうでないときは`v[i]`を2で割ったあまりになる。`v[i]`が0のときは、本当は通りたくないけど通る区間は連続なので通らなければならない。この区間は偶数回通るので、最小の2回通るのが一番お得。`v[i]`が0でないとき、偶数ならすぬけくんの操作で条件をみたせるのでりんごさんは何もする必要がない。奇数ならすぬけくんがどう頑張ろうがりんごさんが1回そうさしなければならない（この区間は偶数回通るので）。また、cost4も同様である
- cost3は`v[i]`が0の時は1になる（奇数回の最小回数）。そうでないとき、偶数なら1、奇数なら0となる。これは先ほどと同様に考えればわかる。
- DPの状態と遷移が考察できたのであとは実装するだけ



## [コード](https://atcoder.jp/contests/yahoo-procon2019-qual/submissions/4220552)

- 初期化は`dp[0][0] = 0`だけでいいらしいけど、僕は`dp[0][0~4] = 0`をした方がわかりやすかったのでそうした
- 冗長な遷移もあるみたいだけど、僕はこのコードがわかりやすい。本当はもっと綺麗に書けるみたい

```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; }
const int INF = 1e18;

const int VARI = 5; // パターンの数
int dp[200010][VARI]; // dp[i][j]: 座標iまで見たとき、区間jを見た時の最小コスト

signed main() {
  // 入力
  int N;
  cin >> N;
  vector<int> v(N);
  for (int i = 0; i < N; i++) { cin >> v[i]; }

  const int one = 0; // 左のゼロ区間
  const int two = 1; // 右のゼロ区間
  const int three = 2; // 左の偶数区間
  const int four = 3; // 右の偶数区間
  const int five = 4; // 奇数区間

  // 初期化
  fill(dp[0], dp[N+1], INF);
  dp[0][one] = 0;
  dp[0][two] = 0;
  dp[0][three] = 0;
  dp[0][four] = 0;
  dp[0][five] = 0;

  // DP
  for (int i = 0; i < N; i++) {
    // 左のゼロ区間
    int cost1 = v[i];
    chmin(dp[i+1][one], dp[i][one] + cost1);

    // 左の偶数区間
    int cost2 = v[i] == 0 ? 2 : v[i] % 2; // 0だったら最低2回通る必要がある。
    chmin(dp[i+1][two], min(dp[i][one], dp[i][two]) + cost2);

    // 奇数区間
    int cost3 = v[i] == 0 ? 1 : (v[i] % 2 == 0); // 0だったら最低1回通る必要がある
    chmin(dp[i+1][three], min({dp[i][two], dp[i][three], dp[i][one]}) + cost3);

    // 右の偶数区間
    int cost4 = v[i] == 0 ? 2 : v[i] % 2;
    chmin(dp[i+1][four], min({dp[i][three], dp[i][four], dp[i][two], dp[i][one]}) + cost4);

    // 右のゼロ区間
    int cost5 = v[i];
    chmin(dp[i+1][five], min({dp[i][four], dp[i][three], dp[i][two], dp[i][one], dp[i][five]}) + cost5);
  }

  int ans = INF;
  // 座標Nを見た時、区間iの最小値が答えになる
  for (int i = 0; i < VARI; i++) {
    chmin(ans, dp[N][i]);
  }

  cout << ans << endl;

  return 0;
}
```



## 要点

- 全探索の状態をまとめたいとき、DPが使えるっぽい
  - 全探索だと死ぬ時にDP使えるといいな。
  - 今回は区間を右に伸ばす全探索をDPにした
- パターンを列挙するといいことがある
  - この問題の場合、5パターンを思いつけると良かった

## 全探索で解く（追記）

- 暇なので全探索で解くとどんな感じのコードになるか書いてみた
- [提出したコード](https://atcoder.jp/contests/yahoo-procon2019-qual/submissions/4223304)。TLEするけど。
- 区間1~5を右に伸ばす感じの全探索をする。
- 区間1~4の右端全探索が$O(L^4)$となる。決め打った区間に応じてスコアを決めるのが$O(L)$となる。よって全体的な計算量は$O(L^5)$となり死滅する。

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

#define int long long

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

int L;
vector<int> A;

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

  int ans = 1e18;
  int first = 0; // 区間1の開始地点
  int five = L; // 区間5の終端
  for (int one = first; one <= L; one++) { // 区間1の終端を探索
    for (int two = one; two <= L; two++) { // 区間2の終端を探索
      for (int three = two; three <= L; three++) { // 区間3の終端を探索
        for (int four = three; four <= L; four++) { // 区間4の終端を探索
          int cand = 0; // 最小コストの候補
          for (int i = 0; i < L; i++) {
            if (0 <= i && i < one) { // 区間1
              cand += A[i];
            } else if (one <= i && i < two) { // 区間2
              cand += (A[i] == 0 ? 2 : A[i] % 2);
            } else if (two <= i && i < three) { // 区間3
              cand += (A[i] == 0 ? 1 : A[i] % 2 == 0);
            } else if (three <= i && i < four) { // 区間4
              cand += (A[i] == 0 ? 2 : A[i] % 2);
            } else if (four <= i && i < five) { // 区間5
              cand += A[i];
            }
          }
          chmin(ans, cand);
        }
      }
    }
  }

  cout << ans << endl;

  return 0;
}
```


## めも

- [アルメリアさんの記事](https://betrue12.hateblo.jp/entry/2019/02/10/014031)
- [けんちょんさんの記事](http://drken1215.hatenablog.com/entry/2019/02/10/014800)
- [ferinさんの記事](https://ferin-tech.hatenablog.com/entry/2019/02/10/%E3%81%BF%E3%82%93%E3%81%AA%E3%81%AE%E3%83%97%E3%83%AD%E3%82%B3%E3%83%B3_2019_D_-_Ears)
- [じゅっぴーさんの記事](https://juppy.hatenablog.com/entry/2019/02/10/Yahoo_%E3%81%BF%E3%82%93%E3%81%AA%E3%81%AE%E3%83%97%E3%83%AD%E3%82%B3%E3%83%B32019_-D_Ears-_Python_%E7%AB%B6%E6%8A%80%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9F%E3%83%B3%E3%82%B0_Atcoder)
- [Misterさんの記事](https://misteer.hatenablog.com/entry/minpro2019-qual)



## 感想

- 「5つの区間にわかれるからDPして」って言われたらなんとか解けるくらいの難易度（僕的には）
- DPの部分は頑張ればなんとかなる
- でも、5つの区間に分割する部分の考察がくっっっっそ大変。まじで。なんで思いつくのかわからん。
- まず、うろうろ図を描く。そんで、いきなり全体について考えるのは大変だから左側だけ考える。左側ってどこだ？スタート地点より左側を考えよう。この部分を考えると、右側から線が入ってきて右側に抜ける。これは偶数回通るってことか。
- みたいな感じ？
- 次に右側を考える。右側はゴールより右を考えよう。これは左から線がきてかならず左に抜ける。これも偶数回とおるな。
- 必然的に真ん中はスタートからゴールの間になる。この区間は左からきて右に抜ける。これはどれだけうろうろする線を描いても奇数回通る区間になる。
- 左側についてより詳しく考えると、最小値より左側がある。
- 右側についてより詳しく考えると、最大値より右側がある
- こんな感じで5つの区間が思いつく感じなのか？？？わからん
- この辺の考察を図を描きながらやると結構スッキリ考察できるな。本番思いつける気はしないけど
- で、区間がわかったら全探索を考えてみる。計算量がえげつないから、状態をまとめるDPを考える。これで解けるって感じか。
- そもそも全探索すら思いつかなかった。その発想がなかった。