ferinの競プロ帳

競プロについてのメモ

AOJ2447 A Two Floors Dungeon

競技プログラミング AOJ

問題ページ
A Two Floors Dungeon | Aizu Online Judge

解法

制約を見るとSがかなり小さい。盤面の状態の変化を全て持つと2^(50*50)で明らかに持てないがスイッチのON/OFFの全通りの2^Sであれば十分持てる。こうすると d[スイッチの状態][x座標][y座標][何階か] = (最短操作回数) として拡張dijkstraができそう。
あらかじめ2^S通りのスイッチのON/OFFについての盤面の状態を求めておく。すると、各状態で上下左右に移動できるか、階の上下ができるか、スイッチがあるかなどの判定がO(1)でできて遷移はO(1)になる。状態数O(HW2^S)なので計算量は問題なくて通る。

かなりややこしくって実装に時間がかかった…

ソースコード

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
#define int ll
using VI = vector<int>;
using VVI = vector<VI>;
using PII = pair<int, int>;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define PB push_back

const ll LLINF = (1LL<<60);
const int INF = (1LL<<30);
const int MOD = 1000000007;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template <typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; }
template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); }
template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
  out<<'('<<a.first<<','<<a.second<<')';
  return out;
}
template<class T>
ostream &operator <<(ostream& out,const vector<T>& a){
  out<<'[';
  REP(i, a.size()) {out<<a[i];if(i!=a.size()-1)out<<',';}
  out<<']';
  return out;
}

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

int d[1<<10][55][55][2];
signed main(void)
{
  cin.tie(0);
  ios::sync_with_stdio(false);

  int w, h;
  cin >> w >> h;
  vector<string> board(h);
  REP(i, h) cin >> board[i];
  int s;
  cin >> s;
  vector<vector<string>> t(s, vector<string>(h));
  REP(i, s) REP(j, h) cin >> t[i][j];

  vector<vector<string>> ope(1<<s, vector<string>(h));

  int sx = -1, sy = -1, gx = -1, gy = -1;
  REP(y, h) REP(x, w) {
    if(board[y][x] == '%') sx = x, sy = y, board[y][x] = '_';
    if(board[y][x] == '&') gx = x, gy = y, board[y][x] = '_';
  }

  REP(i, 1<<s) {
    ope[i] = vector<string>(h, string(w, '.'));
    REP(j, s) if(i&1<<j) {
      REP(y, h) REP(x, w) {
        if(t[j][y][x] == '*') {
          if(ope[i][y][x] == '*') ope[i][y][x] = '.';
          else ope[i][y][x] = '*';
        }
      }
    }
    REP(y, h) REP(x, w) {
      if(ope[i][y][x] == '*') {
        if(board[y][x] == '_') ope[i][y][x] = '^';
        else if(board[y][x] == '^') ope[i][y][x] = '_';
        else if('a' <= board[y][x] && board[y][x] <= 'z') {
          ope[i][y][x] = board[y][x] - ('a' - 'A');
        } else if('A' <= board[y][x] && board[y][x] <= 'Z') {
          ope[i][y][x] = board[y][x] + ('a' - 'A');
        } else ope[i][y][x] = board[y][x];
      } else {
        ope[i][y][x] = board[y][x];
      }
    }
  }

  REP(i, 1<<s) REP(j, h) REP(k, w) REP(l, 2) d[i][j][k][l] = LLINF;
  d[0][sy][sx][0] = 0;
  priority_queue<VI, VVI, greater<VI>> que;
  que.push({d[0][sy][sx][0], 0, sy, sx, 0});

  while(que.size()) {
    VI v = que.top(); que.pop();
    int mask = v[1], y = v[2], x = v[3], fl = v[4];
    if(d[mask][y][x][fl] < v[0]) continue;
    // 上下左右への移動
    REP(i, 4) {
      int nx = x + dx[i], ny = y + dy[i];
      char tmp[2] = {'_', '^'};
      bool cond = ope[mask][ny][nx] == tmp[fl] || (isupper(ope[mask][ny][nx]) && fl == 1) || (islower(ope[mask][ny][nx]) && fl == 0) || (ope[mask][ny][nx] == '|');
      if(IN(0LL, w, nx) && IN(0LL, h, ny) && cond
        && d[mask][ny][nx][fl] > d[mask][y][x][fl] + 1) {
        d[mask][ny][nx][fl] = d[mask][y][x][fl] + 1;
        que.push({d[mask][ny][nx][fl], mask, ny, nx, fl});
      }
    }
    // 階段
    if(ope[mask][y][x] == '|' && d[mask][y][x][!fl] > d[mask][y][x][fl] + 1) {
      d[mask][y][x][!fl] = d[mask][y][x][fl] + 1;
      que.push({d[mask][y][x][fl], mask, y, x, !fl});
    }
    // スイッチ
    if(isupper(ope[mask][y][x]) && fl == 1) {
      int nmask = mask ^ (1<<(ope[mask][y][x]-'A'));
      int nfl = fl;
      if((isupper(ope[nmask][y][x]) && islower(ope[mask][y][x]))
        || (islower(ope[nmask][y][x]) && isupper(ope[mask][y][x]))) {
        nfl = !nfl;
      }
      if(d[nmask][y][x][nfl] > d[mask][y][x][fl] + 1) {
        d[nmask][y][x][nfl] = d[mask][y][x][fl] + 1;
        que.push({d[nmask][y][x][nfl], nmask, y, x, nfl});
      }
    }
    if(islower(ope[mask][y][x]) && fl == 0) {
      int nmask = mask ^ (1<<(ope[mask][y][x]-'A'));
      int nfl = fl;
      if((isupper(ope[nmask][y][x]) && islower(ope[mask][y][x]))
        || (islower(ope[nmask][y][x]) && isupper(ope[mask][y][x]))) {
        nfl = !nfl;
      }
      if(d[nmask][y][x][nfl] > d[mask][y][x][fl] + 1) {
        d[nmask][y][x][nfl] = d[mask][y][x][fl] + 1;
        que.push({d[nmask][y][x][nfl], nmask, y, x, nfl});
      }
    }
  }

  int ret = LLINF;
  REP(i, 1<<s) REP(j, 2) chmin(ret, d[i][gy][gx][j]);
  if(ret == LLINF) cout << -1 << endl;
  else cout << ret << endl;

  return 0;
}

AOJ2741 インビジブル

競技プログラミング AOJ

問題ページ インビジブル | Aizu Online Judge

考えたこと

  • ゲーム系だけど制約が小さいので全探索系っぽい
  • minmaxをする感じで考える
  • 持ちたい状態を考えると山札の何枚目を見ているか、スタックに何枚あるか、どっちのターンかあたり
  • スタックにある枚数を持っておけばパスしたときの得点計算はできそう
  • 再帰DPみたいな感じで書く
  • よくよく考えるとスタックの上に乗っているのがどっちのカードか、スタックが0枚の状態で何回パスしたかを持っておきたいので状態に加える
  • minmaxを書くと通った

がんばって状態をまとめて全探索
実装パートでインデックスずらすみたいな悲しい事件が起きやすそう

ソースコード

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
#define int ll
using VI = vector<int>;
using VVI = vector<VI>;
using PII = pair<int, int>;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define PB push_back

const ll LLINF = (1LL<<60);
const int INF = (1LL<<30);
const int MOD = 1000000007;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template <typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; }
template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); }
template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
  out<<'('<<a.first<<','<<a.second<<')';
  return out;
}
template<class T>
ostream &operator <<(ostream& out,const vector<T>& a){
  out<<'[';
  REP(i, a.size()) {out<<a[i];if(i!=a.size()-1)out<<',';}
  out<<']';
  return out;
}

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

int n, m;
int card[2][55];
bool used[55][55][105][2][5];
int dp[55][55][105][2][5];
int func(int x, int y, int s, int turn, int type) {
  if(used[x][y][s][turn][type]) return dp[x][y][s][turn][type];

  // 1pのターン
  if(turn == 0) {
    int ret = -INF;
    // スタックに置く
    if(x != n) chmax(ret, func(x+1, y, s+1, !turn, 0));
    // パス
    if(type == 4) chmax(ret, 0LL);
    else if(type == 3) chmax(ret, func(x, y, 0, !turn, 4));
    else if(type == 2) chmax(ret, func(x, y, 0, !turn, 3));
    else {
      int score = 0, idx1 = x-1, idx2 = y-1;
      bool flag1 = false, flag2 = false;
      while(s > 0) {
        if(type == 0) {
          if(card[type][idx1] == -1) flag2 = true;
          else if(!flag1) score += card[type][idx1];
          idx1--;
        } else if(type == 1) {
          if(card[type][idx2] == -1) flag1 = true;
          else if(!flag2) score -= card[type][idx2];
          idx2--;
        }
        type = !type;
        s--;
      }
      chmax(ret, func(x, y, 0, !turn, 2) + score);
    }
    used[x][y][s][turn][type] = true;
    return dp[x][y][s][turn][type] = ret;
  }
  else {
    int ret = INF;
    // スタックに置く
    if(y != m) chmin(ret, func(x, y+1, s+1, !turn, 1));
    // パス
    if(type == 4) chmin(ret, 0LL);
    else if(type == 3) chmin(ret, func(x, y, 0, !turn, 4));
    else if(type == 2) chmin(ret, func(x, y, 0, !turn, 3));
    else {
      int score = 0, idx1 = x-1, idx2 = y-1;
      bool flag1 = false, flag2 = false;
      while(s > 0) {
        if(type == 0) {
          if(card[type][idx1] == -1) flag2 = true;
          else if(!flag1) score += card[type][idx1];
          idx1--;
        } else if(type == 1) {
          if(card[type][idx2] == -1) flag1 = true;
          else if(!flag2) score -= card[type][idx2];
          idx2--;
        }
        s--;
        type = !type;
      }
      chmin(ret, func(x, y, 0, !turn, 2) + score);
    }
    used[x][y][s][turn][type] = true;
    return dp[x][y][s][turn][type] = ret;
  }
}

signed main(void)
{
  cin.tie(0);
  ios::sync_with_stdio(false);

  cin >> n >> m;
  REP(i, n) cin >> card[0][i];
  REP(i, m) cin >> card[1][i];

  cout << func(0, 0, 0, 0, 2) << endl;

  return 0;
}

AOJ2606 Perm Query

競技プログラミング AOJ

問題ページ
Perm Query | Aizu Online Judge

解法

各iについて周期が高々40以下といういかにも使えと言っている制約があるので使う。各iについて周期がcnt[i]、1周期でretに加算される合計をsum[i]とする。すると各iを繰り返す回数は区間[l,r]のcnt[i]のlcmに対してlcm/cnt[i]となる。したがって各クエリに対して sum_{i=l}^r lcm/cnt[i]*sum[i] が答えになる。
これを愚直に計算するのではO(NQ)でTLEしそう。区間のlcmはセグ木とかで求められそうだな～とか考えてると、そもそもcnt[i]とsum[i]のペアをセグ木に乗せればよさそうなことに気づく。(cnt,sum)をセグ木の各頂点に乗せるとしてこのマージの演算を考えると、f*1 = (lcm(a1,b1), lcm(a1,b1)/a1*a2+lcm(a1,b1)/b1*b2) と定義すればよさそう。この演算は結合則を満たすし、単位元は(0,1)とすればよさそう。したがってセグ木に乗せられる。各クエリについてO(logN)で答えられるのでO(QlogN)になって通る。

一家に一本抽象化セグ木

ソースコード

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
#define int ll
using VI = vector<int>;
using VVI = vector<VI>;
using PII = pair<int, int>;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define PB push_back

const ll LLINF = (1LL<<60);
const int INF = (1LL<<30);
const int MOD = 1000000007;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template <typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; }
template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); }
template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
  out<<'('<<a.first<<','<<a.second<<')';
  return out;
}
template<class T>
ostream &operator <<(ostream& out,const vector<T>& a){
  out<<'[';
  REP(i, a.size()) {out<<a[i];if(i!=a.size()-1)out<<',';}
  out<<']';
  return out;
}

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

template <typename monoid>
class segmentTree {
public:
  using M = monoid;
  using T = typename M::value_type;

  int sz;
  vector<T> x;

  segmentTree(int n = 1e5) {
    sz = 1; while(sz < n) sz *= 2;
    init();
  }
  void init() { x.assign(sz*2, M::id()); }

  // [a, b)
  T query(int a, int b, int k, int l, int r) {
    if(r <= a || b <= l) return M::id();
    if(a <= l && r <= b) return x[k];
    return M::f(query(a, b, 2*k+1, l, (l+r)/2),
                query(a, b, 2*k+2, (l+r)/2, r));
  }
  T query(int a, int b) {return query(a, b, 0, 0, sz);}
  // 点更新
  void update(int i, const T &val) {
    i += sz-1;
    x[i] = M::g(x[i], val);
    while(i > 0) {
      i = (i-1) / 2;
      x[i] = M::f(x[i*2+1], x[i*2+2]);
    }
  }
};

template <typename T>
struct min_monoid {
  using value_type = T;
  static constexpr T id() { return std::numeric_limits<T>::max(); }
  static T f(const T &a, const T &b) { return min(a, b); }
  static T g(const T &a, const T &b) { return b; }
};
template <typename T>
struct max_monoid {
  using value_type = T;
  static constexpr T id() { return std::numeric_limits<T>::min(); }
  static T f(const T &a, const T &b) { return max(a, b); }
  static T g(const T &a, const T &b) { return b; }
};

struct mono {
  using value_type = PII;
  static constexpr PII id() {return {1, 0};}
  static PII f(const PII &a, const PII &b) {
    int l = a.first / __gcd(a.first, b.first) * b.first;
    return {l, (l/a.first%MOD*a.second%MOD + l/b.first%MOD*b.second%MOD) % MOD};
  }
  static PII g(const PII &a, const PII &b) { return b; }
};

signed main(void)
{
  cin.tie(0);
  ios::sync_with_stdio(false);

  int n, q;
  cin >> n >> q;
  VI p(n), l(q), r(q);
  REP(i, n) cin >> p[i], p[i]--;
  REP(i, q) cin >> l[i] >> r[i];

  VI x(n);
  REP(i, n) x[i] = i;

  VI cnt(n, -1);
  VI sum(n, 0);
  REP(i, 40) {
    REP(j, n) {
      x[j] = p[x[j]];
      if(cnt[j] == -1) (sum[j] += x[j]+1) %= MOD;
      if(cnt[j] == -1 && x[j] == j) cnt[j] = i+1;
    }
  }

  segmentTree<mono> seg(n);
  REP(i, n) seg.update(i, {cnt[i], sum[i]});
  REP(i, q) cout << seg.query(l[i]-1, r[i]).second << endl;

  return 0;
}

*1:a1,a2)*(b1,b2

AOJ1350 There is No Alternative

競技プログラミング AOJ

問題ページ
There is No Alternative | Aizu Online Judge

解法

ある最小全域木Tの辺をひとつ交換して構成できる全域木が最小全域木であれば、その辺はno alternative bridgeではない。ある辺を除去したときに代わりに加えたときに全域木になる辺を列挙したい。辺eを除去することで木Tがグラフg1とg2に別れたとする。このとき、g1の頂点とg2の頂点をつなぐ辺はこの条件を満たすはずである。したがって辺を除去したあとで各頂点がどちらの連結成分に含まれるのか調べることで辺を列挙することができる。これはO(N+M)のdfsを行うことでできる。除去を試す辺はO(N)本なので合計O(N(N+M))で通る。
最小全域木Tを構成
→Tの辺eを除去
→各頂点がどちらの連結成分に含まれるか調べる
→グラフの各辺が全域木になる辺か調べる
→条件を満たしていればno alternative bridgeとしてカウント

交換可能な枝とか基本カットセットについて知ってたので考察がスムーズだった。

ソースコード

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
#define int ll
using VI = vector<int>;
using VVI = vector<VI>;
using PII = pair<int, int>;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define PB push_back

const ll LLINF = (1LL<<60);
const int INF = (1LL<<30);
const int MOD = 1000000007;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template <typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; }
template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); }
template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
  out<<'('<<a.first<<','<<a.second<<')';
  return out;
}
template<class T>
ostream &operator <<(ostream& out,const vector<T>& a){
  out<<'[';
  REP(i, a.size()) {out<<a[i];if(i!=a.size()-1)out<<',';}
  out<<']';
  return out;
}

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

class UnionFind {
public:
  const static int MAX_N = 505;
  int par[MAX_N];
  int s[MAX_N];
  UnionFind() { init(); }
  UnionFind(int n) { init(n); }
  void init() { for(int i=0; i<MAX_N; ++i) par[i] = i, s[i] = 1; }
  void init(int n) { for(int i=0; i<n; ++i) par[i] = i, s[i] = 1; }
  int find(int x) {
    if(par[x] == x) return x;
    return par[x] = find(par[x]);
  }
  void unite(int x, int y) {
    x = find(x);
    y = find(y);
    if(x == y) return;
    if(s[x] < s[y]) par[x] = y, s[y] = s[x] + s[y];
    else par[y] = x, s[x] = s[x] + s[y];
  }
  bool same(int x, int y) { return find(x) == find(y);}
};
UnionFind uf;

signed main(void)
{
  cin.tie(0);
  ios::sync_with_stdio(false);

  int n, m;
  cin >> n >> m;
  VVI edge(m, VI(3, 0));
  REP(i, m) {
    int a, b, c;
    cin >> a >> b >> c;
    a--, b--;
    edge[i] = {c, a, b};
  }

  VVI g(500, VI());
  VVI tree;
  sort(ALL(edge));
  REP(i, m) {
    if(uf.same(edge[i][1], edge[i][2])) continue;
    uf.unite(edge[i][1], edge[i][2]);
    g[edge[i][1]].PB(edge[i][2]);
    g[edge[i][2]].PB(edge[i][1]);
    tree.PB(edge[i]);
  }

  int cnt = 0, ret = 0;
  int type[505] = {};
  bool used[505] = {};

  // cout << tree << endl;
  REP(i, tree.size()) {
    function<void(int,int)> dfs = [&](int v, int t) {
      type[v] = t;
      used[v] = true;
      for(auto e: g[v]) {
        bool cond = tree[i][1] == v && tree[i][2] == e;
        cond |= tree[i][2] == v && tree[i][1] == e;
        if(!used[e] && !cond) dfs(e, t);
      }
    };
    // tree[i] を削除したときの頂点の分割
    int t = 0;
    memset(used, false, sizeof(used));
    REP(j, n) {
      if(used[j]) continue;
      dfs(j, t);
      t++;
    }
    bool ok = true;
    REP(j, m) {
      // j番目のedgeの両端のtypeが異なる
      if(tree[i] == edge[j]) continue;
      if(type[edge[j][1]] != type[edge[j][2]] && tree[i][0] == edge[j][0]) {
        ok = false;
        break;
      }
    }
    if(ok) {
      cnt++;
      ret += tree[i][0];
    }
  }

  cout << cnt << " " << ret << endl;

  return 0;
}

AOJ1246 Concert Hall Scheduling

競技プログラミング AOJ

問題ページ
Concert Hall Scheduling | Aizu Online Judge

考えたこと

  • 区間が飛んでくるのでとりあえず終端でソートする
  • 区間が3つ以上かぶるような日があるとだめ
  • 今までに選んだ区間ですでに2つかぶっているような日が存在
  • その日よりも始点が前の区間を使うのは不可能
  • 終点でソートしてるので始点が前にあると確実に内包しているといえる
  • かぶっている日のうち最も遅い日付が意味がある
  • 終点ソートしてるのでもっと前でかぶっていたら最も遅い日でもかぶっているので
  • すでに1つ、2つかぶっているような日付を持っておきたい
  • dp[i番目][2つかぶっている最も遅い日][1つ被っている最も遅い日] = (最大の収入)
  • 日付の最大をLとすると計算量がO(NL^2)で間に合いそう
  • dpテーブルを全部持つとMLEしそうなので2つだけもつ空間削減テクをする
  • 通る

とりあえず終点ソートするの本当に強い
終点ソートしてあると見るべきものが減るパターンが多い

ソースコード

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
#define int ll
using VI = vector<int>;
using VVI = vector<VI>;
using PII = pair<int, int>;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define PB push_back

const ll LLINF = (1LL<<60);
const int INF = (1LL<<30);
const int MOD = 1000000007;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template <typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; }
template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); }
template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
  out<<'('<<a.first<<','<<a.second<<')';
  return out;
}
template<class T>
ostream &operator <<(ostream& out,const vector<T>& a){
  out<<'[';
  REP(i, a.size()) {out<<a[i];if(i!=a.size()-1)out<<',';}
  out<<']';
  return out;
}

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

int dp[2][405][405];
signed main(void)
{
  cin.tie(0);
  ios::sync_with_stdio(false);

  while(true) {
    int n;
    cin >> n;
    if(!n) break;
    VVI v;
    REP(i, n) {
      int l, r, w;
      cin >> l >> r >> w;
      v.PB({r, l, w});
    }

    sort(ALL(v));

    memset(dp, -1, sizeof(dp));
    int cur = 0, nxt = 1;
    dp[cur][0][0] = 0;
    REP(i, n) {
      REP(j, 366) REP(k, 366) {
        if(dp[cur][j][k] == -1) continue;
        int l = v[i][1], r = v[i][0], w = v[i][2];
        // iを使う
        if(l > j) {
          int nj = l <= k ? k : j;
          chmax(dp[nxt][nj][r], dp[cur][j][k] + w);
        }
        // iを使わない
        chmax(dp[nxt][j][k], dp[cur][j][k]);
      }
      // curとnxtをうまくやるやつ
      swap(cur, nxt);
      REP(j, 366) REP(k, 366) dp[nxt][j][k] = -1;
    }

    int ans = 0;
    REP(i, 366) REP(k, 366) chmax(ans, dp[cur][i][k]);
    cout << ans << endl;
  }

  return 0;
}

AOJ 2306 Rabbit Party

競技プログラミング AOJ

問題ページ
Rabbit Party | Aizu Online Judge

考えたこと

  • 入力がグラフっぽい
  • グラフとしてサンプルを書いてみるけどグラフの知ってるもの(最大安定集合とか)に帰着できない
  • DPを考える
  • dp[i匹目まで][j匹選んだ] みたいなの
  • 今までに選んだうさぎの部分集合を状態に持たないとできる気がしない
  • 2^100を持てるわけがない
  • DPできる気がしないので貪欲を考える
  • i匹選ぶ時の最適な部分集合が単調増加するみたいな
  • そんな性質はない
  • DPも貪欲もできる気がしない
    -----解説を見た-----
  • xとyの友好度が0のとき、xとyを両方取る意味はない
  • クリークの大きさの最大値はそんなに大きくない
  • 大きさNのクリークではN*(N+1)/2本の辺が必要
  • 辺がm本しかないので N*(N+1)/2 <= m = 100 でNが抑えられる
  • クリークの要素数は高々14個
  • 全探索できる

学び

  • クリークの大きさはO(sqrt(m))くらいで抑えられる
  • クリークを全列挙する実装

ソースコード

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
#define int ll
using VI = vector<int>;
using VVI = vector<VI>;
using PII = pair<int, int>;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define PB push_back

const int INF = (1LL<<30);

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }

int n, m, ans;
int g[105][105];

void dfs(VI &v) {
  if(v.size() >= 2) {
    int tmp = 0;
    REP(i, v.size()) {
      int t = INF;
      REP(j, v.size()) if(i != j) {
        chmin(t, g[v[i]][v[j]]);
      }
      tmp += t;
    }
    chmax(ans, tmp);
  }

  int last = v.back();
  FOR(i, last+1, n) {
    bool ok = true;
    for(int j: v) {
      if(g[i][j] == 0) {
        ok = false;
        break;
      }
    }
    if(ok) {
      v.PB(i);
      dfs(v);
      v.pop_back();
    }
  }
}

signed main(void)
{
  cin.tie(0);
  ios::sync_with_stdio(false);

  cin >> n >> m;
  REP(i, m) {
    int a, b, c;
    cin >> a >> b >> c;
    a--,  b--;
    g[a][b] = g[b][a] = c;
  }

  REP(i, n) {
    VI v({i});
    dfs(v);
  }

  cout << ans << endl;

  return 0;
}

AOJ1604 デッドロック検出

競技プログラミング AOJ

問題ページ
Deadlock Detection | Aizu Online Judge

考えたこと

  • とりあえずサンプルを読む
  • あるスレッドで{1,2}が獲得されてて3を取りたい、別のスレッドで{3}を獲得してて1を取りたい→デッドロック
  • あるuから次のuまでに同じ数字が2回以上出てくる→デッドロック
  • 命令のi番目まで見たときに獲得してるロックの集合と次に取りたいロックのpairを持っておきたい気持ちになる
  • 上をv[i] = (獲得してるロックの集合,次に獲得するロック)としてもつ
  • v[i].second が v[j].first に含まれ、v[j].second が v[i].first に含まれ、 v[i].first と v[j].first が共通要素を持たないならデッドロックが起きている
  • スレッド2個しか使わないのでは（は？）と思ってO(N^2)を書くとサンプルで落ちてる
  • スレッド3個以上でしかデッドロックにならない場合は当然ある
  • 命令のi番目まで実行していて次の命令を実行したい
  • このとき命令のj番目まで実行しているスレッドがあると実行できないなら i->j の辺を張る
  • このグラフ上で閉路が存在したらデッドロックが起きる気がする
  • 有向グラフのループ検出なのでトポロジカルソートをする
  • 出すと落ちる
  • スレッドは最大10個しかないので長さ11以上の閉路があったとしてもデッドロックにはならない
  • トポロジカルソートでループに入ってる頂点はわかるのでその頂点集合についてUFで連結成分ごとに分ける
  • ループごとの長さが分かる気がしたのでこれで出すと落ちる
  • 冷静に考えると閉路がくっついているようなパターンがあって無理
  • これ高速にするの無理そう
    -------解説を見た-------
  • 獲得しているロックの集合Sと次に取るロックがtという状態を取りうるか?
  • dp[S][t] = (true or false) みたいなDP配列を考える
  • dp[s1][t1] = dp[s2][t2] = true で s1とs2の共通部分が存在せず、t1 が s2に属するとき dp[s1 | s2][t2] = true も成り立つ
  • 上で考えた通り s1とs2の共通部分が存在せず、t1 が s2に属し、t2 が s1 に属するとき デッドロックが生じる
  • dp配列を更新しつつデッドロックが起きる状態があるか確認していく

ソースコード

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
#define int ll

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define PB push_back

int dp[1<<10][10];
signed main(void)
{
  cin.tie(0);
  ios::sync_with_stdio(false);

  while(true) {
    int n;
    cin >> n;
    if(!n) break;
    string s;
    cin >> s;

    memset(dp, false, sizeof(dp));
    int now = 0;
    bool safe = true;
    REP(i, n) {
      if(s[i] == 'u') now = 0;
      else {
        dp[now][s[i]-'0'] = true;
        if(now & 1<<(s[i]-'0')) {
          safe = false;
          break;
        }
        now |= 1<<(s[i]-'0');
      }
    }

    if(!safe) {
      cout << "UNSAFE" << endl;
      continue;
    }

    REP(s1, 1<<10) REP(t1, 10) {
      if(!dp[s1][t1]) continue;
      // dp[s1][t1] と マージ
      REP(s2, 1<<10) REP(t2, 10) {
        if(!dp[s2][t2]) continue;
        bool cond1 = !(s1&s2) && (s2 & 1 << t1),
             cond2 = !(s1&s2) && (s1 & 1 << t2);
        if(cond1 && cond2) {
          safe = false;
        } else if(cond1) {
          dp[s1 | s2][t2] = true;
        } else if(cond2) {
          dp[s1 | s2][t1] = true;
        }
      }
    }

    if(safe) cout << "SAFE" << endl;
    else cout << "UNSAFE" << endl;
  }

  return 0;
}