#1162570 (C++23) No.5024 魔法少女うなと宝集め

• 問題: No.5024 魔法少女うなと宝集め
• ユーザー: bird01
• 提出日時: 2026-05-02 17:47:26
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 1,954 ms / 2,000 ms
• コード長: 4,197 bytes
• コンパイル時間: 3,923 ms
• コンパイル使用メモリ: 345,568 KB
• 実行使用メモリ: 6,400 KB
• スコア: 1,687,782
• 最終ジャッジ日時: 2026-05-02 17:49:56
• 合計ジャッジ時間: 111,366 ms
• ジャッジサーバーID （参考情報）: judge1_1 / judge3_0

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

ソースコード

#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define uniq(v) (v).erase(unique(all(v)),(v).end()) // 使用前にソートする
#define l_rot(x) rotate(x.begin(),x.begin()+1,x.end());
#define r_rot(x) rotate(x.rbegin(),x.rbegin()+1,x.rend());
#define sz(x) (int)((x).size())
#define fo(x) cout<<x<<endl
#define int long long
#define vi vector<int>
#define vvi vector<vi>
#define vvvi vector<vvi>
#define vp vector<P>
#define vvp vector<vp>
#define vt vector<tuple<int,int,int>>
#define vs vector<string>
#define vm vector<mint>
#define vvm vector<vm>
#define vb vector<bool>
#define vvb vector<vb>
#define fi first
#define se second
using namespace std;
using ll = long long;
using ull = unsigned long long;
using P = pair<int,int>;
#define ppcll __builtin_popcountll
int my_ceil(int a, int b){return (a+(b-1))/b;}
int my_ceil_pm(int a, int b){return ((a*b>0?1:-1)*(abs(a)+(abs(b)-1)))/abs(b);}
template<typename T> T my_max(T a, T b){return a<b?b:a;}
template<typename T> T my_min(T a, T b){return a<b?a:b;}
int gcd(int a, int b){return b?gcd(b,a%b):a;}
int lcm(int a, int b){return a*(b/gcd(a,b));}
void dec_all(vi &A){ rep(i,0,sz(A)) A[i]--;}
template <typename T> bool chmin(T &a, const T& b){if(a>b){a=b; return true;}return false;}
template <typename T> bool chmax(T &a, const T& b){if(a<b){a=b; return true;}return false;}
template<typename T> using min_priority_queue = priority_queue<T, vector<T>, greater<T>>;
const int dx[]={-1,0,1,0,-1,1,1,-1}; // 上,左,下,右,左上,左下,右下,右上
const int dy[]={0,-1,0,1,-1,-1,1,1};

const long long INF=1e18;//8e18;

bool is_outer_range(int R1,int r1,int R2,int r2){
  return (r1<0 or R1<=r1 or r2<0 or R2<=r2);
}

signed main(){
  // 時間管理
  using namespace std::chrono;
  auto t0 = steady_clock::now();
  const double TIME_LIMIT = 1.95;
  
  // 乱数
  mt19937 rng((uint64_t)chrono::steady_clock::now().time_since_epoch().count());
  auto randint = [&](int L, int R){ return uniform_int_distribution<int>(L,R)(rng); }; // [L,R]を生成

  int N,T;
  cin >> N >> T;
  vvi A(N,vi(N));
  rep(i,0,N) rep(j,0,N) cin >> A[i][j];

  int best_score=0;
  vi best_ax,best_ay;
  
  // 渦巻き
  int sxs[4]={0,N-1,0,N-1};
  int sys[4]={0,0,N-1,N-1};
  int ofss[2]={1,3};
  rep(t,0,4){
    rep(u,0,2){
      int x=sxs[t],y=sys[t];
      int dir=0;

      int score=0;
      vvi vis(N,vi(N));
      vi ax,ay;

      rep(i,0,T){
        score+=A[x][y];
        vis[x][y]=1;

        ax.emplace_back(x);
        ay.emplace_back(y);

        while(1){
          int nx=x+dx[dir];
          int ny=y+dy[dir];

          bool need_reroll=false;
          if(is_outer_range(N,nx,N,ny)) need_reroll=true; // 範囲外再抽選
          else if(vis[nx][ny]) need_reroll=true; // 訪問済再抽選

          if(!need_reroll) break;
          dir=(dir+ofss[u])%4;
        }
        x+=dx[dir];
        y+=dy[dir];
      }

      if(chmax(best_score,score)){
        swap(best_ax,ax);
        swap(best_ay,ay);
      }
    }
  }
  
  // 貪欲解
  while(true){
    double elapsed = duration<double>(steady_clock::now()-t0).count();
    if(elapsed > TIME_LIMIT) break;

    // 初期座標
    int sx=randint(0, N-1);
    int sy=randint(0, N-1);
    
    // 貪欲に最大T個まで取っていく
    int score=0;
    int x=sx,y=sy;
    vvi vis(N,vi(N));
    vi ax,ay;
    rep(i,0,T){
      score+=A[x][y];
      vis[x][y]=1;

      ax.emplace_back(x);
      ay.emplace_back(y);

      int nd=-1;
      int mx=0;
      rep(dir,0,4){
        int nx=x+dx[dir];
        int ny=y+dy[dir];
        if(is_outer_range(N,nx,N,ny)) continue; // 範囲外スキップ
        if(vis[nx][ny]) continue; // 訪問済スキップ
        if(chmax(mx,A[nx][ny])){
          nd=dir;
        }
      }
      if(nd==-1) break;
      x+=dx[nd];
      y+=dy[nd];
    }

    // 最良解更新
    if(chmax(best_score,score)){
      swap(best_ax,ax);
      swap(best_ay,ay);
    }
  }
  
  // 出力
  fo(sz(best_ax));
  rep(i,0,sz(best_ax)) cout << best_ax[i] << ' ' << best_ay[i] << endl;
}