AtCoder abc322 参加メモ

B - Prefix and Suffix

問題文通りに愚直にやる

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

int main() {
  int n,m; cin >> n >> m;
  string s,t; cin >> s >> t;

  auto t1 = t.substr(0,n);
  auto t2 = t.substr(m-n);
  int ans = 3;
  if (s == t1 && s == t2) ans = 0;
  if (s == t1 && s != t2) ans = 1;
  if (s == t2 && s != t1) ans = 2;
  cout << ans << endl;
  return 0;
}

C - Festival

二分探索でやると楽

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

int main() {
  int n,m; cin >> n >> m;
  vector<int> a(m);
  REP(i,m) cin >> a[i];
  for(int i = 1; i <= n; i++) {
    auto it = lower_bound(a.begin(),a.end(),i);
    cout << *it - i << endl;
  }
  return 0;
}

D - Polyomino

ポリオミノはそれぞれ回転(4) x 置く位置(4x4) = 64 通り置くパターンがある(重複やグリッドからはみ出るケースも含む)。それが3つあるため全探索すると 64³ 通り。これなら全探索でいける。

実装が重くプログラミング力が試される問題だった。

#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<n;i++)
#define endl '\n'
using P = pair<int,int>;
const int INF = 1e9;

int main() {
  vector p(3,vector<string>(4));
  REP(i,3) REP(j,4) cin >> p[i][j];

  auto rorate90 = [&](vector<string> &s) -> void {
    auto t = s;
    REP(i,4) REP(j,4) t[i][j] = s[3-j][i];
    s = t;
  };

  auto reset = [&](vector<P> &v) -> void {
    int minx = INF, miny = INF;
    for(auto [x,y]: v) {
      minx = min(minx,x);
      miny = min(miny,y);
    }
    for(auto& [x,y]: v) { x -= minx; y -= miny; }
  };

  // pa[i][j] := i番目のポリオミノを (j+1)*90 度回転させたときの座標の集合
  vector pa(3,vector(4,vector<P>()));
  REP(k,3) REP(r,4) {
    rorate90(p[k]);
    REP(i,4) REP(j,4) if (p[k][i][j] == '#') pa[k][r].emplace_back(i,j);
    reset(pa[k][r]); // 左上に詰める
  }

  auto dfs = [&](auto self, int i, vector<vector<bool>> now) {
    if (i == 3) {
      REP(ni,4) REP(nj,4) if (!now[ni][nj]) return false;
      return true;
    }

    bool res = false;
    for(auto npa: pa[i]) {
      REP(ni,4) REP(nj,4) {
        auto nnow = now;
        bool ok = true;
        for(auto [x,y]: npa) {
          auto check = [&]() -> bool {
            int nx = x+ni, ny = y+nj;
            if (nx < 0 || ny < 0 || nx >= 4 || ny >= 4) return false;
            if (nnow[nx][ny]) return false;
            return nnow[nx][ny] = true;
          };
          ok = ok && check();
        }
        res = res || (ok && self(self,i+1,nnow));
      }
    }
    return res;
  };

  bool ans = dfs(dfs,0,vector(4,vector<bool>(4)));
  cout << (ans ? "Yes" : "No") << endl;
  return 0;
}

E - Product Development

DPで解いた。 p <= 5 と小さいため p+1 進数で各パラメータの状態を持つようにした(p <= 5, k <= 5 なので最大でも 6⁵ の状態)

dp[i][j] := i まで見たときの各パラメータの集合が j のときのコストの最小値

#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<n;i++)
#define endl '\n'
using ll = long long;
const ll LINF = numeric_limits<ll>::max();

int main() {
  int n,k,p; cin >> n >> k >> p;
  vector<int> c(n);
  vector a(n,vector<int>(k));
  REP(i,n) {
    cin >> c[i];
    REP(j,k) cin >> a[i][j];
  }

  int base = p+1; // base 進数
  int sn = pow(base,k);
  // dp[i][j] := i 個までみたとき、パラメータ集合が j のときの最小コスト
  vector dp(n+1,vector<ll>(sn, LINF));
  dp[0][0] = 0;
  REP(i,n) REP(s,sn) {
    if (dp[i][s] == LINF) continue;
    // 選ばない
    dp[i+1][s] = min(dp[i+1][s],dp[i][s]);
    // 選ぶ
    int x = 1, nex = s;
    REP(j,k) {
      int now = s / x % base; // 現在のパラメータ値
      nex += (min(p, now + a[i][j]) - now) * x;
      x *= base;
    }
    dp[i+1][nex] = min(dp[i+1][nex],dp[i][s] + c[i]);
  }

  int x = 1, t = 0;
  REP(i,k) { t += p * x; x *= base; }
  if (dp[n][t] == LINF) dp[n][t] = -1;
  cout << dp[n][t] << endl;
  return 0;
}

雑感

D問題の実装重くて、ひやひやした。E問題もDPで解く方針はすぐに立てられたものの、パラメータの集合の持ち方が普段と違いすんなりいかなかった。もうちょっと早く解きたいところ。

tic40さんのAtCoder Beginner Contest 322での成績：1311位
パフォーマンス：1415相当
レーティング：1097→1133 (+36) :)
#AtCoder #ABC322 https://atcoder.jp/users/tic40/history/share/abc322?lang=ja