#1108172 (C++17) No.5022 XOR Printer

• 問題: No.5022 XOR Printer
• ユーザー: aa36
• 提出日時: 2025-07-26 19:09:02
• 言語: C++17 (gcc 13.3.0 + boost 1.87.0)
• 結果: AC
• 実行時間: 1,974 ms / 2,000 ms
• コード長: 9,129 bytes
• コンパイル時間: 2,669 ms
• コンパイル使用メモリ: 225,584 KB
• 実行使用メモリ: 7,716 KB
• スコア: 5,156,979,105
• 最終ジャッジ日時: 2025-07-26 19:10:49
• 合計ジャッジ時間: 106,223 ms
• ジャッジサーバーID （参考情報）: judge3 / judge6

ファイルパターン	結果
other	AC * 50

ソースコード

/*

No.5022 XOR Printer
20bit分考えるらしい
上bitから変更していくと良いのかも？

乱択をたくさんやる

*/

#include<bits/stdc++.h>
using namespace std;
using ll = long long;//int型は使わない
using vecl = vector<ll>;
using graph = vector<vector<ll>>;
using pll = pair<ll , ll>;
const ll inf = (1LL<<61); //約2e18
const ll MOD = 998244353;
const vecl dx={1,0,-1,0};
const vecl dy={0,1,0,-1};
#define rep(i,a,b) for(ll i=(ll)a; i<(ll)b; i++)
#define rrep(i,a,b) for(ll i=(ll)b-1; i>=(ll)a; i--)
#define all(vec1) (vec1).begin(), (vec1).end()
#define debug(var) cerr << #var << " : " << var << endl;
template<typename... Args>
void eerr(Args&&... args){
    ((std::cerr << args << ' '), ...) << '\n';
}
template<typename T>
std::istream& operator>>(std::istream& is, std::vector<T>& v) {
    v.clear();
    std::string line;
    std::getline(is >> std::ws, line); // 1行丸ごと読み込み
    std::stringstream ss(line);
    T x;
    while (ss >> x) {
        v.push_back(x);
    }
    return is;
}
//fastio
struct FastIO {
    FastIO() {
        std::ios::sync_with_stdio(false);
        std::cin.tie(nullptr);
    }
} fastio;
//modulo
template<typename T>
T ovr(T a,T b){
  T ret=a%b;
  if(ret<0)ret+=b;
  return ret;
}

namespace Rand
{
    unsigned long long XSseed = 12345678987654321;
    unsigned long long rand64u()
    {
        XSseed ^= XSseed << 13;
        XSseed ^= XSseed >> 7;
        XSseed ^= XSseed << 17;
        return XSseed ;
    }
    double randf()
    {
        return double(rand64u())/ULLONG_MAX ;
    }
    ll randint(ll MIN,ll MAX)
    {
        if(MAX-MIN<=0)
        {
            cerr << "Rand:randint: warn : MIN > MAX" << endl ;
            return MIN ;
        }
        return MIN+ll(rand64u()%(unsigned long long)(MAX-MIN));
    }
    //scoreは大きいほどよいときに使える関数
    ll rand_pick(vecl Vs , double temp)
    {
        if(Vs.size() == 0)return -1 ;
        //選ぶ
        ll ret = 0  ;
        rep(i,0,Vs.size())
        {
            if(Vs[i] > Vs[ret])
            {
                ret = i ;
            }
        }
        if(exp(Vs[ret] / temp) > randf())
        {
            return ret ;
        }else
        {
            return -1 ;
        }
    }
}
double get_time()
{
    return chrono::duration<double>(chrono::steady_clock::now().time_since_epoch()).count();
}
struct Time_Keeper
{
    double time_limit;
    ll counter = 0;
    ll freq = 1 ;
    double begin_time = get_time();
    vector<double> time_log ; //timeを記録しておく
    double start_time;
    
    Time_Keeper(double tm) : time_limit(0){
        time_limit = tm ;
    }
    //焼きなましを始める時(ただし初期解生成後)
    void start(){
        start_time = get_time() ;
    }
    //t(0<=t<=1でスケーリングしたもの)を返す
    double get_t(){
        double pre_time ;//計測はfreq回に1回することにする
        if(counter % freq == 0){
            pre_time = get_time() ;
            time_log.push_back(pre_time) ;
        }
        else{
            if(time_log.size() < 2){
                pre_time = get_time() ;
            }
            else{
                //線形補間する
                double tmp = time_log[time_log.size() - 1] - time_log[time_log.size() - 2];
                pre_time = time_log.back() + tmp * (counter % freq) / freq; 
            }
        }
        counter ++ ;
        return (pre_time - start_time) / (time_limit - (start_time - begin_time)) ;
    }
};


struct solution {
    pair<ll, string> best_sol = {-inf, ""}; // 最良の解法
    string current_sol = "";               // 現在構築中の解法
    ll current_score = -inf;

    // 新しい解法を開始
    void new_sol() {
        current_sol = "";
    }

    // 現在の解法に手順を追加
    void print(const string & x) {
        current_sol += x;
    }
    void set_score(ll x) {
        current_score = x;
    }
    // 現在の解法をbest_solと比較し、更新する
    void update_sol() {
        if (current_score > best_sol.first) {
            best_sol = {current_score , current_sol};
        }
    }

    // 最良の解法を出力
    void print_best_sol() {
        cerr << "best_score : " << best_sol.first << endl;
        rep(i,0,best_sol.second.size()){
            cout << best_sol.second[i] << endl;
        }
    }
};
solution SOL;

///variable
ll n,t;
ll s = 0;
graph save_a , a;
ll nx = 0 , ny = 0 ;
void ReadInput(){
    cin >> n >> t;
    save_a.resize(n) ;
    rep(i,0,n){rep(j,0,n){ll x;cin >> x;save_a[i].push_back(x);}}
}
void load(){
    a = save_a ;
    t = 1000 ;
    s = 0;
    nx = ny = 0;
}

ll g_now_x(ll gr_id){
    return gr_id / n;
}
ll g_now_y(ll gr_id){
    if(gr_id / n % 2 == 0){
        return gr_id % n;
    }else{
        return n - 1 - gr_id % n;
    }
}
bool inc(){
    t -- ;
    return (t == 0);
}
void debug_binary(ll x, const string& label = "") {
    if (!label.empty()) cerr << label << " : ";
    for (ll i = 20 - 1; i >= 0; --i) {
        cerr << ((x >> i) & 1);
    }
    cerr << " (" << x << ")\n";
}

bool pri_move(ll ax , ll ay , ll bx , ll by){
    if(ax < bx){
        for(ll _ = bx - ax ; _-- ; ){
            SOL.print("D") ;if(inc())return true;
        }
    }else{
        for(ll _ = ax - bx ; _-- ; ){
            SOL.print("U") ;if(inc())return true;
        }
    }
    if(ay < by){
        for(ll _ = by - ay ; _-- ; ){
            SOL.print("R") ;if(inc())return true;
        }
    }else{
        for(ll _ = ay - by ; _-- ; ){
            SOL.print("L") ;if(inc())return true;
        }
    }
    return false;
}
vector<pll> get_best_combination(ll g) {
    ll n = a.size();
    vector<pll> result = {};
    ll best_score = inf;
    if((s>>g)&1){
        best_score = s;
    }

    // 1個だけ
    rep(i1, 0, n) rep(j1, 0, n) {
        ll bitsum = a[i1][j1] ^ s;
        if (((bitsum >> g) & 1) == 1) {
            if (bitsum < best_score) {
                best_score = bitsum;
                result = { {i1, j1} };
            }
        }
    }

    // 2個
    rep(i1, 0, n) rep(j1, 0, n)
    rep(i2, 0, n) rep(j2, 0, n) {
        ll bitsum = a[i1][j1] ^ a[i2][j2] ^ s;
        if (((bitsum >> g) & 1) == 1) {
            if (bitsum < best_score) {
                best_score = bitsum;
                result = { {i1, j1}, {i2, j2} };
            }
        }
    }


    if(best_score == inf)return {{-1,-1}} ;
    return result;
}

unordered_set<ll> skipgrid ;
bool bit(ll g){
    //sのg bit目を1にする
    vector<pll> vb = get_best_combination(g) ;
    if(!vb.empty() && vb[0].first==-1)return false;//不可能
    if(vb.size()>0)for(pll x : vb){
        if(pri_move(nx , ny , x.first , x.second))return true;
        SOL.print("C");if(inc())return true;
        nx = x.first , ny = x.second ;
        s^=a[x.first][x.second];
    }
    //debug_binary(s);
    
    rep(i,0,n*n){
        if(skipgrid.find(i) != skipgrid.end())continue;
        if(pri_move(nx , ny , g_now_x(i) , g_now_y(i)))return true;
        nx = g_now_x(i) , ny = g_now_y(i) ;
        if((a[nx][ny]^s) > (a[nx][ny])){
            SOL.print("W");if(inc())return true;
            a[nx][ny] ^= s ;
        }
    }
    return false;
}
int solve()
{
    skipgrid = {} ;
    ll times = rand() % 10 + 1;
    rep(i,0,times)skipgrid.insert(Rand::randint(0 , n * n )) ;
    SOL.new_sol() ;
    rrep(i,1,20){
        if(bit(i)){
            break;
        }
        double base = std::max(1.0, (double)times + 1);
        bool pd = Rand::randf() < (base - skipgrid.size()) / base ;
        if (skipgrid.size() > 1 && pd) {
            ll pos = *skipgrid.begin();
            skipgrid.erase(skipgrid.begin());
            ll kx = g_now_x(pos);
            ll ky = g_now_y(pos);
            // 最良の (bi, bj) を探す：a[bi][bj] ^ a[kx][ky] ^ s を最大化
            ll best_val = s ^ a[kx][ky];
            pll best_pos = {-1, -1};
            rep(i, 0, n) rep(j, 0, n) {
                if(kx == i && ky == j)continue;
                ll val = a[i][j] ^ a[kx][ky] ^ s;
                if (val > best_val) {
                    best_val = val;
                    best_pos = {i, j};
                }
            }
        
            if (best_pos.first != -1) {
                ll bi = best_pos.first;
                ll bj = best_pos.second;
        
                if (pri_move(nx, ny, bi, bj)) break;
                nx = bi, ny = bj;
        
                SOL.print("C");
                if (inc()) break;
                s ^= a[bi][bj]; // 変化させる
            }
        
            // 最後に (kx, ky) に行って 'C'
            if (pri_move(nx, ny, kx, ky)) break;
            nx = kx, ny = ky;
            SOL.print("W");
            if (inc()) break;
            a[kx][ky] ^= s; 
        }

    }
    ll scr = 0;
    rep(i,0,n)rep(j,0,n)scr+=a[i][j] ;
    debug(scr);
    SOL.set_score (scr);
    SOL.update_sol();
    cerr << t << endl;
    return 0;
}
int main()
{
    Time_Keeper tk(1.97) ;
    tk.start();
    ReadInput();
    while(tk.get_t()<1)load(),solve();
    SOL.print_best_sol() ;
}