ferinの競プロ帳

競プロについてのメモ

AOJ2712 Escape

競技プログラミング AOJ

問題ページ
Escape | Aizu Online Judge

考えたこと

  • 閉路が存在すればそこでUターンできる
  • つまり1->閉路->1みたいな移動ができる
  • 閉路にたどり着くまでの頂点は必ず訪れることができる
  • 閉路の先にある頂点の集合は最後に取ることしてどれか一箇所しか取れない
  • 閉路を検出したい気持ちになるので二重辺連結成分分解をする
  • 二重辺連結成分分解をしたあとの木で探索をする
  • 根の頂点1が含まれる二重辺連結成分からdfsをして閉路までを辿る
  • この探索で必ず訪れられる二重辺連結成分と一箇所しか取れない頂点集合を分類
  • 一箇所しか取れない頂点集合のうち重みが最大の集合を取るとする

二重辺連結成分初めて書いた

ソースコード

#include <bits/stdc++.h>

using namespace std;

struct twoEdgeComponents {
    int n;
    vector<vector<int>> g;             // 入力のグラフ
    vector<int> cmp;                         // 頂点iが属する連結成分
    vector<vector<int>> each_bcc;  // 連結成分iに属する頂点
    vector<pair<int,int>> bridge; // 橋の辺を列挙
    vector<int> order;                       // 頂点iを訪れた順番
    vector<bool> inS;                            // 頂点iがSに存在している
    stack<int> roots, S;                 // 根の候補、訪れた頂点のうちまだ見ていない頂点

    twoEdgeComponents() {}
    twoEdgeComponents(vector<vector<int>> g_) : n(g_.size()), g(g_) {}
    // 辺(p,q)を追加
    void add_edge(int p, int q) {
        g[p].push_back(q);
        g[q].push_back(p);
    }
    // 橋、二重辺連結成分
    void dfs(int cur, int prev, int &k) {
        order[cur] = ++k;
        S.push(cur); inS[cur] = true;
        roots.push(cur);
        for(auto to: g[cur]) {
            if(order[to]==0) dfs(to, cur, k);
            else if(to!=prev && inS[to]) {
                while(order[roots.top()] > order[to]) roots.pop();
            }
        }
        if(cur == roots.top()) {
            if(prev!=-1) bridge.push_back({prev, cur});
            vector<int> bcc;
            while(1) {
                int node = S.top(); S.pop(); inS[node] = false;
                bcc.push_back(node);
                if(node==cur) break;
            }
            each_bcc.push_back(bcc);
            roots.pop();
        }
    }
    // 橋と二重辺連結成分
    void bcc() {
        order.assign(n, 0);
        inS.assign(n, false);
        cmp.assign(n, -1);
        int k = 0;
        for(int i=0; i<n; ++i) {
            if(order[i] == 0) {
                dfs(i, -1, k);
            }
        }
        for(int i=0; i<(int)each_bcc.size(); ++i) {
            for(auto j: each_bcc[i]) {
                cmp[j] = i;
            }
        }
    }
    // 二重編連結成分分解したあとのグラフ（木）を取得
    vector<vector<int>> getbcc() {
        vector<vector<int>> h(each_bcc.size(), vector<int>());
        for(auto i: bridge) {
            int a = cmp[i.first], b = cmp[i.second];
            h[a].push_back(b);
            h[b].push_back(a);
        }
        return h;
    }
};

int main() {
    int n, m;
    cin >> n >> m;
    vector<int> w(n);
    for(int i=0; i<n; ++i) cin >> w[i];
    vector<vector<int>> g(n);
    for(int i=0; i<m; ++i) {
        int a, b;
        cin >> a >> b;
        a--, b--;
        g[a].push_back(b);
        g[b].push_back(a);
    }

    twoEdgeComponents graph(g);
    graph.bcc();
    vector<vector<int>> tree = graph.getbcc();

    vector<int> W(graph.each_bcc.size());
    for(int i=0; i<(int)graph.each_bcc.size(); ++i) {
        for(int j=0; j<(int)graph.each_bcc[i].size(); ++j) {
            W[i] += w[graph.each_bcc[i][j]];
        }
    }

    vector<bool> v(n, false);
    function<bool(int,int)> dfs = [&](int x, int p) {
        bool ret = false;
        if(graph.each_bcc[x].size() >= 2) ret = true;
        for(auto i: tree[x]) {
            if(i == p) continue;
            ret |= dfs(i, x);
        }
        return v[x] = ret;
    };

    dfs(graph.cmp[0], -1);

    int ans = 0;
    for(int i=0; i<(int)graph.each_bcc.size(); ++i) {
        if(v[i]) ans += W[i];
    }

    int tmp = 0;
    vector<int> v2(n, 0);
    function<void(int,int,int)> dfs2 = [&](int x, int p, int cost) {
        if(!v[x]) cost += W[x];
        tmp = max(tmp, cost);
        for(auto i: tree[x]) {
            if(i == p) continue;
            dfs2(i, x, cost);
        }
    };
    dfs2(graph.cmp[0], -1, 0);

    ans += tmp;
    cout << ans << endl;

    return 0;
}

AOJ2784 Similarity of Subtrees

競技プログラミング AOJ

問題ページ
Similarity of Subtrees | Aizu Online Judge

考えたこと

  • 各頂点xを根とした部分木について配列v_xを考える
  • v_x[i]=(深さiの頂点数)とする
  • v_xが等しければその部分木は等しい
  • v_xが等しい頂点の数がa個であればa(a-1)/2個の条件を満たすペアがある
  • ある頂点yの子の配列をうまいことマージして配列v_xをつくれないか
  • マージはv_y[0]=0, v_y[i+1] = sum(v_yの子[i])になりそう
  • マージテク使えないかと思って考えるけど使える形に落ちそうにない
  • 数列v_xをハッシュ化すると簡単にならないか
  • ハッシュをローリングハッシュみたいに定義すると子のハッシュ値からハッシュが計算できそう
  • O(N)でハッシュが計算できそうなので等しいペアの数を計算すると通る

ハッシュが衝突しないかとか無駄に考えて時間を溶かした
Schwartz–Zippel lemmaで示せるらしい

ソースコード

#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 b = 1007, mo = 1e9+7;
VI g[100010];
map<int,int> v;
// 部分木xのハッシュを返す
int func(int x, int p) {
  int ret = b;
  for(int e: g[x]) {
    if(e == p) continue;
    (ret += func(e, x) * b % mo) %= mo;
  }
  v[ret]++;
  return ret;
}

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

  int n;
  cin >> n;
  REP(i, n-1) {
    int a, b;
    cin >> a >> b; a--, b--;
    g[a].PB(b);
    g[b].PB(a);
  }

  mo = 1e9+7;
  b = rand() % mo;
  v.clear();
  func(0, -1);

  int ret = 0;
  for(auto i: v) ret += i.second*(i.second-1)/2;
  cout << ret << endl;

  return 0;
}

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