AGC44振り返り

AGC44の振り返りをします。

結果は一問も解けずに、レートが下がってしまいました(´･ω･`)

ratedの機会はたくさんあるので結果に囚われすぎす、しっかり復習してできることを増やしていきます。

コンテスト後に他の方の解説などを見聞きしてA,B問題を理解できました。

A問題

A - Pay to Win

問題の流れとは逆にNから0に減らしていく過程を考えます。

2,3,5で割る方法を利用する場合は、出来るだけ先に割る行為を先に行った方がいいことがわかります。
1ずつ減らしていくのが最小のコストですむ場合も忘れずに考えます。

以下のような再帰を含むアルゴリズムで書くことができました。

map<ll,ll> m;
ll A, B, C, D;
ll solve(ll N){
 if(N < 10) cout << N << endl;
 if(N == 0) return 0;
 if(N == 1) return D;
 if(m.count(N)) return m[N];

 m[N] = 1e18;
 if(N / 1e9 * D < 3e9) m[N] = min(m[N] , N * D);

 m[N] = min(m[N] , A + D * (N % 2) + solve(N / 2) );
 m[N] = min(m[N] , A + D * (2 - N % 2) + solve((N + 2) / 2) );

 m[N] = min(m[N] , B + D * (N % 3) + solve(N / 3) );
 m[N] = min(m[N] , B + D * (3 - N % 3) + solve((N + 3) / 3) );

 m[N] = min(m[N] , C + D * (N % 5) + solve(N / 5) );
 m[N] = min(m[N] , C + D * (5 - N % 5) + solve((N + 5) / 5) );

 return m[N];

}

int main(){
 ll T; cin >> T;
 vector<ll> ans;
 rep(i,T){
   ll N; cin >> N; cin >> A >> B >> C >> D;
   m.clear();
   ll tmp = solve(N);
   ans.pb(tmp);
 }
 rep(i,T) cout << ans[i] << endl;
}

Nは2,3,5で必要な時に+1,-1することでO(log N)回割れるので計算量はO(log N)^3で求められます。

実際には最も近い2,3,5それぞれの倍数だけ見ればいいはずですが、実装がこちらの方が簡単なので両隣の2,3,5の倍数をみています。

B問題

B - Joker

全てのマスに対して外周までに通る人の数を保存します。

その上で随時dfsで通る人の数を減らしていけば間に合う問題でした。

毎回の人の出入りの計算がO(N^2)です。
そのそれぞれに関してdfsで通る人の人数を減らすことができる場合があります。

そのdfsでの推移の回数は、最初と最後の状態から数えることができます。
最後はどこにいても自由で出入りできるようになるので全てのマスでコスト0で出れます。
最初は一番外側が0、内側に入っていくに従って1ずつ増えていきます。
よって最初の前マスのコストの総和は、0*N^2 + 1*(N - 2)^2 + 2*(N - 4)^2 + ...と計算できます。
この値はO(N^3)なのでN <= 500の元では十分に間に合います。

従って計算量はdfsがネックでO(N^3)で求められることがわかりました。

// 四方向への移動ベクトル
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};

ll d[MAX][MAX];
bool maze[MAX][MAX];

void dfs(ll x , ll y){
 ll z = d[x][y] + maze[x][y];
 // 距離が減るところをdfsで減らす
 rep(i,4){
   ll nx = x + dx[i];
   ll ny = y + dy[i];
   if(nx < 0 or ny < 0) continue;
   if(d[nx][ny] > z){
     d[nx][ny] = z;
     dfs(nx , ny);
   }
 }
}

int main(){
 ll N; cin >> N;
 ll ans = 0;
 // 外周までの距離の初期設定
 rep(i,N) rep(j,N) d[i][j] = min( min(i, j) , min(N - i - 1 , N - j - 1) );
 // pの入力
 vector<ll> p(N * N); rep(i,N * N) cin >> p[i]; rep(i, N * N) p[i]--;
 // mazeの初期化、埋まったところからはそのままいける
 rep(i,MAX) rep(j,MAX) maze[i][j] = true;
 // dfsの操作
 rep(i, N * N){
   ll x = p[i] / N;
   ll y = p[i] % N;
   ans += d[x][y];
   maze[x][y] = false;
   dfs(x, y);
 }
 cout << ans << endl;
}

コンテスト中にA,B問題が解けるくらいになりたいです^ ^

アドバイスやコメントなどあったらぜひお願いします。