問題概要

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

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

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

KUPC 2020 C - Grid and Substrings

問題概要

考えたこと

実験コード