naoya_t@topcoder

SRM430

12.20+.2008

システムの異常で誰もentryできないまま数分が経過したため、今日のSRMは５分延長。

DIV	level	問題名	競技中	後で	System Test	通過率	備考
1	250	BitwiseEquations	◎			74.89%
1	500	TwinTowns	間に合わず	o	passed	19.69%	12/21 https://topcoder-g-hatena-ne-jp.jag-icpc.org/n4_t/20081221/p2
1	1000	(PickingUp)	-			24.19%

250点問題: BitwiseEquations

→OK。186.96点

そう難しい問題ではないが、オーバーフローが怖くて変な所で切ってしまっていたため数が合わず若干手間取る。

500点問題: TwinTowns

→未提出

題意は理解した。

全パターン探索でいいかなと思ってコーディング。

パターン生成が狂っていて焦る。時間切れ。

今日はチャレンジタイムが大荒れ。室内の500点は全滅。

System Testが通って、結果は全体で365/742位。１問しか解けなかったけど真ん中より少し上。

レーティングは微上昇：1425→1456

SRM430 Div1 Medium: TwinTowns

過去問, 練習 | 18:09 |

とりあえず500点問題をちゃんと解いてみる

あれこれ試行錯誤した末、各都市の姉妹都市提携数（あるいは提携可能な余地）を状態として持つDPで書き直した。

• 全n都市の中から都市を１つ選ぶ
• 残りのn-1都市の中からk個の都市（0≦k≦(maxPartners-その都市が既に提携している都市の数)）を選ぶ各組合せについて、
• 各都市の姉妹都市提携数にこの組合せを加えたものをもとに、
• 都市数が１つ少ない場合について、提携最大数および最短合計距離を算出する。
• 算出結果（提携最大数、最短合計距離）に、この都市からの姉妹提携都市関係を加えて返す。

最初は vector<int> で回していたが、高速化＆メモ化のために long longにパックして回すようにした。

#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <cmath>
using namespace std;

#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++)

inline int get_at(long long arcs, int idx)
{
  return (arcs >> (idx * 2)) & 0x3;
}
inline long long set_at(long long arcs, int idx, int val)
{
  long long mask = 3LL << (idx * 2);
  long long vall = (long long)val << (idx * 2);
  return (arcs & (~mask)) | vall;
}

class TwinTowns {
  int n, maxP;
  int distance[10][10];
  bool available[10][10];

  map<long long,int> memo;

private:
  int findMaximum(long long arcs, int till) {
    if (till == 0) return 0;

    long long key = (arcs << 4) | till;
    if (memo.find(key) != memo.end()) return memo[key];

    int pmax = 0, dmin = INT_MAX;//D_INFTY;
    int count = get_at(arcs,till);

    long long arcs_ = arcs;

    int pat_max = (1 << till) - 1;
    int c_max = maxP - count;

    int arcs_mask = (1 << (till*2)) - 1;

    for (int pat=0; pat<=pat_max; pat++) {
      int c = __builtin_popcount(pat);
      if (c > c_max) continue;

      int d = 0;
      for (int i=0,m=1;i<till;i++,m<<=1) {
        if ((pat & m) == 0) continue;
        if (! available[till][i]) goto next_pat;
        if (get_at(arcs_,i) == maxP) goto next_pat;

        arcs_ = set_at(arcs_, i, get_at(arcs_,i) + 1);
        d += distance[till][i];
      }

      {
        int ans = findMaximum(arcs_ & arcs_mask, till-1);
        int ans_p = c + (ans & 31), ans_d = d + (ans >> 5);
        if (ans_p > pmax) {
          pmax = ans_p; dmin = ans_d;
        } else if (ans_p == pmax) {
          if (ans_d < dmin) dmin = ans_d;
        }
      }
    next_pat:
      arcs_ = arcs;
    }

    int ans = (dmin << 5) | pmax;
    memo[key] = ans;
    return ans;
  }
  
public:
  vector<int> optimalTwinTowns(vector<int> x, vector<int> y, int maxPartners, int minDistance) {
    n = x.size();
    if (n == 1) {
      vector<int> ans(2,0);
      return ans;
    }

    maxP = min(maxPartners,n-1);
    rep(i,n) rep(j,n) available[i][j] = false;

    rep(j,n) {
      rep(i,n) {
        if (i == j) continue;
        int dist = abs(x[i]-x[j]) + abs(y[i]-y[j]); // 1-2000
        if (dist >= minDistance) {
          distance[i][j] = distance[j][i] = dist;
          available[i][j] = available[j][i] = true;
        }
      }
    }

    int a = findMaximum(0, n-1);
    vector<int> ans(2,0);
    ans[0] = a & 31; ans[1] = a >> 5;
    return ans;
  }
};