naoya_t@topcoder

SRM486

02:08 |

とりあえずregisterしたものの疲れたしあーもういいや寝ちゃおう寝ちゃおうと思って不参加を決め込んだつもりが0:02過ぎて部屋覗いたらcafelierさんとかsemiexpさんが跋扈していらっしゃったので参戦することにしたRoom11

総括

300: 90.0/passed system test

450: 321.07/passed system test

1000: Opened

411.07p + 0p

• 1000点問題をちょっと考えてあと10分強では書ききれないと悟り300+450を確実に取りに行こうと考えた。
• 300で(1,4)で"/+*"を返すような間抜けな落とし穴があったので終了15秒前ぐらいにresubmitして塞ぐなどした。

Room: #9/20

DivI: #192/774

Rating: 1582→1649 自己ベスト更新キター

脳内解説

珍しく3問開いたので3問分書かねば…

Easy(300): OneRegister

• s,tともに≧1。
  • 減算を使うと0になって終了だがt≧1なので使い途がない
  • 除算を使うと1になる。いつやっても1になる。ならば最初にやるのがコード最短
  • 加算は倍増、乗算は自乗。
• というわけで、s（または1）から始めて {２倍 | 自乗}* してtに辿りつく道を探す。
• コードはtから1/2ないし平方根をとる形でsか1に辿りつくまで繰り返す感じのを書いた
  • 平方根って言っても整数にならないといけないので、√が整数になるやつだけmapで用意しておきました
• 200点台でsubmit
• sが1の場合にも最初に / から始めてしまうことに残り2分ぐらいで気づいてresubmitして90.0点
• passed system test

#define sz(a)  int((a).size())
#define pb  push_back
#define rep(var,n)  for(int var=0,lim=(n);var<lim;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> ii;
typedef long long ll;
#define cons(x,y) make_pair((x),(y))

class OneRegister {
 public:
  string getProgram(int s, int t) {
    if (s==t) return "";

    map<int,int> m;
    rep(i,32768) m[i*i] = i;

    vector<char> code;
    priority_queue<pair<int,string> > pq;
    pq.push(cons(t,""));

    vector<string> ansq;
    
    while(!pq.empty()){
      pair<int,string> h=pq.top(); pq.pop();

      if (h.first == 1 && s!=1) { ansq.pb("/"+h.second);continue; } /// ここの取ってつけたような "&& s!=1" がresubmit更新部分
      else if (h.first == s) { ansq.pb(h.second);continue; }
          
      if (found(m,h.first)) pq.push(cons(m[h.first],"*"+h.second));
      if (h.first % 2 == 0) pq.push(cons(h.first/2,"+"+h.second));
    }
    if (sz(ansq)) {
      vector<pair<int,string> > a2;
      tr(ansq,it) a2.pb(cons(sz(*it),*it));
      sort(all(a2));
      return a2[0].second;
    }
    
    return ":-(";
  }
};

Easy(450): QuickSort

• シミュレーションするだけ？Medium問題にしては易しすぎないか？
• 計算量的には 50,49,...,1 が通れば良いのではないかと
• 単純なメモ化でローカルで660msで行けたので提出
• passed system test

#define sz(a)  int((a).size())
#define pb  push_back
#define rep(var,n)  for(int var=0,lim=(n);var<lim;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())

map<vector<int>,double> mm;
class QuickSort {
  double cost(const vector<int>& L){
    int n=sz(L); if (n<=1) return 0.0;
    if(found(mm,L)) return mm[L];
    
    double tc=0;
    rep(i,n){
      int p=L[i];
      int c=0;
      vector<int> L1, L2;
      rep(j,n){ if (j==i) continue;
        int l=L[j];
        if (l<p) { L1.pb(l); if (j>i) c++; }
        if (l>p) { L2.pb(l); if (j<i) c++; }
      }
      tc += c + cost(L1) + cost(L2);
    }
    double v=tc/n;
    mm[L] = v;
    return v;
  }
 public:
  double getEval(vector <int> L) {
    return cost(L);
  }
};

Hard(1000): BatmanAndRobin

• すべての点をどちらかに含む２つのconvex hullを互いに接しないように作った時に、面積の差が最少になった時の大きい方の面積が答え
• convex hullまわりのあれこれについてはGCJか何かの時に書いた覚えがあるが
• どうやって２つに分けるか（何を試して、何は試さなくてよいのか）適当な計算量で済むのか考えつかず、残り10分強は300と450を確実に取りに行くのに使おうと決めた。BatmanとRobinの物語についてはあとで考えたい。
  • 「ハッ，交差しない2つの凸包は直線で2つに分離できるはず!!」…orz
  • そゆこと
  • cf. 「凸集合の分離定理」 http://en.wikipedia.org/wiki/Separating_axis_theorem (via cafelier)

自己ベスト更新キター