Tree Burning（部分点）

# [Tree Burning](https://atcoder.jp/contests/agc030/tasks/agc030_b)



## コンテスト中の考察

- まずは部分点を取りたい
- とりあえず貪欲を書く。[こんな感じで](https://atcoder.jp/contests/agc030/submissions/3895628)。でもサンプルすら通らない
- 次にDFSを書く。けどなんかバグる。
- 次にDPっぽい雰囲気を感じたからDPを考えてみる。でも、どうDPするかすら思いつかない
- 対戦ありがとうございました



## 理想の考察

- 貪欲っぽい。けど、反例がありそう
- 確実そうなDPを考えてみる
- まず、DPにどういう情報が必要かを考えてみる。
- ここで天才になると、`dp[左回りで燃やした本数][右回りで燃やした本数]`が出来そうだと思いつく
- 次に遷移を考えると以下のようになることがわかる

```cpp
dp[i][j] ← dp[i-1][j]
         ← dp[i][j-1]
```

- ただ、同じ`dp[i][j]`でも、現在地によっては次の遷移がどうなるかが異なる
- 例えば以下の画像の現在地について、２つの状態はどちらも`dp[2][1]`である。そしてその状態から左回りすることを考えてみる。すると、現在地によって遷移の仕方が違っている。よって、現在地の情報も必要であることがわかる

![tree_burning_1.png](https://qiita-image-store.s3.amazonaws.com/0/218584/bcbbdd73-3df8-0d91-e421-a622eb290508.png)



- 以上の考察により、`dp[左回りで燃やした本数][右回りで燃やした本数][現在地]`といったDPができる気がしてくる。現在地は、0の時に左にいて、1の時に右にいると定義する
- 遷移を考えると、以下のようになる

```cpp
// 左への移動
dp[i][j][0] ← dp[i-1][j][0] // 今左にいる
            ← dp[i-1][j][1] // 今右にいる

// 右への移動           
dp[i][j][1] ← dp[i][j-1][0] // 今左にいる
            ← dp[i][j-1][1] // 今右にいる
```

- 遷移を考えたので、次に遷移のときに値がどうなるかを考える。これは図をかいていろいろ考える。
- 現在地が左の時、左回りをするのは`X[i] - X[i-1]`みたいにできる。けど、右回りが絡むと少し面倒になる。配列の後ろから見ないといけないし、なんかいろいろだるい。
- なので、初期位置から右回りの距離を別の配列として用意する
- こんな感じで考察終了



## 解法

1. `dp[左回りで燃やした本数][右回りで燃やした本数][現在地]`という状態を持つ
2. 右回りをしたときの初期位置からの距離を前もって計算しておく
3. DPを以下のように遷移させる

```cpp
// 左への移動
dp[i][j][0] ← dp[i-1][j][0] // 今左にいる
            ← dp[i-1][j][1] // 今右にいる

// 右への移動           
dp[i][j][1] ← dp[i][j-1][0] // 今左にいる
            ← dp[i][j-1][1] // 今右にいる
```





## [コード](https://atcoder.jp/contests/agc030/submissions/3903065)

```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; }

int L, N; // 円周, 木の本数
int X[2222]; // 初期位置からの距離(左回り), 1-indexed
int Y[2222]; // 初期位置からの距離(右回り), 1-indexed
int dp[2222][2222][2]; // dp[左回りで燃やした本数][右回りで燃やした本数][現在地]

signed main() {
  cin >> L >> N;
  for (int i = 1; i <= N; i++) {
    cin >> X[i];
    Y[N-i+1] = L - X[i]; // あらかじめ計算しておく
  }

  for (int li = 0; li <= N; li++) { // 左回りで燃やした本数
    for (int ri = 0; ri <= N; ri++) { // 右回りで燃やした本数
      // 左へ
      if (li > 0) {
        chmax(dp[li][ri][0], dp[li-1][ri][0] + X[li] - X[li-1]); // 今左
        chmax(dp[li][ri][0], dp[li-1][ri][1] + X[li] + Y[ri]); // 今右
      }

      // 右へ
      if (ri > 0) {
        chmax(dp[li][ri][1], dp[li][ri-1][0] + X[li] + Y[ri]); // 今左
        chmax(dp[li][ri][1], dp[li][ri-1][1] + Y[ri] - Y[ri-1]); // 今右
      }
    }
  }

  int ans = 0;
  for (int li = 0; li <= N; li++) {
    // li + ri = Nなので
    int ri = N - li;
    chmax(ans, dp[li][ri][0]);
    chmax(ans, dp[li][ri][1]);
  }

  cout << ans << endl;


  return 0;
}
```



## 要点

- DPでは、まず状態の持ち方を考える。次に遷移を考える
- 遷移は、１つ前の状態から今の状態にどう移るかを考える



## 感想

- むーずーいー（むずいの歌）
- 本番中、何も思いつかねえwwwwwwwって笑ってた。こういう問題の考察の仕方がわからなかった。



## 参考

- [アルメリアさんのブログ](https://betrue12.hateblo.jp/entry/2018/12/30/215006)。いつもお世話になっております



## めも

- DPは区間DPってやつらしい
- [Sorted and Sorted](https://atcoder.jp/contests/arc097/tasks/arc097_c)。アルメリアさんがTwitterにあげてた部分点の類題。彼の感覚だと500~600らしい
- [Static Sushi](https://atcoder.jp/contests/arc096/tasks/arc096_b)。問題設定が似てた
- 満点解法はstatic sushiっぽいことをするっぽい？

<blockquote class="twitter-tweet" data-lang="ja"><p lang="ja" dir="ltr">AGC030 B: 部分点は典型DPです（ABC Onlyの400点として出せるレベル）これで強力な実験ツールが手に入るので実験して仮説を立てればあとは強化版 Static Sushi</p>&mdash; えびま (@evima0) <a href="https://twitter.com/evima0/status/1079013607680049152?ref_src=twsrc%5Etfw">2018年12月29日</a></blockquote>
<script async src="https://platform.twitter.com/widgets.js" charset="utf-8"></script>



## おまけ

- 解き直した時のメモ



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

int L, N;
int X[222222];

signed main() {
  cin >> L >> N;
  rep (i, N) {
    cin >> X[i];
  }

  for (int li = 0; li <= N; li++) {
    for (int ri = 0; ri <= N; ri++) {
      dp[li][ri] = dp[li-1][ri] + ;
      dp[li][ri] = dp[li][ri-1] + ;
    }
  }

  return 0;
}
```

- これではどういう移動かわからない。というのも左３個、右２個の状態だと以下の図のようになるが、どちらにいるかはわからない。なのでどちらにいるかという情報も持たせる
- よくよく考えると、その情報いらない気がしてきた。なんか複雑だし
- [こんな感じで書いた](https://atcoder.jp/contests/agc030/submissions/3899536)けど、WAだった。
- やはり現在地は必要なのか？
- 必要であることがわかった。あの画像
- さて、実装していくわけだが、添え字でバグる。よくよく考えると、右回りは配列の後ろから見る必要があることを忘れていた。
- なので、対応づけが必要となる。いちいち考えるのは面倒なのであらかじめ用意する。
- 右回りについて実装するも、かなりバグる。なので、右回りからの距離を前もって計算しておいた方が良い