Introduction to Heuristic Contest

# 0:始めに
https://atcoder.jp/contests/intro-heuristics

のメイン備忘録&解説記事です
120018595点をとりました
公式解説がRustだったのでC++でのコードを俺得で書きました。
各種コードはここからどうぞ

https://github.com/motimotipurinn/Introduction-to-Heuristics-Contest

概略を説明すると貪欲して貪欲ベースに局所探索して焼きなまししました

# 1:貪欲 greedy.cpp　104195466点
main() 各日付に対して0~25のどれを入れればいいのかを、0日~26日先のスコアを見ながら更新していきます。ここに各種関数を張っておきます

```cpp
  rep(i, 26) {
    auto t = solve(D, c, d, i);
    in score = get_score(c, d, t);
    if (chmax(ans_score, score)) {
      ans = t;
    }
  }
```
solve()

```cpp
vin solve(int D, vin &c, vvin &d, int K) {
  vin t;
  rep(i, D) {
    int max_score = -INF;
    int p = -1;
    rep(j, 26) {
      t.push_back(j);
      in score = evaluate(c, d, t, K, D);
      if (chmax(max_score, score)) {
        p = j;
      }
      t.pop_back();
    }
    t.push_back(p);
  }
  return t;
}

```
get_score()　愚直にscore計算してます

```cpp
ll get_score(vin &c, vvin &d, vin &t) {
  in score = 0;
  vin last(26, -1);
  rep(i, t.size()) {
    score += d[i][t[i]];
    last[t[i]] = i;
    rep(j, 26) score -= c[j] * (i - last[j]);
  }
  return score;
}
```
evaluate()　k日先でのscore計算してます
```cpp
ll evaluate(vin &c, vvin &d, vin &t, int K, int D) {
  in score = 0;
  vin last(26, -1);
  rep(i, t.size()) {
    score += d[i][t[i]];
    last[t[i]] = i;
    rep(j, 26) { score -= c[j] * (i - last[j]); }
  }
  for (in i = t.size(); i < min<long long>(D, t.size() + K); i++) {
    rep(j, 26) score -= (i - last[j]) * c[j];
  }
  return score;
}
```
# 2:局所探索  lo_search.cpp 111768159点
時間の限りランダムな一点をランダムな値に変更したり、2点をswapします。scoreの上昇が見られたらその変更を採択します。
局所最適解に落ちいりやすいのですが、貪欲法よりは多少いい結果が期待できます
ちなみにコードでは上記の2つの行動のスコア計算には無駄があります。詳しくは公式解説をご覧ください
main()
```cpp
while (1) {
    end = std::chrono::system_clock::now();
    double elapsed =
        std::chrono::duration_cast<std::chrono::milliseconds>(end - start)
            .count();
    if (elapsed < 1800) {
      int dice = rnd(2);
      if (dice == 0) {
        int p = rnd(D), q = rnd(26);
        int old = ans[p];
        ans[p] = q;
        int new_score = get_score(c, d, ans);
        if (!(chmax(ans_score, new_score))) {
          ans[p] = old;
        }
      } else {
        int p = rnd(D), q = rnd(1, 16);
        if (p + q < D) {
          swap(ans[p], ans[p + q]);
          int new_score = get_score(c, d, ans);
          if (!(chmax(ans_score, new_score))) {
            swap(ans[p], ans[p + q]);
          }
        }
      }
    } else {
      break;
    }
  }
```

#3:焼きなまし法 main.cpp 120018595点
詳しい解説は公式解説を読んでもらえればいいのですが簡単に説明すると、(貪欲でない)探索の進度が低いうちはscoreが減ったとしても確率的にそれを許容するというものです。こうすることで局所解から脱出することができます。また探索が終わりの方に近づいてくるとscoreもその探索方法においては理論値に近づいてきてるわけですから、score減少への更新を許容するのは不利になります。なので終盤においてはscoreが減ったときの許容する確率どんどん減らしていきます。

```
ld t2 = elapsed2 / 1300;
```
の部分ですが、これは初期解の貪欲を求めるのに700msぐらいの時間がかかるから制限時間の2000msとの差分をとったものです。2000で割るよりいいscoreが得られました。

```cpp
  ld T0 = 2e3;
  ld T1 = 6e2;
  ld T = T0;
  int cnt = 0;
  start2 = std::chrono::system_clock::now();
  while (1) {
    end = std::chrono::system_clock::now();
    double elapsed =
        std::chrono::duration_cast<std::chrono::milliseconds>(end - start)
            .count();
    double elapsed2 =
        std::chrono::duration_cast<std::chrono::milliseconds>(end - start2)
            .count();
    if (elapsed > 1900) {
      break;
    }
    cnt++;
    if (cnt % 50 == 0) {
      ld t2 = elapsed2 / 1300;
      T = pow(T0, 1 - t2) * pow(T1, t2);
    }
    int dice = rnd(2);
    if (dice == 0) {
      int p = rnd(D), q = rnd(26);
      int old = ans[p];
      ans[p] = q;
      int new_score = get_score(c, d, ans);
      ld x = exp((new_score - ans_score) / T);
      if (chmax(ans_score, new_score) || rnd.randBool(x)) {
        ans_score = new_score;
      } else {
        ans[p] = old;
      }
    } else {
      int p = rnd(D), q = rnd(1, 16);
      if (p + q < D) {
        swap(ans[p], ans[p + q]);
        int new_score = get_score(c, d, ans);
        ld x = exp((new_score - ans_score) / T);
        if (chmax(ans_score, new_score) || rnd.randBool(x)) {
          ans_score = new_score;
        } else {
          swap(ans[p], ans[p + q]);
        }
      }
    }
  }
```
# 4:感想
はじめてHeuristicの勉強をしてみたのですが普通に楽しめました。実装が苦手なので愚直が割と簡単そうなコンテストがあればまた参加してみたいです
間違いがあれば指摘お願いします。

参考
https://qiita.com/ganyariya/items/52a36af7fb39da1c9527
https://atcoder.jp/contests/intro-heuristics/editorial