Official
B - Number Box Editorial by PCTprobability
まず、高橋君がどのマスから出発するかを全探索します。
次に、高橋君が進む方向を全探索します。
すると、高橋君が通ったマスに書かれている数字を左から通った順番に並べた整数が確定するためこれを求め、それらの最大値を取ればよいです。
最大で \(10\) 桁の数を扱うため、32bit型整数でなく、64bit型整数などを使いましょう。
実装上の注意ですが、\(8\) 方向のいずれかに進むか探索する場合
vector<int> x={1,1,1,0,0,-1,-1,-1},y={1,0,-1,1,-1,1,0,-1}
などの配列を用意すると便利です。
また、マス目の上下と左右が繋がっていることに関しては、今いる座標を \(\bmod\ N\) で管理すれば実装が楽になります。
高橋君が通ったマスに書かれている数字を左から通った順番に並べた整数を求めるときははじめ整数 \(X=0\) を持ち、マスを移動するたびに \(X\) を \(10\) 倍し、\(X\) に今いるマスに書かれた整数を足す。とすると楽になります。
C++ の実装例
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
int n;
cin>>n;
ll ans=0;
vector<vector<ll>> a(n,vector<ll>(n));
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
char c;
cin>>c;
a[i][j]=c-'0';
}
}
vector<int> p={1,1,1,0,0,-1,-1,-1},q={1,0,-1,1,-1,1,0,-1};
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
for(int k=0;k<8;k++){
ll now=0;
ll x=i,y=j;
for(int l=0;l<n;l++){
now*=10;
now+=a[x][y];
x+=p[k];
y+=q[k];
x%=n;
x+=n;
y%=n;
y+=n;
x%=n;
y%=n;
}
ans=max(ans,now);
}
}
}
cout<<ans<<endl;
}
posted:
last update: