けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AOJ ???? Grid and Substrings (KUPC 2020 C)

山登り法で見つかった!スコアが下がっていくのを眺めるの快感!

問題概要

 N \times N のグリッドに以下の条件を満たすように英小文字を入れよ。

  • 横方向、縦方向に連結しているマス目を抜き出してできる文字列は  N^{2}(N-1) 個ある
  • そのすべてが互いに相異なる

これを実現した  N の値に応じてスコアが与えられる。 N = 13 で満点が与えられる。

考えたこと

長さ 2 の文字列のみ互いに相異なれば必要かつ十分!!!
13 × 13 のマス目に 0〜25 の値を入れる方法であって、どの隣接する 2 マスについてもそのペアの値が互いに相異なるようにしたい。

そこで、各ペアについてのヒストグラムを作って、その各項についての高さ  h に対して  h(h-1) の値の総和をスコアとすることにした。そのスコアが 0 になるまで

  • グリッドの 1 マスをランダムに選んで
  • そのマスの値をランダムに書き換える

としてあげて、改善されるならそれを採用、改善されないなら reject するのをひたすら繰り返した。

現実的な時間でスコア = 0 に収束した。具体的に求まったのは以下のもの。

13
bxerzpkbrwtwf
arxhnewpqhvnz
pvyuiikclaujy
tkrsurafygdnm
ckumbfqiakhyc
psgiesabojwbs
fcamyzevrdgyq
kgnfohzsiwjjf
iqchfjvdloqsf
ngultueadsvle
pgzqyvpixomhb
jcwqwcmoigsrn
axzoxjputhkpr

実験コード

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

unsigned int randInt() {
    static unsigned int tx = 123456789, ty=362436069, tz=521288629, tw=88675123;
    unsigned int tt = (tx^(tx<<11));
    tx = ty; ty = tz; tz = tw;
    return ( tw=(tw^(tw>>19))^(tt^(tt>>8)) );
}

int randInt(int minv, int maxv) {
    return randInt() % (maxv - minv + 1) + minv;
}

using pint = pair<int,int>;
int calc(const vector<vector<int>> &a) {
    map<pint,int> collecter;
    for (int i = 0; i < a.size(); ++i) {
        for (int j = 0; j+1 < a.size(); ++j) {
            collecter[(pint(a[i][j], a[i][j+1]))]++;
            collecter[(pint(a[j][i], a[j+1][i]))]++;
        }
    }
    int res = 0;
    for (auto it : collecter) res += it.second*(it.second-1);
    return res;
}

int main() {
    vector<vector<int>> a(13, vector<int>(13, 0));
    int score = calc(a);
    while (score) {
        int i = randInt(0, 12);
        int j = randInt(0, 12);
        int v = randInt(0, 25);
        int p = a[i][j];
        a[i][j] = v;
        int nscore = calc(a);
        if (nscore < score) score = nscore;
        else a[i][j] = p;
    }
    int N = 13;
    cout << N << endl;
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) cout << (char)('a'+a[i][j]);
        cout << endl;
    }
}