ei1333の日記

ぺこい

AtCoder Regular Contest 081

REを2回出してしまった.

サンプルをちゃんと通そうらずひるど

発想難しい….

C - Make a Rectangle

arc081.contest.atcoder.jp

解法

長方形の気持ちになると解けます.

一番長いアと二番目に長いアが答えなのでソートしてえいする.

ソース

おいおいサンプル通ってないやんけ(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

arc081.contest.atcoder.jp

解法

思考停止すると, 左からメモ化再帰出来るためえい.

{\mathrm{rec(idx, top, bottom)}} := {\mathrm{idx}} 列目以降で, 直前の列の上の色が {\mathrm{top}}, 下の色が {\mathrm{bottom}} だったときの組合せ

みたいなアレ.

ソース

#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

arc081.contest.atcoder.jp

解法

思考停止すると, 左からメモ化再帰できるためえい再び.

{\mathrm{rec(idx)}} := {\mathrm{idx}} 文字目以降の部分文字列で, その部分列ではない最小の長さ

みたいなアレ.

各アで, 次に使う文字は a-z の 26 通り. 例えば次に文字 {c} を使ったとき, そのときの解は rec( {\mathrm{idx}} 文字以降で最初に現れる {c} の位置 + 1) + 1 みたいになることが分かる(分かるので).

～～以降で最初に現れる {c} は文字種別に取り出してソートしておくと, 雑にやっても {O(\log |S|)} くらいで求めることができるので, 計算量は {O(26|S| \log |S|)}.

今回は長さが最小かつ辞書順最小の文字列を出力する必要があるので, 復元する. 遷移時に次に使った文字を保存しておけば, 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

arc081.contest.atcoder.jp

解法

選べる長方形が険しい条件なので言い換えたい気持ちになる.

考察すると(これは嘘で解説を見ると) {2 \times 2} のマスを見たときに黒マスを奇数個含むマスが, 選ぶ長方形の中に含まれていないことと, 問題の条件が同値ということがわかる.

含まれないかつ最大の長方形は, そういうアルゴリズムがあるためできる. {O(HW)}.

ソース

天才だなぁ(思い浮かばない.

#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;
}