ferinの競プロ帳

競プロについてのメモ

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

AOJ2585 一日乗車券

競技プログラミング AOJ

問題ページ 1 Day Passport | Aizu Online Judge

考えたこと

  • とりあえず入力で何がくるのかちゃんと読む
  • 会社の数の制約が小さい
  • dp[S] = (会社の集合Sを乗り放題にするために必要な最小コスト) を求めておく
  • これは簡単なbitDPでできてO(2^KP)
  • 会社の集合Sが乗り放題のときに s->t に行くかかる時間がh以下の最小のコストを求めたい
  • d[i][j] = (頂点iまでに時間jかかったときの最小コスト) として拡張dijkstra
  • 全ての集合Sに対して拡張dijkstraをするのでO(2^KMlogNH) になる
  • 計算量が問題なさそうなので出すと通った

典型詰め合わせセットみたいな問題

ソースコード

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

struct edge { int to, cost, time, com; };

vector<edge> g[105];
int dp[1<<8], ticket[1<<8], fee[1<<8];
int d[105][30];
signed main(void)
{
  cin.tie(0);
  ios::sync_with_stdio(false);

  while(true) {
    int n, m, h, k;
    cin >> n >> m >> h >> k;
    if(!n) break;
    REP(i, 1<<k) dp[i] = ticket[i] = fee[i] = 0;
    REP(i, n) g[i].clear();
    REP(i, m) {
      int a, b, c, h, r;
      cin >> a >> b >> c >> h >> r;
      a--, b--;
      g[a].PB({b, c, h, r-1});
      g[b].PB({a, c, h, r-1});
    }
    int s, t;
    cin >> s >> t; s--, t--;
    int p;
    cin >> p;
    REP(i, p) {
      int l;
      cin >> l >> fee[i];
      REP(j, l) {
        int com;
        cin >> com; com--;
        ticket[i] |= 1<<com;
      }
    }

    REP(i, 1<<k) dp[i] = INF;
    dp[0] = 0;
    REP(i, 1<<k) REP(j, p) chmin(dp[i | ticket[j]], dp[i] + fee[j]);

    int ans = INF;
    REP(i, 1<<k) {
      // iの会社はただで使えるとする
      int ret = dp[i];

      REP(j, 105) REP(l, 30) d[j][l] = INF;
      d[s][0] = 0;
      priority_queue<VI, VVI, greater<VI>> que;
      que.push({d[s][0], s, 0});

      while(que.size()) {
        VI v = que.top(); que.pop();
        if(v[1] == t) break;
        for(edge e: g[v[1]]) {
          int n_cost = d[v[1]][v[2]] + (i & 1 << e.com ? 0 : e.cost);
          if(v[2] + e.time <= h && d[e.to][v[2]+e.time] > n_cost) {
            d[e.to][v[2]+e.time] = n_cost;
            que.push({d[e.to][v[2]+e.time], e.to, v[2]+e.time});
          }
        }
      }

      int mi = INF;
      REP(j, h+1) chmin(mi, d[t][j]);
      chmin(ans, ret+mi);
    }

    if(ans == INF) cout << -1 << endl;
    else cout << ans << endl;
  }

  return 0;
}

yukicoder No.685 Logical Operations

競技プログラミング yukicoder

問題ページ
No.685 Logical Operations - yukicoder

考えたこと

  • bitだし2進数で考える
  • x AND y, x XOR y, x OR y を書いてみる
X 01001
Y 11101

& 01001
^ 10100
| 11101
  • x,yのi桁目を(x_i,y_i)と表す
  • AND < XOR を満たすためには1が出てくる最初の桁が(0,1)であることが必要
  • XOR < OR を満たすためにはどこかに(1,1)が必要
  • N <= 10^18 で条件を満たす数の数え上げ→大体桁DP
  • dp[i桁目][j(N未満が確定しているか)][(1,1)の存在][(0,1)が先頭にあるか] のDP
  • (0,1)の先頭はまだ1がでていなければ0、(0,1)が先頭なら1、それ以外が先頭なら2とする
  • dp[i][j][k][l] からの遷移について考える
  • (0,0)(0,1)(1,0)(1,1) の4通りが遷移としてある
  • (0,0) であれば dp[i+1][j || 0<(nのi桁目)][k][l]
  • (1,0) では x <= y の条件から (0,1) が前の桁で出ていることが必要で dp[i+1][j || 0<(nのi桁目)][k][l] となる
  • (0,1) では y <= n の条件からyのi桁目を1にできることが必要で dp[i+1][j][k][l==0?1:l]
  • (1,1) でも y <= n の条件からyのi桁目を1にできることが必要で dp[i+1][j][1][l==0?2:l]
  • 遷移が全て書けたのでこれにしたがって桁DPを書く

ソースコード

#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[65][2][2][3];
signed main(void)
{
  cin.tie(0);
  ios::sync_with_stdio(false);

  int n;
  cin >> n;

  // nを2進数にしたときの桁数
  int m = 0, n_ = n;
  while(n_ > 0) {
    m++;
    n_ /= 2;
  }

  dp[0][0][0][0] = 1;
  REP(i, m) REP(j, 2) REP(k, 2) REP(l, 2) {
    if(dp[i][j][k][l] == 0) continue;
    int lim = j?1:(n>>(m-i-1)&1);
    // (0,0)
    (dp[i+1][j || 0<lim][k][l] += dp[i][j][k][l]) %= MOD;
    // (1,0)
    if(l == 1) (dp[i+1][j || 0<lim][k][l] += dp[i][j][k][l]) %= MOD;
    if(lim == 1) {
      // (0,1)
      int cond = l==0?1:l;
      (dp[i+1][j][k][cond] += dp[i][j][k][l]) %= MOD;
      // (1,1)
      cond = l==0?2:l;
      (dp[i+1][j][1][cond] += dp[i][j][k][l]) %= MOD;
    }
  }

  int ans = 0;
  REP(i, 2) (ans += dp[m][i][1][1]) %= MOD;
  cout << ans << endl;

  return 0;
}

AOJ1330 Never Wait for Weights

競技プログラミング AOJ

問題ページ
Never Wait for Weights | Aizu Online Judge

考えたこと

  • bがaよりwグラム重いことを頂点bから頂点aへ重みがwの辺を張ることで表す
  • すると重さの差の質問クエリがある頂点からある頂点までの距離を求めるクエリに帰着できる
  • 重さの差を測るクエリは辺を張ることで表す
  • 質問クエリでその時点で2頂点が連結なら距離は絶対にわかる
  • 逆に非連結なら"UNKNOWN"になる
  • 余計に辺が張ってあったとしても関係ないのでクエリ先読みして辺を張っておいてよい
  • 問題設定からすでに連結している2頂点間で辺を張るようなクエリは無視できる
  • 無視できるクエリについて辺を張らないとするとグラフは森になる
  • 森で2点間の距離を高速に求めるクエリ→LCAでよさそう
  • 辺の重みの正負がその辺と逆辺で反対になるのに注意しつつ考える
  • いつものLCAみたいに考えると d[u] + d[v] - d[lca]*2 だけど上の通りこれはおかしい
  • vの方は正負が反転して (d[u] - d[lca]) - (d[v] - d[lca]) となる
  • lcaの部分が消えてd[u]-d[v]となる
  • つまり実はLCAが要らなくてdfsで根からの距離を求めればいいだけ

考察するとdfsするだけになって面白い

ソースコード

#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 ll LLINF = (1LL<<60);

class UnionFind {
public:
  const static int MAX_N = 100010;
  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;

vector<PII> g[100010];
int d[100010];
void dfs(int x, int p, int dist) {
  d[x] = dist;
  for(auto e: g[x]) {
    if(e.first != p) dfs(e.first, x, dist + e.second);
  }
}

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

  while(true) {
    int n, m;
    cin >> n >> m;
    if(!n) break;

    REP(i, n) g[i].clear();
    memset(d, 0, sizeof(d));
    uf.init(n);

    vector<PII> query;
    VI ans(m+5);
    int idx = 0;
    REP(i, m) {
      char c;
      int a, b;
      cin >> c >> a >> b; a--, b--;
      if(c == '!') {
        int w; cin >> w;
        if(!uf.same(a, b)) {
          uf.unite(a, b);
          g[a].PB({b, -w});
          g[b].PB({a, w});
        }
      } else {
        query.PB({a, b});
        if(!uf.same(a, b)) ans[idx] = LLINF;
        idx++;
      }
    }

    REP(i, n) if(d[i] == 0) dfs(i, -1, 0);

    REP(i, query.size()){
      if(ans[i]==LLINF) cout << "UNKNOWN" << endl;
      else cout << d[query[i].first] - d[query[i].second] << endl;
    }
  }

  return 0;
}

AOJ2200 Mr. Rito Post Office

競技プログラミング AOJ

問題ページ
Mr. Rito Post Office | Aizu Online Judge

考えたこと

  • 人がx、船がyにある状態を(x,y)と書くことにする
  • ある頂点aにいるとき考えられる状態は (a,1)(a,2)(a,3)…(a,n) のN通り
  • 頂点aから頂点bに移動するとき(a,1)→(b,1)(b,2)…(b,n)、(a,2)→(b,1)(b,2)…(b,n) … のN^2通りの移動方法がある
  • (a,x) → (b,y) への移動にかかる最短距離がO(1)でわかればO(N^2R)で解ける
  • 3*10^7くらいでそれっぽい計算量
  • 前計算で最短距離を求められるようにしておきたい
  • d[i][j] = ((i,j)に到達するまでの最短距離) として拡張dijkstraをするとできそう
  • 計算量について考えると始点がO(N^2)でdijkstraがO(MlogN)あるので全体でO(N^2MlogN)
  • これはTLEしそう
  • 陸と海で別々に考えられないか？
  • (a,x) → (b,y) へ移動するときに海を使うとする
  • そのときは 陸でaから船があるxまで行く→海でyまで行く→陸でyからbまで行くと移動するのが最適
  • x=yであれば海を使わないことも可能でそれならば陸でaからbまで行く
  • 陸と海の道でそれぞれ最短経路を求めることができれば(a,x) → (b,y) の最短距離がわかる
  • これはワーシャルフロイドを用いてO(N^3)で解ける
  • したがって全体で O(N^3+N^2R) で解ける

ソースコード

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
#define int ll
using VI = vector<int>;

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

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 d1[205][205], d2[205][205];
signed main(void)
{
  cin.tie(0);
  ios::sync_with_stdio(false);

  to_string(123);

  while(true) {
    int n, m;
    cin >> n >> m;
    if(!n) break;
    REP(i, n) REP(j, n) {
      d1[i][j] = i==j?0:INF;
      d2[i][j] = i==j?0:INF;
    }
    REP(i, m) {
      int x, y, c;
      char t;
      cin >> x >> y >> c >> t;
      x--, y--;
      if(t == 'L') {
        chmin(d1[x][y], c);
        chmin(d1[y][x], c);
      } else {
        chmin(d2[x][y], c);
        chmin(d2[y][x], c);
      }
    }

    REP(k, n) REP(i, n) REP(j, n) {
      chmin(d1[i][j], d1[i][k] + d1[k][j]);
      chmin(d2[i][j], d2[i][k] + d2[k][j]);
    }

    int r;
    cin >> r;
    VI cur(n, INF), nxt(n, INF);
    int now;
    cin >> now; now--;
    REP(i, n) cur[i] = i==now?0:INF;
    REP(i, r-1) {
      int g;
      cin >> g; g--;

      REP(j, n) {
        // (now, j) からスタートする
        REP(k, n) {
          // (g, k) を目的とする
          // 陸でnow->j 船でj->k 陸でk->g
          int tmp = d1[now][j] + d2[j][k] + d1[k][g];
          // 陸だけで移動
          if(j == k) chmin(tmp, d1[now][g]);
          chmin(nxt[k], cur[j] + tmp);
        }
      }

      cur = nxt;
      nxt.assign(n, INF);
      now = g;
    }

    int ret = INF;
    REP(i, n) chmin(ret, cur[i]);
    cout << ret << endl;
  }

  return 0;
}

GCJ 2018 round1 C - A Whole New Word

競技プログラミング

問題ページ Google Code Jam

考えたこと

  • 全ての可能な単語パターンは何通りか
  • i文字目の文字種をc[i]とするとc[i]の総積になる
  • nがこれに等しければ何をつくっても一致するので不可能
  • とりあえず適当にケースをつくってみる
  • j文字目が全て同じ文字→j文字目を異なるものにできない
  • j文字目に異なる文字が含まれるのが1列だけ→新たな単語をつくることはできない
ABC
ABD
ABE
  • 何か実験してると1文字交換して不可能で2文字交換するとできるみたいなパターンがなさそう
  • 1文字置換ならば全探索してもO(N^2LlogN)くらいになりそう
  • 全ケース最悪なパターンが来るとちょっと怪しい気持ちになる
  • 答えが見つかったタイミングで終了してるから最悪になるケースはそんななさそう
  • 単語iに単語jの文字を移したとしても新たな単語が作れないときを考えるとAAAA,AAAB,AAAC,AAAD,…,AAAZみたいな感じでそんなに個数がなさそう
  • 何とかなりそうなので出すと通った

ソースコード

#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)

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

  int testcase;
  cin >> testcase;
  REP(tes, testcase) {
    int h, w;
    cin >> h >> w;
    vector<string> s(h);
    REP(i, h) cin >> s[i];

    set<string> st;
    REP(i, h) st.insert(s[i]);

    string ans = "-";
    REP(i, h) REP(j, h) {
      if(i == j) continue;
      REP(k, w) {
        if(s[i][k] != s[j][k]) {
          string tmp = s[i];
          tmp[k] = s[j][k];
          if(st.find(tmp) == st.end()) {
            ans = tmp;
            goto end;
          }
        }
      }
    }

    end:;
    cout << "Case #" << tes+1 << ": " << ans << endl;
  }

  return 0;
}