Grid_and_Substrings

// https://atcoder.jp/contests/kupc2020/tasks/kupc2020_c

#include <random>
#include "bits/stdc++.h"

using namespace std;

void solve() {
  const uint64_t seed = 3169617890;
  const int N = 18, CHAR_NUM = 26;
  mt19937_64 rnd{seed};

  vector<string> ss(N, string(N, '$'));

  for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
      char c = 'a' + rnd() % CHAR_NUM;
      ss[i][j] = c;
    }
  }

  auto calc_score = [&]() {
    int score = 0;
    vector<vector<int>> cnt(CHAR_NUM, vector<int>(CHAR_NUM));
    for (int i = 0; i < N; i++) {
      for (int j = 0; j < N; j++) {
        if (i + 1 < N) {
          int x = ss[i][j] - 'a', y = ss[i + 1][j] - 'a';
          if (cnt[x][y]) score++;
          cnt[x][y]++;
        }
        if (j + 1 < N) {
          int x = ss[i][j] - 'a', y = ss[i][j + 1] - 'a';
          if (cnt[x][y]) score++;
          cnt[x][y]++;
        }
      }
    }
    return score;
  };
  int score = calc_score(), counter = 0;
  while (score > 0) {
    counter++;
    int x = rnd() % N, y = rnd() % N;
    char nxtc = 'a' + rnd() % CHAR_NUM, prec = ss[x][y];
    ss[x][y] = nxtc;
    int nxtscore = calc_score();
    if (nxtscore <= score) {
      if (nxtscore < score) {
        const int MAX_SCORE = 2 * N * (N - 1);
        cout << "iter: " << counter << ", progress: " << (MAX_SCORE - nxtscore)
             << " / " << MAX_SCORE << endl;
      }
      score = nxtscore;
      continue;
    }
    ss[x][y] = prec;
  }
  for (auto s : ss) cout << s << endl;
}

int main() { solve(); }