https://beta.atcoder.jp/contests/ddcc2017-qual/tasks
去年の予選です。ばちゃコンしました。
ABはい
C set
D
とりあえず、対称な4マスずつに分けて考えれば良いことがわかります。
すると縦に対称、横に対称、3マス塗られている、4マス塗られているの4パターンについて考えればよいです。
しかし最初に縦か横に対称性がある時、除かなくてはならないことに注意です。
int N, M; int A, B; string S[MAX_N]; void solve() { cin >> N >> M; cin >> A >> B; int V = 0, H = 0, D = 0, C = 0; bool odd = false; rep(i, 0, N) cin >> S[i]; rep(i, 0, N / 2) { rep(j, 0, M / 2) { int cnt = 0; cnt += (S[i][j] == 'S'); cnt += (S[i][M - 1 - j] == 'S'); cnt += (S[N - 1 - i][j] == 'S'); cnt += (S[N - 1 - i][M - 1 - j] == 'S'); if(cnt == 4) D++; if(cnt == 3) { C++; odd = true; } if(cnt == 2) { if(S[i][j] == S[N - 1 - i][j] && S[i][M - 1 - j] == S[N - 1 - i][M - 1 - j]) V++; else if(S[i][j] == S[i][M - 1 - j] && S[N - 1 - i][j] == S[N - 1 - i][M - 1 - j]) H++; else odd = true; } if(cnt == 1) odd = true; } } if(odd || (V && H)) cout << max(A * (V + C), B * (H + C)) + (max(A, B) + A + B) * D + A + B << "\n"; else { if(V) cout << max(A * (V + C - 1), B * (H + C)) + (max(A, B) + A + B) * D + A + B << "\n"; //C == 0 else if(H) cout << max(A * (V + C), B * (H + C - 1)) + (max(A, B) + A + B) * D + A + B << "\n"; // C == 0 else cout << max(A * (V + C), B * (H + C)) + (max(A, B) + A + B) * D << "\n"; //C == 0, V == 0, H == 0 } }
場合分けを詰めるタイプの問題苦手なんだよなぁ。