AGC 006: B Median Pyramid Easy

問題

B: Median Pyramid Easy - AtCoder Grand Contest 006 | AtCoder

i段目に2 * i - 1個のブロックがあり、ピラミッド型に積まれている。 ブロックには数字がかかれていて、あるブロックの数字はその左下と真下と右下のブロックに書かれた数字の中央値である。 ブロックの段数と、最上段のブロックに書かれた値が入力として与えられる。このとき、最下段が1〜Nの順列となるような場合は存在するか。存在するならば、1行目に"Yes"と出力し、2行目以降は条件を満たす順列を1つ出力せよ。そのような順列がひとつも存在しない場合は"No"と一行に出力せよ。

  • 2\le N\le 10^5
  • 1\le x\le 2\times N−1
続きを読む

LiveArchive 5874 Social Holidaying

問題

一般グラフにおいて辺数最大マッチングのサイズを求めよ。

解法

蟻本P198や組合せ最適化P271 系10.9 に載っているTutte行列を用いて最大マッチングを求めるLovaszのランダム化アルゴリズムを使う。 別の解法としては、Edmondsの辺数最大マッチングアルゴリズム(Cardinality Matching Algorithm)を投げるものがある。

Lovaszのランダム化アルゴリズムは、以下の定理に基づく。

定理(Tutte[1947])

Gが完全マッチングを持つための必要十分条件は、detT_G(x)が恒等的に零ではないことである。

Tutte行列は変数xを要素としている。行列の行列式は計算が難しいが、この変数に一様な乱数を与えることで、十分な確率で最大マッチングの頂点数が求まる。

具体的には、N \times Nの正方行列に対して辺が張られている要素に歪対称(M = -M^T)に[0,\ 1]の範囲で一様な乱数を設定し、他の要素の値は0として行列のランクを求めると、辺数最大マッチングのサイズの2倍(最大マッチングの頂点数)となる。よって、これを2で割った値が答えとなる。

一様な乱数なので、srand(), rand()を使わずにrandom_device, mt19937, uniform_real_distributionを使った方がいい感じにACした。行列のランクを求めるコードは他の人のコードを参考にした。

ところで、Tutte行列なので歪対称にする必要があると思うのだが、そうした場合はそこそこWAになる。歪対称にせずにT_{v,w}とT_{w,v}を別々のランダムな値にすると常にACする。テストケースがおかしいのか自分が勘違いしているのかがわからない。

また、組合せ最適化P271によると、乱数として[0,\ 1]の範囲の実数ではなく十分大きなNを選んで有限集合\{1,2,...,N\}からランダムに整数を選んできても良いはずなのだが、よくわからない理由（行列計算のオーバーフローなどだろうか？）でしばしばWAになったので、実数乱数を用いた。

namespace flow {

class maximum_matching {
private:
  using number = double;
  using vec = vector<number>;
  using mat = vector<vec>;

  double const EPS = 1e-8;

  random_device seed_gen;
  mt19937_64 mt;
  uniform_real_distribution<number> dist;
  mat A;

  int mrank(){
    const int N = A.size();
    int rank = 0;
    mat B(N, vec(N+1, 1));
    for(int i=0; i<N; i++)
      for(int j=0; j<N; j++)
        B[i][j] = A[i][j];

    for(int i=0; i<N; i++) {
      int pivot = i;
      for(int j=i; j<N; j++) {
        if(abs(B[j][i]) > abs(B[pivot][i])) pivot = j;
      }

      swap(B[i], B[pivot]);

      if(abs(B[i][i]) < EPS) continue;

      for(int j=i+1; j<N+1; j++)
        B[i][j] /= B[i][i];

      for(int j=0; j<N; j++) if(i != j)
        for(int k=i+1; k<N+1; k++)
          B[j][k] -= B[j][i] * B[i][k];

      rank ++;
    }
    return rank;
  }

public:

  maximum_matching(int V) : mt(seed_gen()), dist(0, 1) {
    A.resize(V);
    for(int i=0; i<V; i++)
      A[i].resize(V);
  }

  void add_edge(int u, int v) {
    A[u][v] = dist(mt);
    A[v][u] = dist(mt);
  }

  int maximum_matching_number() {
    return mrank() / 2;
  }
};
}

int main() {

  int Tc; cin >> Tc;
  while(Tc--) {
    int N, M; cin >> N >> M;

    vector<int> A(N);
    for(int i=0; i<N; i++) cin >> A[i];

    set<int> able;
    for(int i=0; i<M; i++) {
      int x; cin >> x;
      able.insert(x);
    }

    flow::maximum_matching mm(N);

    for(int i=0; i<N; i++)
      for(int j=i+1; j<N; j++) {
        if(i == j) continue;
        if(able.count(A[i] + A[j]))
          mm.add_edge(i, j);
      }

    cout << mm.maximum_matching_number() << endl;
  }

  return 0;
}

LiveArchive 5875 Orienteering

問題

巡回コースの通過点のリストが与えられる。N個の通過点とM人のプレイヤーがいる。各通過点は(x_i,\ y_i)座標に存在し、得られる得点がs_iである。各プレイヤーは名前name_iと移動できる最大距離d_iを持つ。各プレイヤーは原点から移動を始め、入力の通過点のうち幾つかの通過点の集合を選び、それを入力の順に訪れて、最後に原点に戻る。プレイヤーの移動は直線的で最短経路を辿る。プレイヤーの入力の順に、プレイヤー名と得られる最大得点を出力せよ。

続きを読む

AOJ2397 Three-way Branch

問題

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2397

縦に長いグリッドが与えられる。(0, 0)の位置から(W-1, H-1)の位置に移動したい。移動の方法は、左下に、真下、右下のいずれかである。途中、N個の障害物が有り、その場所は移動できない。移動の方法は何通りあるか。mod\ 10^9+9で出力せよ。

  • 1\le W\le 75
  • 2\le H\le 10^{18}
  • 0\le N\le 30
続きを読む

CODE FESTIVAL 2016 qual C - C: 二人のアルピニスト

問題

山脈の高さの列が与えられる。山を登るときは高さの最大値を記録して登る。左から登った人と右から登った人の記録が与えられる。このとき、本当の高さの列としてありうるパターン数をmod 10^9+7で求めよ。記録に矛盾がある場合もあるので、そのときは0と出力せよ。

  • 1\le N\le 10^5
  • 1\le T_i\le 10^9
  • 1\le A_i\le 10^9
  • T_i\le T_{i+1}(1\le i\le N−1)
  • A_i\ge A_{i+1}(1\le i\le N−1)
続きを読む

CODE FESTIVAL 2016 qual C - B: K個のケーキ

問題

K個のケーキがT種類ある。各種類a_i個ずつ存在する。毎日1個ずつ食べるとして、全てのケーキを食べ終えたとき、前日と同じケーキを食べる回数の最小値を出力せよ。

  • 1\le K\le 10000,\ 1\le T\le 100
  • 1\le a_i\le 100
  • a_1\ +\ a_2\ +\ ...\ +\ a_T\ =\ K
続きを読む

CODE FESTIVAL 2016 qual C - D: Friction

問題

D: Friction - CODE FESTIVAL 2016 qual C | AtCoder

H\times Wのブロックがある。各ブロックは赤、緑、青のいずれかである。1度の操作で、一番下の行あるブロックのうち1つを消すことができる。消すときにかかるコストは、消した列の各ブロックの横に隣り合うブロックのうち色が同じ物の数のぶんだけかかる。全てのブロックを消すためのコストを最小化せよ。部分点はW=3の場合である。

  • 1\le H\le 300
  • 2\le W\le 300
続きを読む