atcoder abc183 E - Queen on Grid

問題

E - Queen on Grid

解法

DP + 累積和。

dp配列は、 dp[i][j] = {i,j}地点に到達できる場合の数 で考える。

するとdp[i][j] は以下のように3方向のdpの累積を足すと求められる。

dp[i][j] = dp[i][j-1] + dp[i][j-2] ... + dp[i][0]
 + dp[i-1][j] + dp[i-2][j] ... + dp[0][j]
 + dp[i-1][j-1] + dp[i-2][j-2] ... + dp[0][0]

毎回dpの累積を計算すると計算量が増えてしまうため、累積和で高速化する。

dp[i][j] = 右移動の累積和 + 下移動の累積和 + 右下移動の累積 
#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<n;i++)
// mint は省略

const int MX = 2005;
int h,w;
char s[MX][MX];
mint dp[MX][MX];
mint x[MX][MX], y[MX][MX], z[MX][MX]; // 3方向それぞれの累積和. x: 右方向, y: 下方向, z: 右下方向

void f(int i, int j) {
  if (s[i][j] == '#') return;

  if (0 <= j-1) x[i][j] = x[i][j-1] + dp[i][j-1];
  if (0 <= i-1) y[i][j] = y[i-1][j] + dp[i-1][j];
  if (0 <= i-1 && 0 <= j-1) z[i][j] = z[i-1][j-1] + dp[i-1][j-1];

  dp[i][j] = x[i][j] + y[i][j] + z[i][j];
}

int main() {
  cin >> h >> w;
  REP(i,h) REP(j,w) cin >> s[i][j];

  dp[0][0] = 1;
  REP(i,h) REP(j,w) {
    if (i == 0 && j == 0) continue;
    f(i,j);
  }

  cout << dp[h-1][w-1] << endl;
  return 0;
}

atcoder ABC 104 D - We Love ABC

問題

D - We Love ABC

解法

? があると複雑なため、まずは ? 抜きで考えてみる。 素朴に3重ループでA->B->Cとなるパターンを総当りしてみる。

#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<n;i++)
using ll = long long;

int main() {
  string s; cin >> s;
  int n = s.size();

  ll ans = 0;
  REP(i,n) {
    for(int j=i+1; j<n; j++) {
      for(int k=j+1; k<n; k++) {
        ans += (s[i]=='A' && s[j]=='B' && s[k]=='C');
      }
    }
  }
  cout << ans << endl;
}

$O(N{^3})$ では制約に間に合わないためDPで考えてみる。

dp[n][4]; // [n文字までで][1: Aまで, 2: Bまで, 3: Cまでを満たす状態]

ll dp[100000][4];

int main() {
  string s; cin >> s;
  int n = s.size();

  dp[0][0] = 1;
  REP(i,n) {
    REP(j,4) dp[i+1][j] += dp[i][j]; // i+1の各状態にiの状態の数をそのまま足す

    if (s[i] == 'A') dp[i+1][1] += dp[i][0]; // Aにすすめる
    else if (s[i] == 'B') dp[i+1][2] += dp[i][1]; // Bにすすめる
    else if (s[i] == 'C') dp[i+1][3] += dp[i][2]; // Cにすすめる
  }

  cout << dp[n][3] << endl;
}

? の場合を考慮する。

// mint にする
mint dp[100000][4];

int main() {
  string s; cin >> s;
  int n = s.size();

  dp[0][0] = 1;
  REP(i,n) {
    REP(j,4) dp[i+1][j] += s[i]== '?' ? dp[i][j]*3 : dp[i][j]; // ?の場合は3文字ありえる

    if (s[i] == 'A') dp[i+1][1] += dp[i][0];
    else if (s[i] == 'B') dp[i+1][2] += dp[i][1];
    else if (s[i] == 'C') dp[i+1][3] += dp[i][2];
    else if (s[i] == '?') { // ? の場合はA, B, C それぞれ考慮する
      dp[i+1][1] += dp[i][0];
      dp[i+1][2] += dp[i][1];
      dp[i+1][3] += dp[i][2];
    }
  }

  cout << dp[n][3] << endl;
  return 0;
}

雑感

DPムズい

AtCoder ABC 180 E - Traveling Salesman among Aerial Cities

問題

E - Traveling Salesman among Aerial Cities

解法

巡回セールスマン問題。

ナイーブな全探索では $O(N{!})$ かかるため、 $ n=17 $ では時間切れになる。

そこでbitDPと呼ばれる手法を使う。 bitDPでは計算量が $ O(N{^2}2{^n})$ となるため今回の制約下では十分間に合う。

dp配列定義

dp[訪れた都市の集合(bitで表現)][今いる都市番号] = 最小コスト
// 集合はbitで表現する.
// bitのn桁目が0だとn都市は未訪問、1だと訪問済

dpの更新

// 訪れた都市集合が i のとき、j 都市から k 都市への移動
dp[ i|1<<k ][k] = min(
  dp[ i|1<<k ][k],
  dp[i][j] + cost[i][j]
);  

コード

#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<n;i++)
template<class T>bool chmin(T &a,const T &b) {if(b<a){a=b; return 1;} return 0;}
const int INF = 1e9;

int main() {
  int n; cin >> n;
  int x[n],y[n],z[n];
  REP(i,n) cin >> x[i] >> y[i] >> z[i];

  // dp定義: [訪れた都市集合][今いる都市] = 最小コスト
  // 訪れた都市集合はbitで表現する
  // INF(十分大きい値)で初期化する
  vector<vector<int>> dp(1<<n,vector<int>(n,INF));

  // 都市iから都市jへのコストを事前計算
  int cost[n][n];
  REP(i,n) REP(j,n) {
    int c1 = abs(x[j]-x[i]);
    int c2 = abs(y[j]-y[i]);
    int c3 = max(0,z[j]-z[i]);
    cost[i][j] = c1+c2+c3;
  }

  // 開始点0から各都市への移動
  REP(i,n) {
    // 0から0への移動はスキップ
    if (i==0) continue;
    dp[1<<i][i] = cost[0][i];
  }

  REP(i,1<<n) {
    REP(j,n) {
      // j都市のフラグが立っていない場合
      // 未訪問のj都市からは移動できないのでスキップ
      if (~i>>j&1) continue;
      REP(k,n) {
        // k都市のフラグが立っている場合
        // 訪問済みなのでスキップ
        if (i>>k&1) continue;
        chmin(dp[i|1<<k][k], dp[i][j]+cost[j][k]);
      }
    }
  }

 // 全てに訪問済みで今いる都市が0(開始点に戻ってきている)の最小コスト
  cout << dp[(1<<n)-1][0] << endl;
}

HHKB プログラミングコンテスト 2020 D - Squares

問題

D - Squares

解法

解説: Editorial - HHKB Programming Contest 2020

上記解説手順で解いてみる

#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<n;i++)
typedef long long ll;
const int mod = 1000000007;
// mintは省略 https://github.com/atcoder/ac-library

int main() {
  int t;
  cin >> t;
  REP(i,t) {
    ll n,a,b;
    cin >> n >> a >> b;

    // N正方形内に赤と青の正方形を置く全パターンを求める
    mint ax = n-a+1; // N内にaの区間を置くパターン
    mint bx = n-b+1; // N内にbの区間を置くパターン
    mint all = ax*ax*bx*bx;

    // 赤い正方形の内部と青い正方形の内部が重なるケースを求める
    // x4: 空白マスはn-a-b. (空白)(赤)(空白)(青)(空白) となるため空白+(赤と青分の+2)から2つを選ぶ組み合わせを求める
    mint x4 = a+b <= n ? (n-a-b+2)*(n-a-b+1)/2 : 0;
    mint x3 = x4*2;
    mint x2 = ax*bx-x3;
    mint x1 = x2*x2;

    // 全体から内部が重なるケースを引く
    mint ans = all-x1;
    cout << ans << endl;
  }
}

atcoder ABC 100 D - Patisserie ABC

問題

D - Patisserie ABC

解法

公式解説が詳しいのでそこに書いてある通り。

https://img.atcoder.jp/abc100/editorial.pdf

$ x,y,z $ の3要素の正方向と負方向の組み合わせは $ 2 ^ 3 $ 通り。 それぞれの組み合わせで $ x,y,z $ の合計が大きいものから $ M $ 個を取って合計が一番大きいものが答えとなる。

#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<n;i++)
using ll = long long;

int main() {
  int n,m;
  cin >> n >> m;
  ll x[n],y[n],z[n];
  REP(i,n) cin >> x[i] >> y[i] >> z[i];

  ll sum[1<<3][n],ans = 0;

  for (int bit = 0; bit < (1<<3); bit++) { // bit全探索
    REP(i,n) {
      sum[bit][i] = 0;
      // bitが立っているところは正方向、立ってなければ負方向
      sum[bit][i] += (bit >> 0 & 1) ? x[i] : -x[i];
      sum[bit][i] += (bit >> 1 & 1) ? y[i] : -y[i];
      sum[bit][i] += (bit >> 2 & 1) ? z[i] : -z[i];
    }

    sort(sum[bit], sum[bit]+n, greater<ll>()); // 降順ソート
    ll tmp = 0;
    REP(i,m) tmp += sum[bit][i]; // 大きいものからM個を合計する
    if (ans < tmp) ans = tmp;
  }

  cout << ans << endl;
}

雑感

  • 貪欲法的なアプローチ
  • 正/負方向を8通り決め打ちして考える、というのを思いつくのが難しい

atcoder ABC 099 D - Good Grid

問題

D - Good Grid

解法

  • $ (i+j) \% 3 $ なので条件を満たすために使う色は3色のみ
  • 事前に $ (i+j) \% 3 $ を3パターンに塗ったときのそれぞれのコストを計算しておく
  • 全ての色の組み合わせについて調べる(全探索)。$O(N{^3})$ となるが $ C=30 $ の制約には十分間に合う
#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<n;i++)

int N,C;
int d[30][30],c[500][500];
int cost[3][30];
int ans=1e9;

int main() {
  cin >> N >> C;
  REP(i,C) REP(j,C) cin >> d[i][j];
  REP(i,N) REP(j,N) cin >> c[i][j], c[i][j]--;

  REP(x,C) REP(i,N) REP(j,N) {
    cost[(i+j)%3][x] += d[c[i][j]][x];
  }

  REP(i,C) REP(j,C) REP(k,C) {
    if (i==j || j==k || k==i) continue;
    ans = min(ans, cost[0][i]+cost[1][j]+cost[2][k]);
  }

  cout << ans << endl;
}

雑感

  • 問題文を理解するのに時間がかかった
  • 事前計算が大事

atcoder ABC 098 D - Xor Sum 2

問題

D - Xor Sum 2

解法

全探索すると $O(N{^2})$となり間に合わないため、計算量を減らす工夫が必要になる。

この問題は単調増加する区間の数え上げなので、尺取り法の要領で解くことができる。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define REP(i,n) for(int i=0;i<n;i++)

int main() {
  int n,sum=0,r=0; cin >> n;
  vector<int> a(n);
  REP(i,n) cin >> a[i];

  ll ans=0;
  REP(l,n) {
    while(r < n) {
      // xor と sum が等しくなければ条件を満たさないので終了する
      if ((sum^a[r]) != (sum+a[r])) break;
      sum += a[r];
      r++;
    }
    ans += r-l;

    if (r == l) r++;
    sum -= a[l];
  }

  cout << ans << endl;
  return 0;
}