2010-05-28

Member SRM 471 Hard(1000): ConstructPolyline

たまにはDiv1 Hard問題も眺めてみないとSTL使いこなし以上の実力がつかないと思いHard問題を開いてみる

３次元空間で、最大50本の線分が与えられる。これをクロスさせずに繋いでいった時の両端の距離の最大値を求める

ノートにうにうに3次元（的な）線を描いてみて、クロスするのって戻ってるってことだから最大値なら必然的にクロスしないのでは？と思った（が証明したわけではない）
線分(x_i,y_i,z_i)をどっち向きに繋げるか。p_i={1 or -1}を掛けるとして、合計の長さ（の２乗）は $L^2=(\sum_{i=1}^Np_ix_i)^2+(\sum_{i=1}^Np_iy_i)^2+(\sum_{i=1}^Np_iz_i)^2 =\sum_{i=1}^N\sum_{j=1}^Np_ip_j(x_ix_j+y_iy_j+z_iz_j)$
$x_ix_j+y_iy_j+z_iz_j$ は50x50個前もって計算できる。正かもしれないし負かもしれない。零もありうるよね
$p_i$ , $p_j$ （それぞれ+1か-1）の組み合わせが $2^{50}$ 通りあるので、これを調整して $L^2$ を最大化したい。

1. サンプルケースは全部通るけどnが大きいと間違いなくTLEなコード：

というわけでまずは愚直に。 $O(N^22^N)$ とか馬鹿なの？死ぬの？

#define rep(var,n)  for(int var=0;var<(n);var++)
typedef long long ll;

class ConstructPolyline {
  int n;
  // inline int sign(int x){ return x ? (x > 0 ? 1 : -1) : 0; }
 public:
  long long maximizeLength(vector <int> x, vector <int> y, vector <int> z) {
    n = x.size();
    vector<vector<int> > aij(n,vector<int>(n,0));
    // vector<vector<int> > sij(n,vector<int>(n,0));
    rep(i,n) rep(j,n) {
      aij[i][j] = x[i]*x[j] + y[i]*y[j] + z[i]*z[j];
      // sij[i][j] = sign(aij[i][j]);
      sum += (ll)abs(aij[i][j]);
    }
    ll lim=1LL << n, summax = 0;
    for(ll m=0; m<lim; m++) { // ... 2^50
      ll sum = 0;
      rep(i,n) {
        int pi = (m & (1LL << i)) ? 1 : -1;
        rep(j,n) {
          int pj = (m & (1LL << j)) ? 1 : -1;
          sum += pi * pj * aij[i][j];
        }
      }
      summax = max(summax,sum);
    }
    return summax;
  }
};

サンプルテストは全部通るけど...N=50に行くまでもなくTLE死の予感
2^50通りの計算に相当する部分を時間内で終わらせるにはどうしたらいいか。
LayCurse先生曰く：

でも，2^50通りしか考えれないし，リスタート＋ランダム局所探索で通っちゃったりするんじゃない？

そう思ったら通る気がしてきたぞ？

いまから，一瞬で局所探索書いて，サブミットして通したら上位狙える．

いいや，やっちゃえ．

（中略）

てか，Hard，やっぱりランダムで通るんかい．まぁ，想定解法ではないはずなのでのちのち勉強．
SRM471 DIV1 参加記録 - ゲームにっき(仮)

コンテスト途中で通信が切れ、再ログインしてもコンテストへのアクセスができずおそらくノーゲーム（だがなぜかレーティングに反映されている感じ・・・ノーゲームになったかどうかとか、TopCoder主催側の公式アナウンスとかってあるとしたらどこで見られるの？）なので解説とか出てなくて、とりあえずあの状況あの時間で1000点問題を通していた超人達(Petrとktuan)のコードを見てみた。なるほど、こういうのでテスト通るのか。勉強になる。

以下、コードはコピペできなかったのでスクリーンショットを見て手打ちです

Petr

[image]

import java.util.*;

public class ConstructPolyline {
  static class Unit {
    double x;
    double y;
    double z;

    Unit(double x, double y, double z) {
      double len = Math.sqrt(x*x + y*y + z*z);
      if (Math.abs(len) < 1e-12) {
        this.x = 0;
        this.y = 0;
        this.z = 0;
      } else {
        this.x = x / len;
        this.y = y / len;
        this.z = z / len;
      }
    }
  }

  long res;
  int[] x;
  int[] y;
  int[] z;

  public long maximizeLength(int[] x, int[] y, int[] z) {
    this.x = x;
    this.y = y;
    this.z = z;

    Unit[] u = new Unit[x.length];
    for (int i=0; i<x.length; ++i)
      u[i] = new Unit(x[i],y[i],z[i]);

    res = 0;
    for (int i=0; i<x.length; ++i)
      for (int j=i+1; j<x.length; ++j)
        for (int k=j+1; k<x.length; ++k) {
          Unit sum = new Unit(u[i].x + u[j].x + u[k].x,
                              u[i].y + u[j].y + u[k].y,
                              u[i].z + u[j].z + u[k].z);
          verify(sum);

          double ki = 0.439156431;
          double kj = 0.389754875;
          double kk = 0.572398221;
          sum = new Unit(ki*u[i].x + kj*u[j].x + kk*u[k].x,
                         ki*u[i].y + kj*u[j].y + kk*u[k].y,
                         ki*u[i].z + kj*u[j].z + kk*u[k].z);
          verify(sum);
        }
    Random r = new Random(4392714938214321L);
    for (int i=0; i<100000; ++i) {
      Unit sum = new Unit(r.nextDouble()*2-1, r.nextDouble()*2-1, r.nextDouble()*2-1);
      verify(sum);
    }
    return res;
  }

  private void verify(Unit sum){
    long sx=0;
    long sy=0;
    long sz=0;
    for (int i=0; i<x.length; ++i) {
      double prod = sum.x * x[i] + sum.y * y[i] + sum.z * z[i];
      if (prod >= 0) {
        sx += x[i];
        sy += y[i];
        sz += z[i];
      } else {
        sx -= x[i];
        sy -= y[i];
        sz -= z[i];
      }
    }
    res = Math.max(res, sx*sx + sy*sy + sz*sz);
  }
}

スタート地点からある方向に向かうとして、N個のベクトルがその方向に進む感じなら +1, 戻る感じなら -1 を掛けたベクトルを加算。てのをいろいろな向きで試して最大値を得ている
- N個のベクトルから任意の３つを取り出して足したもの
- なぞの係数を掛けたもの
- あと十万件ランダムで
なるほど、内積を使って進むか戻るか調べるのか。
- 仮定した進行方向に対してベクトルが成す角度がθなら、内積は|a||b|cosθなので90度未満（進む）なら正、90度（横）で0、90度超（戻る）なら負だ

ktuan