#1171813 (C++23) No.3593 I Love Sudoku

• 問題: No.3593 I Love Sudoku
• ユーザー: tkdgkb
• 提出日時: 2026-07-17 22:00:41
• 言語: C++23 (gcc 15.2.0 + boost 1.90.0)
• 結果: WA
• 実行時間: -
• コード長: 4,821 bytes
• コンパイル時間: 2,083 ms
• コンパイル使用メモリ: 342,156 KB
• 実行使用メモリ: 9,316 KB
• 最終ジャッジ日時: 2026-07-17 22:00:49
• 合計ジャッジ時間: 6,666 ms
• ジャッジサーバーID （参考情報）: judge2_1 / judge1_0

ファイルパターン	結果
other	WA * 1

ソースコード

#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int a[9][9], b[9][9], c[9][9];
int base_M[9][9] = {
    {0,1,2, 3,4,5, 6,7,8},
    {3,4,5, 6,7,8, 0,1,2},
    {6,7,8, 0,1,2, 3,4,5},
    {1,2,3, 4,5,6, 7,8,0},
    {4,5,6, 7,8,0, 1,2,3},
    {7,8,0, 1,2,3, 4,5,6},
    {2,3,4, 5,6,7, 8,0,1},
    {5,6,7, 8,0,1, 2,3,4},
    {8,0,1, 2,3,4, 5,6,7}
};

void calc_C() {
    for(int i = 0; i < 9; i++) {
        for(int j = 0; j < 9; j++) {
            int sum = a[i][0] * b[0][j] + a[i][1] * b[1][j] + a[i][2] * b[2][j]
                    + a[i][3] * b[3][j] + a[i][4] * b[4][j] + a[i][5] * b[5][j]
                    + a[i][6] * b[6][j] + a[i][7] * b[7][j] + a[i][8] * b[8][j];
            c[i][j] = sum % 9;
        }
    }
}

int calc_score() {
    int score = 0;
    for(int i = 0; i < 9; i++) {
        int m1 = 0, m2 = 0;
        for(int j = 0; j < 9; j++) {
            m1 |= (1 << c[i][j]);
            m2 |= (1 << c[j][i]);
        }
        score += 18 - __builtin_popcount(m1) - __builtin_popcount(m2);
    }
    for(int r = 0; r < 9; r += 3) {
        for(int c0 = 0; c0 < 9; c0 += 3) {
            int mk = 0;
            for(int i = 0; i < 3; i++) {
                mk |= (1 << c[r+i][c0]) | (1 << c[r+i][c0+1]) | (1 << c[r+i][c0+2]);
            }
            score += 9 - __builtin_popcount(mk);
        }
    }
    return score;
}

struct Move {
    int is_a, type, v1, v2;
};

Move get_random_move() {
    Move m;
    m.is_a = rng() % 2;
    m.type = rng() % 5;
    if(m.type == 0 || m.type == 1) {
        int b_idx = rng() % 3;
        m.v1 = b_idx * 3 + rng() % 3;
        m.v2 = b_idx * 3 + rng() % 3;
        while(m.v1 == m.v2) m.v2 = b_idx * 3 + rng() % 3;
    } else if(m.type == 2 || m.type == 3) {
        m.v1 = rng() % 3;
        m.v2 = rng() % 3;
        while(m.v1 == m.v2) m.v2 = rng() % 3;
    } else {
        m.v1 = rng() % 9;
        m.v2 = rng() % 9;
        while(m.v1 == m.v2) m.v2 = rng() % 9;
    }
    return m;
}

void apply_move(int M[9][9], Move m) {
    if(m.type == 0) {
        for(int i = 0; i < 9; i++) swap(M[m.v1][i], M[m.v2][i]);
    } else if(m.type == 1) {
        for(int i = 0; i < 9; i++) swap(M[i][m.v1], M[i][m.v2]);
    } else if(m.type == 2) {
        for(int k = 0; k < 3; k++) {
            for(int i = 0; i < 9; i++) swap(M[m.v1*3+k][i], M[m.v2*3+k][i]);
        }
    } else if(m.type == 3) {
        for(int k = 0; k < 3; k++) {
            for(int i = 0; i < 9; i++) swap(M[i][m.v1*3+k], M[i][m.v2*3+k]);
        }
    } else {
        for(int i = 0; i < 9; i++) {
            for(int j = 0; j < 9; j++) {
                if(M[i][j] == m.v1) M[i][j] = m.v2;
                else if(M[i][j] == m.v2) M[i][j] = m.v1;
            }
        }
    }
}

void randomize_matrix(int M[9][9]) {
    for(int i = 0; i < 9; i++) {
        for(int j = 0; j < 9; j++) M[i][j] = base_M[i][j];
    }
    for(int step = 0; step < 300; step++) {
        Move m = get_random_move();
        apply_move(M, m);
    }
}

void print_ans() {
    for(int i = 0; i < 9; i++) {
        for(int j = 0; j < 9; j++) cout << a[i][j] << (j == 8 ? "" : " ");
        cout << "\n";
    }
    for(int i = 0; i < 9; i++) {
        for(int j = 0; j < 9; j++) cout << b[i][j] << (j == 8 ? "" : " ");
        cout << "\n";
    }
}

void solve() {
    auto start_time = chrono::steady_clock::now();
    auto get_time = [&]() {
        return chrono::duration<double>(chrono::steady_clock::now() - start_time).count();
    };

    while(get_time() < 1.90) {
        randomize_matrix(a);
        randomize_matrix(b);
        calc_C();
        int score = calc_score();

        if(score == 0) {
            print_ans();
            return;
        }

        double temp_start = 5.0;
        double temp_end = 0.1;
        int steps = 150000;
        int backup_c[9][9];
        
        for(int step = 0; step < steps; step++) {
            if(step % 1024 == 0 && get_time() > 1.90) return;
            
            double pct = (double)step / steps;
            double temp = temp_start * pow(temp_end / temp_start, pct);

            Move m = get_random_move();
            memcpy(backup_c, c, sizeof(c));

            apply_move(m.is_a ? a : b, m);
            calc_C();
            int nxt_score = calc_score();

            if(nxt_score == 0) {
                print_ans();
                return;
            }

            int delta = nxt_score - score;
            if(delta <= 0 || (rng() % 100000) / 100000.0 < exp(-delta / temp)) {
                score = nxt_score;
            } else {
                apply_move(m.is_a ? a : b, m);
                memcpy(c, backup_c, sizeof(c));
            }
        }
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
}