REを2回出してしまった.
サンプルをちゃんと通そうらずひるど
発想難しい….
C - Make a Rectangle
解法
長方形の気持ちになると解けます.
一番長いアと二番目に長いアが答えなのでソートしてえいする.
ソース
おいおいサンプル通ってないやんけ(1RE).
#include <bits/stdc++.h> using namespace std; int main() { int N; map< int, int > mp; cin >> N; for(int i = 0; i < N; i++) { int A; cin >> A; ++mp[A]; } vector< int > luz{0}; for(auto &&p : mp) { if(p.second >= 4) luz.push_back(p.first); if(p.second >= 2) luz.push_back(p.first); } sort(luz.rbegin(), luz.rend()); cout << 1LL * luz[0] * luz[1] << endl; }
D - Coloring Dominoes
解法
思考停止すると, 左からメモ化再帰出来るためえい.
:= 列目以降で, 直前の列の上の色が , 下の色が だったときの組合せ
みたいなアレ.
ソース
#include <bits/stdc++.h> using namespace std; const int mod = 1e9 + 7; int N; string A, B; int dp[52][4][4]; int rec(int idx, int top, int bottom) { if(idx == N) return (1); if(~dp[idx][top][bottom]) return (dp[idx][top][bottom]); int ret = 0; if(A[idx] == B[idx]) { for(int i = 1; i <= 3; i++) { if(top != i && bottom != i) { (ret += rec(idx + 1, i, i)) %= mod; } } } else { for(int i = 1; i <= 3; i++) { for(int j = 1; j <= 3; j++) { if(top != i && bottom != j && i != j) { (ret += rec(idx + 2, i, j)) %= mod; } } } } return (dp[idx][top][bottom] = ret); } int main() { cin >> N; cin >> A; cin >> B; memset(dp, -1, sizeof(dp)); cout << rec(0, 0, 0) << endl; }
E - Don’t Be a Subsequence
解法
思考停止すると, 左からメモ化再帰できるためえい再び.
:= 文字目以降の部分文字列で, その部分列ではない最小の長さ
みたいなアレ.
各アで, 次に使う文字は a-z の 26 通り. 例えば次に文字 を使ったとき, そのときの解は rec( 文字以降で最初に現れる の位置 + 1) + 1 みたいになることが分かる(分かるので).
~~以降で最初に現れる は文字種別に取り出してソートしておくと, 雑にやっても くらいで求めることができるので, 計算量は .
今回は長さが最小かつ辞書順最小の文字列を出力する必要があるので, 復元する. 遷移時に次に使った文字を保存しておけば, rec() した情報をもとに調べることができる.
ソース
すぐ解けて喜んでたら, 配列サイズが足りなくてREして悲しい.
#include <bits/stdc++.h> using namespace std; const int INF = 1 << 30; string S; set< int > beet_aizu[26]; int dp[200005], nxt[200005]; int rec(int idx) { if(idx == S.size() + 1) return (0); if(dp[idx] < INF) return (dp[idx]); for(int i = 0; i < 26; i++) { int cost = rec(*beet_aizu[i].upper_bound(idx)) + 1; if(cost < dp[idx]) { dp[idx] = cost; nxt[idx] = i; } } return (dp[idx]); } void rec2(int idx) { if(nxt[idx] == -1) return; cout << (char) (nxt[idx] + 'a'); rec2(*beet_aizu[nxt[idx]].upper_bound(idx)); } int main() { cin >> S; for(int i = 0; i < S.size(); i++) { beet_aizu[S[i] - 'a'].emplace(i + 1); } for(int i = 0; i < 26; i++) { beet_aizu[i].emplace((int) S.size() + 1); } fill_n(dp, 200001, INF); memset(nxt, -1, sizeof(nxt)); rec(0); rec2(0); cout << endl; }
F - Flip and Rectangles
解法
選べる長方形が険しい条件なので言い換えたい気持ちになる.
考察すると(これは嘘で解説を見ると) のマスを見たときに黒マスを奇数個含むマスが, 選ぶ長方形の中に含まれていないことと, 問題の条件が同値ということがわかる.
含まれないかつ最大の長方形は, そういうアルゴリズムがあるためできる. .
ソース
天才だなぁ(思い浮かばない.
#include <bits/stdc++.h> using namespace std; int LargestRectangle(vector< int > height) { stack< int > st; height.push_back(0); vector< int > left(height.size()); int ret = 0; for(int i = 0; i < height.size(); i++) { while(!st.empty() && height[st.top()] >= height[i]) { ret = max(ret, (i - left[st.top()]) * height[st.top()]); st.pop(); } left[i] = st.empty() ? -1 : st.top(); st.emplace(i); } return (ret); } int main() { int H, W; bool mat[2000][2000] = {{}}; cin >> H >> W; for(int i = 0; i < H; i++) { string beet; cin >> beet; for(int j = 0; j < W; j++) mat[i][j] = beet[j] == '#'; } for(int i = 0; i < H - 1; i++) { for(int j = 0; j < W - 1; j++) { mat[i][j] ^= mat[i + 1][j]; mat[i][j] ^= mat[i + 1][j + 1]; mat[i][j] ^= mat[i][j + 1]; } } vector< int > height(W - 1, 1); int ret = max(H, W); for(int i = 0; i < H - 1; i++) { for(int j = 0; j < W - 1; j++) { if(mat[i][j]) height[j] = 1; else ++height[j]; } ret = max(ret, LargestRectangle(height)); } cout << ret << endl; }