Hatena::Grouptopcoder

naoya_t@topcoder RSSフィード

2010-05-28

Member SRM 471 Hard(1000): ConstructPolyline

| 12:53 | Member SRM 471 Hard(1000): ConstructPolyline - naoya_t@topcoder を含むブックマーク はてなブックマーク - Member SRM 471 Hard(1000): ConstructPolyline - naoya_t@topcoder Member SRM 471 Hard(1000): ConstructPolyline - naoya_t@topcoder のブックマークコメント

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

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

  • ノートにうにうに3次元(的な)線を描いてみて、クロスするのって戻ってるってことだから最大値なら必然的にクロスしないのでは?と思った(が証明したわけではない)
  • 線分(x_i,y_i,z_i)をどっち向きに繋げるか。p_i={1 or -1}を掛けるとして、合計の長さ(の2乗)は 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個のベクトルから任意の3つを取り出して足したもの
    • なぞの係数を掛けたもの
    • あと十万件ランダムで
  • なるほど、内積を使って進むか戻るか調べるのか。
    • 仮定した進行方向に対してベクトルが成す角度がθなら、内積は|a||b|cosθなので90度未満(進む)なら正、90度(横)で0、90度超(戻る)なら負だ

ktuan

[image]

#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <queue>
using namespace std;

#define Rep(i,n) for(int i=0;i<(n);++i)
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Ford(i,a,b) for(int i=(a);i>=(b);--i)
#define fi first
#define se second
#define pb push_back
#define MP make_pair

typedef pair<int,int> PII;
typedef vector<int> VI;

class ConstructPolyline {
 public:
  long long maximizeLength(vector <int> x, vector <int> y, vector <int> z);
};

const int sogoc = 1200;
int h[55];
int n;

long long ConstructPolyline::maximizeLength(vector <int> x, vector <int> y, vector <int> z) {
  double d = 2 * M_PI / sogoc;
  n = x.size();
  long long result = 0;
  for(int i=0; i<sogoc; ++i) {
    double alpha = i*d;
    double vz = sin(alpha);
    double tt = cos(alpha);
    for (int j=0; j<sogoc; ++j) {
      double beta = j*d;
      double vx = tt * cos(beta);
      double vy = tt * sin(beta);
      for (int t=0; t<x.size(); ++t) {
        double r = vx*x[t] + vy*y[t] + vz*z[t];
        if (r>0) h[t] = 1;
        else h[t] = -1;
      }
      int tx=0, ty=0, tz=0;
      for (int t=0; t<x.size(); ++t) {
        tx += h[t] * x[t];
        ty += h[t] * y[t];
        tz += h[t] * z[t];
      }
      long long cur = (long long)tx*tx + (long long)ty*ty + (long long)tz*tz;
      if (cur > result) result = cur;
    }
  }
  return result;
};
  • こちらは、1200^2=1440000方位について同様の方法(内積が正なら+1、負なら-1を掛けて加算)で求めた総和で距離を求め、その最大を取っている。乱数も変な定数もない。
    • 方位の取り方はalpha(緯度相当),beta(経度相当)にそれぞれ円周を1200分割した角度(rad)を入れるループを回してる
  • サンプルケースだと(ローカル環境で)1件あたり250〜700msec
トラックバック - http://topcoder.g.hatena.ne.jp/n4_t/20100528

2010-05-27

Member SRM471 Medium(500): ThirteenHard (再考)

| 12:43 | Member SRM471 Medium(500): ThirteenHard (再考) - naoya_t@topcoder を含むブックマーク はてなブックマーク - Member SRM471 Medium(500): ThirteenHard (再考) - naoya_t@topcoder Member SRM471 Medium(500): ThirteenHard (再考) - naoya_t@topcoder のブックマークコメント

(最初に書いたコードはこちら: http://topcoder.g.hatena.ne.jp/n4_t/20100527/1274893027

  • (N-1)番目に到達すると分かっている(最短かは分からない)時刻があるなら、それ以降の時刻については検証無意味。
    • priority_queueを使ったほうがスマートかな。
  • int[25][2^13]である駅までの最短時間が分かったとしても、その後でmod13死にするかもしれないのでmod13が違うやつは生かしておくべき。最短との比較枝切りをやめると最悪ケースでTLE
    • やっぱりint[25][13][2^13]でないと駄目。
  • それから
    ...
    bool boo = false;
    if (sm>0) {
      for(int k=0,p=1; k<13; k++,p<<=1){
        if (msk & p) {
          if (((sm + 13) - k) % 13 == 0) { boo=true; break; }
        }
      }
    }
    if (boo) continue;
    ...

ここは

    if (msk & (1 << (sm % 13))) continue;

と等価ではないか!

勿論、C/C++の演算子の優先順位に従えば括弧は省略できて

    if (msk & 1 << sm % 13) continue;

と書けるが直感的にこれが(msk&1)<<(sm%13)などに見えてしまって怖くてたまらない。

  • てな感じで書き直したのがこれ:
#define sz(a)  int((a).size())
#define pb  push_back
#define all(c)  (c).begin(),(c).end()
#define tr(c,i)  for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)
#define rep(var,n)  for(int var=0;var<(n);var++)
#define found(s,e)  ((s).find(e)!=(s).end())

typedef pair<int,int> ii;
typedef pair<int,ii> iii;
#define cons(x,y) make_pair((x),(y))
#define car(x) ((x).first)
#define cdr(x) ((x).second)
#define cadr(x) (x).second.first
#define cddr(x) (x).second.second

#define INF 987654321 // 13で割り切れない

class ThirteenHard {
  int conv(char c){
    int d = INF;
    if ('A'<=c && c<='Z') d = 1+(c-'A');
    else if ('a'<=c && c<='z') d = 27+(c-'a');
    return d%13 ? d : INF;
  }

 public:
  int calcTime(vector <string> city) {
    int n=sz(city);
    vector<vector<int> > ds(n,vector<int>(n));
    rep(i,n) rep(j,n) ds[i][j] = conv(city[i][j]);

    vector<vector<vector<int> > > e(n,vector<vector<int> >(13,vector<int>(8192,INF)));

    int goal = n-1;

    priority_queue<iii> q;
    q.push( cons(0,cons(0,0)) );
    while(!q.empty()) {
      iii t=q.top(); q.pop();
      int sm=-car(t), wh=cadr(t), msk=cddr(t);
      int msk2 = msk; if (sm > 0) msk2 |= 1 << sm % 13;

      if (sm >= e[wh][sm%13][msk2]) continue;

      if (wh == goal) return sm;
      e[wh][sm%13][msk2] = sm;
      for(int j=0,m=1; j<n; j++,m<<=1) {
        int d_ = ds[wh][j];
        if (d_ != INF) {
          int sm2 = sm + d_;
          if (sm2 % 13 == 0) continue;
          if (msk2 & 1 << sm2 % 13) continue;
          q.push( cons(-sm2,cons(j, msk2)) );
        }
      }
    }
    return -1;
  }
};
  • passed system test.

追記

  • スタート地点からのラップタイムではなく、スタート以降現在までの全地点から現在地点までの所要時間(のmod13)を持てばint[25][2^13]でいいのか。
    • 余り0なら持つ必要がないのでint[25][2^12]で良いとか(by cafelier先生)
トラックバック - http://topcoder.g.hatena.ne.jp/n4_t/20100527

2010-01-15

SRM458

| 02:57 | SRM458 - naoya_t@topcoder を含むブックマーク はてなブックマーク - SRM458 - naoya_t@topcoder SRM458 - naoya_t@topcoder のブックマークコメント

01.14.2009+

DIVlevel問題名競技中後でSystem Test通過率備考
1 250 BouncingBalls 15'45'' - passed system test - 196.42pt
1 450 NewCoins 間に合わず - - -
1 900 - 開いてない -

250点問題: BouncingBalls

  • すべてのパターンについて調べても高々2^12通り
  • 跳ね返る回数=跳ね返らず直進するとした場合に交差する回数
  • 傾きが同じなら除外
  • 交点が(0..t]にあるか
  • 15'45''
  • passed system test
#define sz(a)  int((a).size())
#define rep(var,n)  for(int var=0;var<(n);var++)
#define all(c)  (c).begin(),(c).end()
#define tr(c,i)  for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)

class BouncingBalls {
  vector<int> y,v;
  int n,t;
  int test(){
    int cnt = 0LL;
    for(int i=0;i<n-1;i++){
      for(int j=i+1;j<n;j++){
        if (v[i]==v[j]) continue;
        double at = (double)(y[j] - y[i])/(v[i] - v[j]);
        if (0 < at && at <= t) cnt++;
      }
    }
    return cnt;
  }
 public:
  double expectedBounces(vector<int> x, int T) {
    n=sz(x); t=T;
    y.assign(all(x)); v.resize(n);
    int ps=1<<n, cnt=0;
    rep(p,ps){
      for(int j=0,m=1;j<n;j++,m<<=1) v[j] = (p&m) ? 1 : -1;
      cnt += test();
    }
    return (double)cnt / ps;
  }
};

450点問題: NewCoins

  • Sample Caseが全部通るやつは書けた。まだ30分ちょい残ってる。
  • でも最悪とは言えないまでもひどいケースで試してTLE
  • これがなんとかならないとsubmitできない
  • なんとかならなかった
  • 提出を諦めた(Sample Caseしか通らない)コードを晒しておく:
#define sz(a)  int((a).size())
#define pb  push_back
#define FOR(var,from,to) for(int var=(from);var<=(to);var++)
#define rep(var,n)  for(int var=0;var<(n);var++)
#define all(c)  (c).begin(),(c).end()
#define tr(c,i)  for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)
#define found(s,e)  ((s).find(e)!=(s).end())

typedef pair<int,int> i_i;

class NewCoins {
  int n,maxprice;
  vector<i_i> av; int avn;
  vector<int> coins;

  map<vector<int>,int> memo;
  map<vector<int>,int> mmc;

  int sub() {
    int cn = sz(coins); 

    if (found(memo,coins)) return memo[coins];
    
    int lastcoin = coins.back(); coins.pop_back();

    int cntnow=0;
    if (found(mmc,coins)) {
      cntnow = mmc[coins];
      coins.pb(lastcoin);
      rep(i,avn){
        if (av[i].first>=lastcoin){
          int k = (av[i].first / lastcoin) * av[i].second;
          int m = lastcoin / coins[cn-2];
          cntnow -= (m-1)*k;
        }
      }
    } else {
      // cn=1
      coins.pb(lastcoin);
      rep(j,avn){
        if (av[j].first % lastcoin) {
          memo[coins]=-1; return -1;
        }
        cntnow += av[j].second * av[j].first/lastcoin;
      }
    }

    mmc[coins] = cntnow;
    cn++;

    for(int b=lastcoin*2;b<=maxprice;b+=lastcoin){
      coins.pb(b);
      int cnt = sub();
      coins.pop_back();
      if (cnt >= 0) cntnow = min(cntnow, cnt);
    }
    memo[coins] = cntnow;
    return cntnow;
  }
 public:
  int minCoins(vector<int> price) {
    memo.clear();
    mmc.clear();
    n=sz(price); maxprice = price[n-1];
    map<int,int> a;
    rep(i,n) { int p=price[i]; if (found(a,p)) a[p]++; else a[p]=1; }
    av.assign(all(a)); avn = sz(av);
    if (avn==1) return av[0].second;

    int minc=INT_MAX;
    coins.clear();
    for(int b=1;b<=price[0];b++){
      coins.pb(b);
      int cnt = sub();
      coins.pop_back();
      if (cnt >= 0) minc = min(minc, cnt);
    }
    return minc;
  }
};

900点問題: 開いてない

Challenge phase

  • 他の人の450を見てみた。Javaが多い。あと、なんか短い。

System Test

o - -

196.42 points

結果

room:9/20位

DIV1:282/680位

1292→1366(+74) 少し持ち直したがまだ青。

http://gyazo.com/676d02329e29cd36fe112a183fee9b69.png

トラックバック - http://topcoder.g.hatena.ne.jp/n4_t/20100115