SRM525 Div2Med DropCoins
問題概要
テーブルに有るコインを4方向にずらして枠外に振り落とせる。テーブル上に残るコインの数が、与えられた数Kに一致するための最小のテーブルの移動回数を求めよ。
解法
制約が小さく、テーブルが 30*30 なので単なる6重ループで求まるはずだが、二次元の累積和を取った4重ループでも解答可能。以下のコードは4重ループのコード。
またテーブルからコインを振り落とす際に盤面全体が移動していくので、四方向のうち反対の方向にずらそうとするときがあるので、それを注意して計算式を書く必要がある。解答では、押して引いた際に消費回数が小さい方向をみて、それを押し(引き)の分の2倍で求めている。
反省
600点問題だから少なくとも4重ループの二次元累積和の問題だろうと、勝手に身構えてオーダー計算見誤ってしまった。
#include <bits/stdc++.h> using namespace std; #define INF (1<<29) class DropCoins { public: int sum[52][52]; int mat[52][52]; int getMinimum(vector <string> board, int K) { int const H = board.size(); int const W = board[0].size(); memset(mat, 0, sizeof(mat)); for(int i=1; i<=H; i++) for(int j=1; j<=W; j++) mat[i][j] = board[i-1][j-1] == 'o'; memset(sum, 0, sizeof(sum)); for(int i=1; i<=H; i++) { for(int j=1; j<=W; j++) { sum[i][j] = mat[i][j] + sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1]; } } int ans = INF; for(int i=0; i<H; i++) for(int j=0; j<W; j++) for(int k=i+1; k<=H; k++) for(int l=j+1; l<=W; l++) if(sum[k][l] - sum[k][j] - sum[i][l] + sum[i][j] == K) { int cand = min((W-l)*2+j, (W-l)+j*2) + min((H-k)*2+i, (H-k)+i*2); ans = min(ans, cand); } if(ans == INF) return -1; else return ans; } };