PKU 3182 The Grove

問題

グリッド上に連結した池がある。これをぐるっと回って戻ってくるための最短経路を求めよ。ただし8連結方向に移動できる。

やりかた

通ったけど多分嘘解法。

凸包。まず池の周りを4連結で囲むように印をつける。その印にたいして凸包を計算して池を一周するための最短経路数を求める。
続いて凸包で囲まれる円周の一辺を取り除いて始点を迂回するルートにした場合の経路長を計算する（下図の点線ルート、もしくは波線ルート）。この取り除く辺を円周の全ての辺に対して試してみて、最小値を計算する。

正しくないような気がしたが、これで通った。

以下ソース。

const int NUM = 100;
int dy[] = {1, 0, -1, 0, 1, -1, -1, 1};
int dx[] = {0, 1, 0, -1, 1, 1, -1, -1};
int H, W;
int d[NUM][NUM];
char f[NUM][NUM];

int bfs(int sy, int sx, int gy, int gx){
  FILL(d, -1);
  d[sy][sx] = 0;
  queue<int> Q;
  Q.push(sy * W + sx);
  while(!Q.empty()){
    int y = Q.front() / W, x = Q.front() % W;
    Q.pop();
    if(gy == y && gx == x) return d[y][x];
    for(int k = 0; k < 8; k++){
      int ny = y + dy[k], nx = x + dx[k];
      if(0 <= ny && ny < H && 0 <= nx && nx < W &&
	 d[ny][nx] == -1 && f[ny][nx] == '.'){
	d[ny][nx] = d[y][x] + 1;
	Q.push(ny * W + nx);
      }
    }
  }
}


int add(int a, int b){
  if(abs(a + b) < EPS * (abs(a) + abs(b))) return 0;
  return a + b;
}

struct P{
  int x, y;
  P() {}
  P(int x, int y) : x(x), y(y) {}
  P operator + (P p){
    return P(add(x, p.x), add(y, p.y));
  }
  P operator - (P p){
    return P(add(x, -p.x), add(y, -p.y));
  }
  P operator * (int d){
    return P(x * d, y * d);
  }
  int dot(P p){
    return add(x * p.x, y * p.y);
  }
  int det(P p){
    return add(x * p.y, -y * p.x);
  }
};

bool cmp_x(P a, P b){
  if(a.x != b.x) return a.x < b.x;
  return a.y < b.y;
}

vector<P> convex_hull(vector<P> &p){
  int N = p.size();
  sort(p.begin(), p.end(), cmp_x);
  int k = 0;
  vector<P> ret(N * 2);
  for(int i = 0; i < N; i++){
    while(k > 1 && (ret[k - 1] - ret[k - 2]).det(p[i] - ret[k - 1]) <= 0) k--;
    ret[k++] = p[i];
  }
  for(int i = N - 2, t = k; i >= 0; i--){
    while(k > t && (ret[k - 1] - ret[k - 2]).det(p[i] - ret[k - 1]) <= 0) k--;
    ret[k++] = p[i];
  }
  ret.resize(k - 1);
  return ret;
}

int main(int argc, char **argv){
  vector<P> p;
  cin >> H >> W;
  int sy, sx;
  for(int i = 0; i < H; i++){
    for(int j = 0; j < W; j++){
      cin >> f[i][j];
      if(f[i][j] == '*')
	sy = i, sx = j;
    }
  }
  for(int i = 0; i < H; i++){
    for(int j = 0; j < W; j++){
      for(int k = 0; k < 4; k++){
	int ny = i + dy[k], nx = j + dx[k];
	if(0 <= ny && ny < H && 0 <= nx && nx < W &&
	   f[ny][nx] == 'X'){
	  P tmp;
	  tmp.y = i, tmp.x = j;
	  p.push_back(tmp);
	  break;
	}
      }
    }
  }

  bfs(sy, sx, -1, -1);
  
  vector<P> ch = convex_hull(p);
  int M = ch.size();

  int round = 0;
  for(int i = 0; i < M; i++){
    f[ch[i].y][ch[i].x] = '@';
    round += max(abs(ch[i].y - ch[(i + 1) % M].y),
		 abs(ch[i].x - ch[(i + 1) % M].x));
  }

  int ans = INF;
  for(int i = 0; i < M; i++){
    int l = max(abs(ch[i].y - ch[(i + 1) % M].y),
		abs(ch[i].x - ch[(i + 1) % M].x));
    int hige = d[ch[i].y][ch[i].x]
      + d[ch[(i + 1) % M].y][ch[(i + 1) % M].x];
    ans = min(ans, round - l + hige);
  }
  cout << ans << endl;
  return 0;
}

アップした図はiPad pro+Applepenで書いてみたもの。これは便利！

POJ 1387 Labyrinth

問題

やりかた

木の直径を求める問題。グラフ上の適当な点からはじめて最も遠い点を見つける。続いてその点から最も遠い点を探すとその間が直径になる。
メモリ量、制限時間ともにシビア。グラフは隣接リストで持たずに、ある頂点に対する４方向の連結情報をビット状態で持つようにして、一つの頂点の情報をcharで表現してメモリを減らした。

以下ソース。

int R, C;
char f[1001][1001];
int dy[] = {1, 0, -1, 0};
int dx[] = {0, 1, 0, -1};

char G[1000001];
int d[1000001];

void bfs(int idx){
  memset(d, -1, sizeof(d));

  queue<int> Q;
  Q.push(idx);
  d[idx] = 0;
  while(!Q.empty()){
    int x = Q.front(); Q.pop();
    for(int k = 0; k < 4; k++){
      if(G[x] >> k & 1){
	int v = x + dy[k] * C + dx[k];
	if(d[v] == -1){
	  Q.push(v);
	  d[v] = d[x] + 1;
	}
      }
    }
  }

  return;
}

int main(){
  int T;
  scanf("%d", &T);
  while(T--){
    scanf("%d %d", &C, &R);
    for(int i = 0; i < R; i++){
      for(int j = 0; j < C; j++){
	f[i][j] = getchar();
      }
      getchar();
    }
    memset(G, 0, sizeof(G));
    
    int start;
    for(int i = 0; i < R; i++){
      for(int j = 0; j < C; j++){
	if(f[i][j] == '.'){
	  start = i * C + j;
	  for(int k = 0; k < 4; k++){
	    int ny = i + dy[k], nx = j + dx[k];
	    if(0 <= ny && ny < R
	       && 0 <= nx && nx < C && f[ny][nx] == '.'){
	      G[i * C + j] |= 1 << k;
	    }
	  }
	}
      }
    }

    //木の直径
    bfs(start);
    int fur = max_element(d, d + R * C) - d;
    bfs(fur);
    int ans = *max_element(d, d + R * C);
    printf("Maximum rope length is %d.\n", ans);
  }
  return 0;
}

POJ 1376 Robot

問題

グリッド上の格子点を直径1.6mの円形のロボットがスタート地点からゴール地点まで移動する。グリッドの一部に障害物があり、ロボットを障害物にぶつけてはいけない。ロボットは一回の移動で左右に向きを変えるか、1~3つ分の格子点を直進することができる。ゴール地点に行くための最短の移動回数を求めよ。

やりかた

グリッド上の位置、向きを状態にもつ幅優先。
以下ソース。

int H, W;
int sy, sx, gy, gx;
string dir;
bool f[60][60];
int d[60][60][4];
int dy[] = {-1, 0, 1, 0};
int dx[] = {0, 1, 0, -1};

bool in(int y, int x){
  if(0 < y && y < H && 0 < x && x < W){
    if(!f[y][x] && !f[y - 1][x - 1] &&
       !f[y - 1][x] && !f[y][x - 1]){
      return true;
    }
  }
  return false;
}

int main(){
  while(cin >> H >> W, H){
    for(int i = 0; i < H * W; i++){
      int v; cin >> v;
      f[i / W][i % W] = v == 1;
    }
    cin >> sy >> sx >> gy >> gx >> dir;

    FILL(d, INF);
    int c;
    if(dir == "north") c = 0;
    if(dir == "east") c = 1;
    if(dir == "south") c = 2;
    if(dir == "west") c = 3;
    queue<pair<int, int> > Q;
    Q.push(make_pair(sy * W + sx, c));
    d[sy][sx][c] = 0;
    while(!Q.empty()){
      int y = Q.front().first / W,
	x = Q.front().first % W,
	c = Q.front().second;
      Q.pop();

      if(y == gy && x == gx) break;
      
      for(int k = 1; k <= 3; k++){
	int ny = y + k * dy[c], nx = x + k * dx[c];
	if(in(ny, nx)){
	  if(d[ny][nx][c] == INF){
	    Q.push(make_pair(ny * W + nx, c));
	    d[ny][nx][c] = d[y][x][c] + 1;
	  }
	}else break;
      }
      if(d[y][x][(c + 1) % 4] == INF){
	Q.push(make_pair(y * W + x, (c + 1) % 4));
	d[y][x][(c + 1) % 4] = d[y][x][c] + 1;
      }
      if(d[y][x][(c + 3) % 4] == INF){
	Q.push(make_pair(y * W + x, (c + 3) % 4));
	d[y][x][(c + 3) % 4] = d[y][x][c] + 1;
      }      
    }

    int ans = INF;
    for(int s = 0; s < 4; s++)
      ans = min(ans, d[gy][gx][s]);
    cout << (ans >= INF ? -1 : ans) << endl;
  }
  return 0;
}

POJ 2341 Spell Checker

問題

アルファベットと.,;:-!?とスペースからなる文章が与えられる．文の区切りは.か!か?である．文章中の不整合な箇所の個数を答えよ．
ただし不整合なケースとは以下の2種類を指す．

1. 文頭が大文字でない
2. 単語の途中に大文字がある

やりかた

文意を正確に汲み取る必要がある．
注意するのは以下のケース．

1. 文頭が記号である場合はその次の文字を文頭として見る
2. 単語中に記号がある場合は単語の区切りとみなす
3. 改行は単語の区切りとみなす

以下ソース．

int main(){
  char c;
  bool s_start = true, w_start = true;
  int cnt = 0;

  while((c = getchar()) != -1){
    if(c == '\n'){
      w_start = true;
    }
    else if(c == '.' || c == '?' || c == '!'){
      s_start = w_start = true;
    }
    else if(c == ' ' || c == ':' || c == ',' || c == '-'){
      w_start = true;
    }
    else{
      if(s_start && w_start){

	if(!isalpha(c)) continue;
	if(islower(c)) cnt++;
	
	s_start = w_start = false;
	
      }else if(!s_start && w_start){

	s_start = w_start = false;
	
      }else if(!s_start && !w_start){

	if(isupper(c)) cnt++;
	
      }
    }
  }
  cout << cnt << endl;
  return 0;
}

POJ 2782 Bin Packing

問題

アイテムがN個あり、それぞれの重さが与えられる。これらのアイテムをビンに詰めたいとする。一つのビンにたいして最大で2個までのアイテムを詰められる。このとき必要な最小のビンの数を求めよ。ただし一つのビンに詰めるアイテムの重さの和がLより大きくなってはいけない。

やりかた

ビンパッキング問題なので普通なら効率的にはできないが、ビンに入れられるアイテム数がせいぜい2なので貪欲で解ける。最小の重みのアイテムと、合わせてビンに詰めることができる最大の重みを持つアイテムを見つけてこれら2つを消去し、ビン1つにカウントする。合わせて詰められるアイテムが見つからない場合は単独で消去し、ビン1つにカウントする。これをアイテムがなくなるまで繰り返せばいい。アイテムはmultisetで管理し、条件に合う最大重みのアイテムを見つける処理はlower_boundで二分探索する。

以下ソース。

#include <sstream>
#include <string>
#include <vector>
#include <set>
#include <algorithm>
#include <iostream>
#include <cstdio>
#define ALL(c) (c).begin(), (c).end()

using namespace std;

int main(){
  int N, L;
  scanf("%d %d", &N, &L);

  multiset<int> x;
  for(int i = 0; i < N; i++){
    int a;
    scanf("%d", &a);
    x.insert(a);
  }

  int ans = 0;
  while(!x.empty()){
    int b = L - *x.begin();//計算上詰められる最大重み
    multiset<int>::iterator it = x.begin();
    it =  x.upper_bound(b);
    if(it != x.begin()) it--;
    
    if(it != x.begin()) x.erase(it); //抱き合わせできるものが見つかった場合は消す
    x.erase(x.begin());//今見ているアイテムを消す
    ans++;
  }

  printf("%d\n", ans);
  return 0;
}

POJ 3862 Business Center

問題

エレベータがm台あり、各エレベータには昇降用のボタンが2つだけついている。エレベータiの上昇ボタンを押すとu[i]階上がり、下降ボタンを押すとd[i]階下がる。階数は無限にあるが、0階より下の階はない。m台のエレベータのうちのいずれか一台のエレベータを選んで、n回昇降ボタンを押した上で到達することができるもっとも低層の階（ただし1階以上）を求めよ。

やりかた

上昇ボタンをx回、下降ボタンをn-x回押してp階にたどり着けるとするととなる。xについて解くと xは整数であるから分子は分母で割り切れる必要があり、これを満たすようなpは になる。すべてのエレベータでpを計算して最小値を求めればいい。

以下ソース。

int main(){
  int n, m, u, d;
  scanf("%d %d", &n, &m);

  int ans = INF;
  for(int i = 0; i < m; i++){
    scanf("%d %d", &u, &d);
    ans = min(ans, u + d - (d * n) % (u + d));
  }
  printf("%d\n", ans);
  return 0;
}

POJ 2342 Anniversary party

問題

N人のうちから何人かパーティに招待したい。N人には上司部下の関係が存在し、これらは一つの木構造をなしている。（つまり、ある一人にたいして上司はせいぜい一人しかおらず、上司のいない人間はただ一人である）
パーティには部下とその直属の上司が同時に出席できない、という制限を設けた時、パーティの楽しさを最大化せよ。ただしパーティの楽しさは招いた人のconvivialityの和として定義される。

やりかた

木DP。
dp[idx][prevuse]:=（頂点idxを根とする部分木において、idxの親をパーティに招いたかどうかを状態として持たせた場合のconvivialityの最大値）

このように置くと、
idxの親を招いた場合にはidxを招くことはできず、
招いていない場合には、idxを招くことができるし、招かないこともできる。

convivialityがマイナスの場合はそもそも招かなくていい。
以下ソース。

int p[6001], dp[6001][2];
vector<vector<int> >g;

int dfs(int idx, bool prevuse){
  if(dp[idx][prevuse] != -1) return dp[idx][prevuse];
  
  int ret = 0;
  if(prevuse){//idxの親を招いている場合
    for(int i = 0; i < g[idx].size(); i++){
      int next = g[idx][i];
      ret += dfs(next, false);
    }
  }else{//招いていない場合
    int s1 = 0, s2 = 0;
    for(int i = 0; i < g[idx].size(); i++){
      int next = g[idx][i];
      s1 += dfs(next, false); //idxを招く
      s2 += dfs(next, true);  //idxを招かない
    }
    ret = max(s1, s2 + max(p[idx], 0));
  }
  return dp[idx][prevuse] = ret;
}


int main(int argc, char **argv){
  int N;
  scanf("%d", &N);
  g.clear();
  g.resize(N);
  for(int i = 0; i < N; i++) scanf("%d", p + i);

  int a, b;
  vector<bool> f(N, false);
  for(int i = 0; i < N - 1; i++){
    scanf("%d %d", &a, &b);
    g[b - 1].push_back(a - 1);
    f[a - 1] = true;
  }
  int s;
  for(s = 0; s < N; s++) if(!f[s]) break;//探索は根から始める
  FILL(dp, -1);

  printf("%d\n", dfs(s, false));
  scanf("%d %d", &a, &b);
  return 0;
}