JOI春合宿2012 Day3 - Algorithmer’s note

昨日よりましになった。リス（3完）

Fortune Telling

Segment Tree×平面走査やるだけ

#include <cstdio>
#include <algorithm>
#include <vector>

using namespace std;

typedef long long i64;
const int MAX = 100000;

struct seg_tree
{
  static const int DEPTH = 18;
  static const int SZ = 1<<DEPTH;
  i64 weight[SZ*2], stat[SZ*2]; int swap[SZ*2];

  seg_tree()
  {
    for(int i=0;i<2*SZ;i++){
      weight[i] = stat[i] = 0;
      swap[i] = 0;
    }
  }

  void init(int* v, int ln)
  {
    for(int i=0;i<ln;i++) weight[i+SZ] = v[i];
    for(int i=ln;i<SZ;i++) weight[i+SZ] = 0;
    for(int i=SZ-1;i>=1;i--) weight[i] = weight[i*2] + weight[i*2+1];
  }

  void flip(int pL, int pR, int qL, int qR, int depth)
  {
    //printf("%d %d %d %d %d\n", pL, pR, qL, qR, depth);
    if((pR<<depth)<=qL || qR<=(pL<<depth)) return;
    if(qL<=(pL<<depth) && (pR<<depth)<=qR){
      stat[pL] = weight[pL] - stat[pL];
      swap[pL] ^= 1;
      return;
    }
    
    if(swap[pL]){
      swap[pL] = 0;
      swap[pL*2] ^= 1; stat[pL*2] = weight[pL*2] - stat[pL*2];
      swap[pL*2+1] ^= 1; stat[pL*2+1] = weight[pL*2+1] - stat[pL*2+1];
    }
    flip(pL*2, pL+pR, qL, qR, depth-1);
    flip(pL+pR, pR*2, qL, qR, depth-1);
    stat[pL] = stat[pL*2] + stat[pL*2+1];
  }

  void flip(int qL, int qR)
  {
    flip(1, 2, qL+SZ, qR+SZ, DEPTH);
  }

  i64 sum()
  {
    return stat[1];
  }
};

struct action
{
  int pos, left, right;
  action(){ }
  action(int _l, int _r, int _p){ pos = _p; left = _l; right = _r; }
};

inline bool operator<(const action& A, const action& B)
{
  return A.pos < B.pos;
}

int M, N, K;
int x1[MAX], x2[MAX], y1[MAX], y2[MAX];
int xs[2*MAX], xln, dif[2*MAX];
seg_tree seg;
action act[2*MAX];

int main()
{
  scanf("%d%d%d", &M, &N, &K);
  for(int i=0;i<K;i++){
    scanf("%d%d%d%d", x1+i, x2+i, y1+i, y2+i);
    --x1[i]; --y1[i];
    xs[i*2] = x1[i];
    xs[i*2+1] = x2[i];
  }
  sort(xs, xs+2*K);
  xln = unique(xs, xs+2*K) - xs;
  for(int i=0;i<xln-1;i++) dif[i] = xs[i+1] - xs[i];
  seg.init(dif, xln-1);
  for(int i=0;i<K;i++){
    act[i*2] = action(lower_bound(xs, xs+xln, x1[i])-xs, lower_bound(xs, xs+xln, x2[i])-xs, y1[i]);
    act[i*2+1] = action(lower_bound(xs, xs+xln, x1[i])-xs, lower_bound(xs, xs+xln, x2[i])-xs, y2[i]);
  }
  sort(act, act+2*K);
  i64 ret = 0;
  for(int i=0;i<2*K;i++){
    if(i>0) ret += seg.sum() * (act[i].pos - act[i-1].pos);
    seg.flip(act[i].left, act[i].right);
    //printf("%lld\n", seg.sum());
  }

  printf("%lld\n", (i64)M*N - ret);

  return 0;
}

Kangaroo

適当に DP をやると通る

#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

typedef long long i64;
const i64 MOD = 1000000007;
const int MAX = 300;

#define ADD(X,Y) ( (X) = ( (X) + (Y) ) % MOD )

int N, A[MAX], B[MAX];

i64 dp[2][MAX+1][MAX+1];

int main()
{
  scanf("%d", &N);
  for(int i=0;i<N;i++) scanf("%d%d", A+i, B+i);
  sort(A, A+N); sort(B, B+N);
  reverse(A, A+N); reverse(B, B+N);

  int bp = 0, t = 0, cFree;
  for(int i=0;i<=N;i++)
    for(int j=0;j<=N;j++) dp[0][i][j] = dp[1][i][j] = 0;
  dp[t][0][0] = 1;

  for(int i=0;i<N;i++){
    while(bp<N && A[i]<B[bp]) bp++;
    for(int j=0;j<=N;j++)
      for(int k=0;k<=N;k++) dp[1-t][j][k] = 0;
    for(int j=0;j<=N;j++)
      for(int k=0;k<=N;k++){
	if(!dp[t][j][k]) continue;
	cFree = bp - j - k;

	//A: not connect
	ADD(dp[1-t][j][k+cFree], dp[t][j][k]);
	if(k>0) ADD(dp[1-t][j+1][k-1], dp[t][j][k] * k);
	ADD(dp[1-t][j+1][k], dp[t][j][k] * cFree);
      }
    t = 1-t;
  }

  i64 ret = 0;
  for(int i=0;i<=N;i++) ADD(ret, dp[t][i][0]);
  printf("%lld\n", ret);

  return 0;
}

Sokoban

関節点っぽいものを求めると解ける

#include <cstdio>
#include <queue>
#include <algorithm>

using namespace std;
typedef long long i64;
typedef pair<pair<int, int>, int> bfsdat;

const int MAX = 1010;

struct union_find
{
  int val[4];
  union_find(){ val[0]=val[1]=val[2]=val[3]=-1; }
  int root(int p){ return (val[p]<0)?p:(val[p]=root(val[p])); }
  void join(int p, int q)
  {
    p = root(p); q = root(q); if(p==q) return;
    val[p] += val[q]; val[q] = p;
  }
};

int M, N;
char in[MAX][MAX];
int ax[4]={-1,0,1,0},ay[4]={0,1,0,-1}; //up, right, down, left
bool vis[MAX][MAX];
int idx[MAX][MAX], iLast; int decl[MAX][MAX][4];
int wayGoing[MAX][MAX];
union_find con[MAX][MAX];
int weight[MAX][MAX][4];

int calc_size(int px, int py)
{
  int ret = (in[px][py]=='.') ? 1 : 0;
  vis[px][py] = true;
  for(int i=0;i<4;i++){
    if(in[px+ax[i]][py+ay[i]]=='#') continue;
    if(!vis[px+ax[i]][py+ay[i]]) ret += calc_size(px+ax[i], py+ay[i]);
  }

  return ret;
}

pair<int, int> dfs(int px, int py, int fw, int gsize)
{
  idx[px][py] = iLast++;
  int count=(in[px][py]=='.') ? 1 : 0, ef=0;

  for(int i=0;i<4;i++){
    if(i==fw) continue;
    if(in[px+ax[i]][py+ay[i]]=='#') continue;
    if(idx[px+ax[i]][py+ay[i]]!=-1){
      //ever visited
      if(idx[px+ax[i]][py+ay[i]] < idx[px][py]){
	//parent
	decl[px+ax[i]][py+ay[i]][wayGoing[px+ax[i]][py+ay[i]]]++;
	ef++;
	con[px][py].join(fw, i);
	con[px+ax[i]][py+ay[i]].join((i+2)%4, wayGoing[px+ax[i]][py+ay[i]]);
      }else{
	//child
	//join something;;;
      }
    }else{
      //not visited yet
      wayGoing[px][py] = i;
      pair<int, int> stat = dfs(px+ax[i], py+ay[i], (i+2)%4, gsize);
      count += stat.first;
      weight[px][py][i] = stat.first;

      int eTmp = stat.second - decl[px][py][i];
      if(eTmp) con[px][py].join(i, fw);
      ef += eTmp;
    }
  }
  weight[px][py][fw] = gsize - count;

  return make_pair(count, ef);
}

bool bfsVis[MAX][MAX][4];
int bx, by;

void bfs()
{
  queue<bfsdat> q;
  for(int i=0;i<4;i++){
    if(in[bx+ax[i]][by+ay[i]]=='.')
      q.push(make_pair(make_pair(bx, by), i));
  }

  int px, py, w;
  while(!q.empty()){
    bfsdat tmp = q.front(); q.pop();
    if(bfsVis[tmp.first.first][tmp.first.second][tmp.second]) continue;
    bfsVis[tmp.first.first][tmp.first.second][tmp.second] = true;

    //back
    px = tmp.first.first; py = tmp.first.second; w = tmp.second;
    if(in[px+ax[w]*2][py+ay[w]*2]!='#'){
      q.push(make_pair(make_pair(px+ax[w], py+ay[w]), w));
    }
    
    //move other side
    for(int i=0;i<4;i++){
      if(i != w && con[px][py].root(i) == con[px][py].root(w)){
	q.push(make_pair(make_pair(px, py), i));
      }
    }
  }

}

int main()
{
  scanf("%d%d", &M, &N);
  for(int i=1;i<=M;i++){
    scanf("%s", in[i]+1);
    in[i][0] = in[i][N+1] = '#';
    in[i][N+2] = '\0';
  }
  for(int i=0;i<=N+1;i++) in[0][i] = in[M+1][i] = '#';
  in[0][N+2] = in[M+1][N+2] = '\0';
  M += 2; N += 2;

  for(int i=0;i<M;i++)
    for(int j=0;j<N;j++){
      vis[i][j] = false; idx[i][j] = -1;
      for(int k=0;k<4;k++){
	weight[i][j][k] = 0;
	bfsVis[i][j][k] = false;
	decl[i][j][k] = 0;
      }
      if(in[i][j]=='X'){
	bx = i; by = j;
      }
    }

  iLast = 0;
  for(int i=1;i<M-1;i++)
    for(int j=1;j<N-1;j++) if(in[i][j]!='#' && idx[i][j]==-1){
	int sz = calc_size(i, j);
	dfs(i, j, -1, sz);
      }
  
  bfs();

  i64 ret = 0;
  for(int i=1;i<M-1;i++){
    for(int j=1;j<N-1;j++){
      if(in[i][j]=='.'){
	for(int k=0;k<4;k++){
	  if(bfsVis[i][j][k]) ret += weight[i][j][k];
	}
      }
    }
  }

  printf("%lld\n", ret);

  return 0;
}