Regionals 2008 :: Europe - Northwestern

参加出来なかったけど会津の練習会で行われていた
http://rhodon.u-aizu.ac.jp:8080/arena/room.jsp?id=596
http://livearchive.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=326
E以外

4286 - Equilibrium Mobile

問題

モビールを吊り合わせるために変えるべきおもりの数を求めよ

制約

深さ16以下

解法

各おもりは同じ深さならば同じ重さでなければならない。
深さが１個下がると必ずおもりの重さの和は２倍になる。
よって、あるおもりの集合において、根の部分で考えた重さが同じなら、その集合の重さを変えずに釣り合わせることができる。
全てのおもりについて、根の部分で考えた重さをテーブルに入れていき、最も数の多い重さに合わせるというふうに考えれば良い。

4287 - Proving Equivalences

問題

n個の命題が全て同値であることを証明したい。
今、m個についてはA⇒Bを証明済みである。
最低あと何個A⇒Bを証明すればよいか。

制約

1 ≤ n ≤ 20000
0 ≤ m ≤ 50000

解法

n頂点で、A⇒Bを証明済みならば頂点Aから頂点Bへ辺を張ったグラフを考える。
このグラフに辺を加えることにより全体を強連結にすれば、全て同値と証明したことになる。
すなわち、全体を強連結にするために最低必要な辺の数を求める。
まずこのグラフを強連結成分分解する。
すると連結成分に分かれるが、連結成分をサイクル状につなげていけば全体が強連結になる。
入次数0、出次数0の頂点をそれぞれカウントし、そのmaxが答えとなる。
ただし、もともと全体が強連結のとき、答えは0となることに注意。

4288 - Cat vs. Dog

問題

c匹の猫とd匹の犬を番組に出演させることを考える。
v人の人がいて、それぞれ猫好きか犬好きである。
猫好きの人は、ある１匹の猫を出演させて欲しく、ある１匹の犬を出演させてほしくない。
犬好きの人はその逆である。
できるだけ多くの人の希望に合わせるように出演する犬猫を決めたとき、希望通りになる人の数は最大何人か。

制約

1 ≤ c, d ≤ 100
0 ≤ v ≤ 500

解法

人を頂点としたグラフを考える。
ここで、ある人とある人の希望が相容れないとき、その頂点間に辺を張る。
このとき、猫好きと犬好きで別れた二部グラフとなる。
このグラフにおける最大独立集合が答えとなる。
二部グラフなので二部マッチングに帰着される。

4289 - Disgruntled Judge

aとbを回すだけなのだけど、1億だったので無理かと思って無駄に考えてしまった。

4290 - Easy Climb

4291 - Sculpture

問題

直方体n個によって作られる物体を考える。
この物体は連結でない場合もある。
このとき、この物体の体積と表面積を求めよ。
ただし、中に空洞があったとしても、物体を水に入れたとき水が入ってこないような部分に関しては、表面積を加えたり体積を減らしたりしない。（サンプル２）

制約

n<=50
1<=座標<=500

解法

普通に幾何でやるのは一生かかっても出来そうにない。
座標圧縮して、３次元テーブルに空間上のセル（直方体）を対応させる。
各セルが、物体の内部か外部かはBFSで調べる。
座標0の番兵を使ってこのBFSを楽にした。
表面積は、隣接セルが外側のときに対応する面積を加算というふうにやる。
何故か速度１位だった。

ソース

struct P {
  int x,y,z;
  P(int x, int y, int z) : x(x),y(y),z(z) {}
  P() {}
};

P p0[50];
P p[50];

void UNIQUE(vector<int> &v) {
  sort(ALL(v));
  v.erase(unique(ALL(v)), v.end());
}

bool cell[105][105][105];
bool out[105][105][105];

int rx[1010];
int ry[1010];
int rz[1010];

vector<int> xs, ys, zs;

void PUSH(const P &p) {
  xs.push_back(p.x);
  ys.push_back(p.y);
  zs.push_back(p.z);
}

int main() {
  int T;
  cin >> T;
  while(T--) {
    int n;
    cin >> n;
    xs.assign(1,0); ys.assign(1,0); zs.assign(1,0);
    
    REP(i,n) {
      int x0,y0,z0,x,y,z;
      cin>>x0>>y0>>z0>>x>>y>>z;
      p0[i]=P(x0,y0,z0);
      p[i]=P(x0+x,y0+y,z0+z);
      PUSH(p0[i]);
      PUSH(p[i]);
    }
    
    UNIQUE(xs);
    UNIQUE(ys);
    UNIQUE(zs);

    int nx = xs.size();
    int ny = ys.size();
    int nz = zs.size();
    
    REP(i,nx) rx[xs[i]] = i;
    REP(i,ny) ry[ys[i]] = i;
    REP(i,nz) rz[zs[i]] = i;
    
    memset(cell,0,sizeof(cell));
    REP(i,n) {
      for (int x=rx[p0[i].x]; x<rx[p[i].x]; ++x) {
        for (int y=ry[p0[i].y]; y<ry[p[i].y]; ++y) {
          for (int z=rz[p0[i].z]; z<rz[p[i].z]; ++z) {
            cell[x][y][z] = 1;
          }
        }        
      }
    }
    
    const int dx[] = {-1,1,0,0,0,0};
    const int dy[] = {0,0,-1,1,0,0};
    const int dz[] = {0,0,0,0,-1,1};

    memset(out,0,sizeof(out));
    queue<P> Q;
    Q.push(P(0,0,0));
    out[0][0][0] = 1;
    while(!Q.empty()) {
      P p = Q.front(); Q.pop();
      REP(i,6) {
        int x=p.x+dx[i];
        int y=p.y+dy[i];
        int z=p.z+dz[i];

        if (x<0||x>=nx||y<0||y>=ny||z<0||z>=nz) continue;
        if (cell[x][y][z]) continue;
        if (!out[x][y][z]) {
          out[x][y][z] = 1;
          Q.push(P(x,y,z));
        }
      }
    }
    
    int a = 0, b = 0;
    REP(i,nx-1) {
      REP(j,ny-1) {
        REP(k,nz-1) {
          if (!out[i][j][k]) {
            int lx = xs[i+1]-xs[i];
            int ly = ys[j+1]-ys[j];
            int lz = zs[k+1]-zs[k];

            int sx = ly*lz;
            int sy = lz*lx;
            int sz = lx*ly;
            int t[6] = {sx,sx,sy,sy,sz,sz};
            REP(d,6) {
              int ii = i+dx[d];
              int jj = j+dy[d];
              int kk = k+dz[d];
              if (ii<0|jj<0||kk<0|| out[ii][jj][kk]) {
                a += t[d];
              }
            }
            b += lx*ly*lz;
          }
        }
      }
    }
    cout << a << " " << b << endl;
  }
}

4292 - Matchsticks

問題

マッチn本ちょうど使って、数を作る。
数字の作り方は問題の通り。
このとき作ることが出来る最小と最大の数を求めよ。

制約

2 ≤ n ≤ 100

解法

サンプルからも想像がつくが、最小は出来るだけ8を使い、最大は出来るだけ1を使う。
最大はmod2の場合分け、最小はmod7の場合分けが必要。
最小の場合分けが意味わからなくなったので、メモ化再帰でやった。
メモ化再帰ならあまり考えなくてもできるので楽。

4293 - White Water Rafting

問題

２つの多角形で表されるコースがある。
１つの多角形は１つの多角形を完全に包含している。
２つの多角形の間がコースとなっている。
このとき、このコースを通ることが出来る円の半径の最大値を求めよ。

制約

3<=頂点数<=100

解法

全ての辺同士について、線分と線分の距離を計算し、最小値を２で割る。

4294 - Shuffle

問題

シャッフルしてs曲の音楽を聞く。
ここでは、s曲がランダムで並び替えられ、その順番でs曲全て再生されたらまた並び替えて再生することを繰り返す。
最近再生された曲n個分の記録がある。
このとき、何曲先で再び並び替えが起こりうるかのパターン数を求めよ。

制約

1 ≤ s, n ≤ 100000

解法

flag[i] = i曲先で再び並び替えが起こるなら１
というテーブルを作り、全て1を入れておく。
ある連続s曲（端はこれに限らず）で全ての曲が現れていたら、その区間は正当だと言える。
そうでなければ、その区間は正当では無いので、その区間に対応するflagを0にする。
これを区間を順にずらしながらO(n+s)でやればよい

4295 - Videopoker

問題

テストケースごとに、ポーカーのそれぞれの役の点数が与えられる。
ポーカーでは、任意枚のカードを手札から捨て、デッキから新たに捨てた数だけのカードを引く。
最終的な手札の役によって、得られる点数が決まる。
n個のポーカーの手札が与えられるので、最善の捨て方をしたときに得られる得点の期待値を求めよ。

制約

テストケース<=100
n<=10

解法

ポーカーの役判定については、Spaghetti Sourceにあるものを利用できる。
前処理として、全パターンの手札に対して役を調べておき、テーブルに入れる。
今の手札Aに対して、全パターンの手札でループを回し（手札Bとする）、手札Bにするために手札Aから捨てるべきカードをビット（Sとする）として求める。
ここで、捨てるべきカードは一意に決まることに注意。
手札Bの役は求めてあるので、得点を求めることは容易。
ビット列Sの期待値に、
（Sを捨てることによって手札Bになる確率）　×　得点
を足しこむ。
答えは、全てのビット列の中における期待値の最大値。
ここで、k枚捨てることによって希望の手札になる確率は、

適当にやると時間が危ないかもしれないので、高速化のためのヒント。

• 役のない手札は覚えない。役のある手札は1296420とかになる
• 手札を覚えるのにmapを使わない。配列で十分
• 何を捨てるべきかの計算をO(5)でやる。13*4のテーブルに手札Aに現れたカードを記録しておくと出来る

制限時間6sと書いてあるけど、Statisticsをみると10sかかってる人もいる・・・
デバッグが大変だった。