AHC 典型 : 解をたくさん作る

貪欲の次の一手として。

とりあえず貪欲は書けました。次は何をすれば良いですか？

パラメータを変えてみたり、乱択要素を入れてみたりした別の解をたくさん作って、一番スコアが良かった解を出力しましょう！

struct Answer {
  /* ここに解の情報を持つ */

  int score;

  void print(ostream& out) {
    /* ここで解の出力をする */
  }

  bool operator<(const Answer& rhs) const {
    return score < rhs.score;
  }
};


class Solver {
protected:
  int param;

public:
  Solver(int param) : param(param) {}

  Answer solve() {
    /* ここで問題を解いて Answer を生成 */
    return answer;
  }
};


int main() {
  // たくさん解を作る
  vector<Answer> answers;
  for (int param = 0; param < 10; param++) {
    auto answer = Solver(param).solve();
    answers.push_back(answer);
  }

  // 一番スコアが良かった解を出力
  auto best_answer = *max_element(answers.begin(), answers.end());
  best_answer.print(cout);
}

Answer solve() を仮想関数にして子クラスで実装することで異なる複数のロジックを記述するのも良いです。

嬉しい点

  • 貪欲解 1 つから確実にスコアを伸ばせる
  • 新しい解法（Solver）を追加してもスコアが落ちることがない
    • 良くない解なら採用されないだけなので
    • 乱数がズレるとか、実行時間を逼迫するとかでテストケースによっては下がるとかはある
  • 貪欲解をそのまま流用しやすく、実装コストが低い
  • 問題のパラメータによって良い解法が異なるみたいなのにも対応できる

留意点

基本的に局所探索の方がつよいので、局所探索ができるかつ実装時間が十分にあるなら局所探索をしましょう。

インタラクティブ問題では無理じゃない？

クエリを投げたり答えを投げたりする入出力部分は別クラスに切り出し、シミュレータで性能を測り、一番スコアが良かった解で本番に臨みましょう！

class IO {
public:
  int score;

  virtual QueryResult query(int a, int b) = 0;
  virtual int answer(const vector<int>& v) = 0;
};


// 本番用の入出力
class RealIO : public IO {
public:
  QueryResult query(int a, int b) override {
    /* 標準出力でクエリを投げる */
    return QueryResult(/* 標準入力で受け取ったクエリ結果 */);
  }

  int answer(const vector<int>& v) override {
    /* 標準出力で答えを投げる */
    return 0;
  }
};


// シミュレータ
class DummyIO : public IO {
public:
  DummyIO() {
    /* ジャッジ側と同様の手順で状態を初期化 */
  }

  QueryResult query(int a, int b) override {
    /* ジャッジ側と同様の手順でクエリ結果を生成 */
    return QueryResult(/* クエリ結果 */);
  }

  int answer(const vector<int>& v) override {
    score = /* ジャッジ側と同様の手順でスコアを計算 */
    return score;
  }
};


class Solver {
protected:
  shared_ptr<IO> io;
  int param;

public:
  Solver(shared_ptr<IO> io, int param) : io(io), param(param) {}

  int solve() {
    /* io を介して入出力を行い問題を解く */
    return io->score;
  }
};


int main() {
  const int trial_num = 10;
  vector<int> score_sum(10);

  // シミュレーションにより一番良さげな解法を特定
  for (int param = 0; param < 10; param++) {
    for (int i = 0; i < trial_num; i++) {
      auto dummy_io = make_shared<DummyIO>();
      score_sum[param] += Solver(dummy_io, param).solve();
    }
  }

  int best_param = distance(score_sum.begin(), max_element(score_sum.begin(), score_sum.end()));

  // 一番良さげな解法で本番に臨む
  auto real_io = make_shared<RealIO>();
  Solver(real_io, best_param).solve();  
}

嬉しい点

  • 入出力部分を切り出すことで、本番と全く同じコードでシミュレーションも回せる

留意点

  • シミュレーションをたくさん回す必要があり、計算コストが軽い解法でしか使えない