結果

問題 No.5022 XOR Printer
コンテスト
ユーザー random contestant
提出日時 2025-07-26 16:32:41
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
MLE  
実行時間 -
コード長 4,870 bytes
コンパイル時間 6,394 ms
コンパイル使用メモリ 337,056 KB
実行使用メモリ 716,448 KB
スコア 0
最終ジャッジ日時 2025-07-26 16:33:40
合計ジャッジ時間 13,634 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other TLE * 12 MLE * 2 -- * 36
権限があれば一括ダウンロードができます

ソースコード

diff # 

// #define _GLIBCXX_DEBUG
#pragma GCC optimize("O3")
// #pragma GCC optimize("O2")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
using ll = long long;
#define rep(i,n) for (ll i = 0; i < (n); ++i)
using vl = vector<ll>;
using vvl = vector<vl>;
using P = pair<ll,ll>;
#define pb push_back
#define int long long
// #define double long double
#define INF (ll) 3e18
// Ctrl + Shift + B コンパイル
// Ctrl + C 中断
// ./m 実行


// No.5022 XOR Printer

int N = 10;
int T = 1000;
vvl a(10, vl(10));

void input() {
  cin >> N >> T;
  rep(i, 10) rep(j, 10) cin >> a[i][j];
}

int score() {
  int res = 0;
  for(auto x : a) for(auto y : x) res += y;
  return res;
}

vector<P> move_log;
string move_cycle;

void init(){
  // 経路を決め打ってしまおう
  for(int j = 1; j < 10; j++) {
    move_cycle.push_back('R');
    move_log.emplace_back(0, j);
  }
  for(int i = 1; i < 10; i++){
    if(i % 2) {
      move_cycle.push_back('D');
      for(int j = 9; j >= 1; j--){
        move_log.emplace_back(i, j);
        if(j != 1) move_cycle.push_back('L');
      }
    } else {
      move_cycle.push_back('D');
      for(int j = 1; j < 10; j++){
        move_log.emplace_back(i, j);
        if(j != 9) move_cycle.push_back('R');
      }
    }
  }
  move_cycle.push_back('L');
  for(int i = 9; i >= 0; i--) {
    move_log.emplace_back(i, 0);
    if(i != 0) move_cycle.push_back('U');
  }
  assert(move_log.size() == 100);
  assert(move_cycle.size() == 100);
  
   {
    const int REPEAT = 10;                 // 追加で 10 回複製 → 11 周分
    vector<P> base_move = move_log;            // 元の 100 要素を退避
    string    base_cycle = move_cycle;

    for(int r = 0; r < REPEAT; ++r){
      move_log.insert(move_log.end(), base_move.begin(), base_move.end());
      move_cycle += base_cycle;
    }
  }
}

struct state {
  int done256count = 0;
  map<int, string> available; // 0~255利用可能なスタンプ + 操作列
  vvl now_a;
  P prev = P(-1, -1);
  int stamped_this_turn = -1;
  int zobh = 0;

  // 「大きいほど小さい」順序
  bool operator<(const state& rhs) const {
    if (done256count != rhs.done256count)
      return done256count > rhs.done256count;   // 大きいほうを「より小さい」とみなす
    return available.size() > rhs.available.size();
  }
};

vector<vector<state>> beam(1001);

unordered_set<int> hash_seen;

void beamsearch() {
  for(auto & x : a) for(auto & y : x) y >>= 12;
  int beam_width = 100;
  {
    state start;
    start.available[0] = "";
    start.now_a = a;
    beam[0].push_back(start);
  }
  int best = 0;
  P best_where = P(-1, -1);
  rep(i, 1000){
    auto [ni, nj] = move_log[i];
    rep(is, beam[i].size()){
      state &sta = beam[i][is];
      state nxt = sta;
      if(nxt.stamped_this_turn != -1){
        nxt.available.clear();
        nxt.available[nxt.stamped_this_turn] = "";
        nxt.stamped_this_turn = -1;
      }
      nxt.prev = P(i, is);
      for(auto &x : nxt.available) x.second.push_back(move_cycle[i]);
      map<int, string> moved = nxt.available;
      for(auto &x : nxt.available){
        moved[x.first ^ nxt.now_a[ni][nj]] = x.second + 'C';
      }
      nxt.available = moved;
      if(nxt.now_a[ni][nj] != 255){
        int want = 255 ^ nxt.now_a[ni][nj];
        if(nxt.available.count(want) && want != 0){
          // 更新したやつを入れる
          state stamped = nxt;
          stamped.done256count++;
          stamped.now_a[ni][nj] = 255;
          stamped.zobh += ni*10007 + nj;
          stamped.zobh %= 1000000007;
          if(hash_seen.count(stamped.zobh)) continue;
          stamped.stamped_this_turn = want;
          stamped.available[want] += 'W';
          beam[i+1].push_back(stamped);
        }
      }
      beam[i+1].push_back(nxt);
    }
    if(beam[i+1].size() == 0){
      cerr << "ターン : " << i << endl;
      throw runtime_error("ビームが空");
    }
    sort(beam[i+1].begin(), beam[i+1].end());
    while(beam[i+1].size() > beam_width) beam[i+1].pop_back();
    // 解の更新
    if(beam[i+1][0].done256count > best){
      best = beam[i+1][0].done256count;
      best_where = P(i+1, 0);
    }
  }

  // best_where から復元
  vector<string> res;
  while(best_where.first != -1){
    auto [i, j] = best_where;
    state now = beam[i][j];
    if(now.stamped_this_turn != -1){
      res.push_back(now.available[now.stamped_this_turn]);
    }
    best_where = now.prev;
  }
  reverse(res.begin(), res.end());
  int count = 0;
  for(auto x : res) {
    for(auto y : x) {
      cout << y << " ";
      count++;
      if(count == 1000) break;
    }
    cout << endl;
    if(count == 1000) break;
  }
  if(count == 1000) cerr << "Force end" << endl;
  exit(0);
}

signed main(){
  input();
  init();
  beamsearch();
}
0