Hatena::Grouptopcoder

naoya_t@topcoder RSSフィード

2010-07-30

SRM477 Easy: Islands

| 01:46 | SRM477 Easy: Islands - naoya_t@topcoder を含むブックマーク はてなブックマーク - SRM477 Easy: Islands - naoya_t@topcoder SRM477 Easy: Islands - naoya_t@topcoder のブックマークコメント

寝倒し回。

  • 隣接する六角形のマス目同士が異なる属性なら海岸。それだけ
  • 最近HHKB触ってなくて打鍵がもたつく...
  • 229.37 (8'40'')
  • passed
  • とりあえずこれが取れてればレーティングは微増だったっぽい
using namespace std;
#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()

class Islands {
 public:
  int beachLength(vector <string> kingdom) {
    int R=sz(kingdom),C=sz(kingdom[0]);
    int b=0;
    rep(r,R){
      rep(c,C-1){
        if(kingdom[r][c]!=kingdom[r][c+1])b++;
      }
    }
    for(int r=0;r<R-1;r+=2){
      rep(c,C){
        if(kingdom[r][c]!=kingdom[r+1][c])b++;
      }
      rep(c,C-1){
        if(kingdom[r][c+1]!=kingdom[r+1][c])b++;
      }
    }
    for(int r=1;r<R-1;r+=2){
      rep(c,C){
        if(kingdom[r][c]!=kingdom[r+1][c])b++;
      }
      rep(c,C-1){
        if(kingdom[r][c]!=kingdom[r+1][c+1])b++;
      }
    }
    return b;
  }
};

SRM477 Medium: PythTriplets

| 01:46 | SRM477 Medium: PythTriplets - naoya_t@topcoder を含むブックマーク はてなブックマーク - SRM477 Medium: PythTriplets - naoya_t@topcoder SRM477 Medium: PythTriplets - naoya_t@topcoder のブックマークコメント

寝倒し回

  • なんだ最大フローで解ける問題じゃん
    • GCJの問題でこういう系のなかった?
    • 最大マッチングを求める問題は、全てのメンバーを二部グラフの両側に置いて、可能な結合パターンのところに容量1のパイプを敷いて、ソースとシンクを別途設け、ソースから二部グラフの一方の全メンバーにそれぞれ容量1のパイプを、二部グラフのもう一方の全メンバーからシンクへそれぞれ容量1のパイプを敷き、ソースからシンクへの最大フローを求めればよい。
    • 2階調画像のノイズ消去に同様の手法が使えるのが面白いです
  • あ。答えが2倍になってる。最後に2で割ればおk
  • submitted
  • 396.39 (15'22'')
  • failed system test...
    • GCDチェック忘れてるし
    • もう馬鹿馬鹿馬鹿
    • gcd()いれたらpassed system test
    • こういう抜けた所はどうにかしたい...これも取れてればrating1700行けるところなのに
  • 以下、通るコード。コメントアウトしてるgcd()の部分が抜け。
    • うわ。皆さんの日記みたらGCD忘れが意外に多い。ナカーマ><
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vector<int> > vvi;
typedef vector<string> vs;
typedef vector<long long> vll;
#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())

vector<string> split(string str, int delim=' ')
{
  vector<string> result;

  const char *s = str.c_str();
  if (delim == ' ') {
    for (const char *p=s; *p; p++) {
      if (*p == delim) s++;
      else break;
    }
    if (!*s) return result;

    for (const char *p=s; *p; p++) {
      if (*p == delim) {
        if (s < p) {
          string a(s,p-s);
          result.push_back(a);
        }
        s = p + 1;
      }
    }
    if (*s) result.push_back(s);
  } else {
    for (const char *p=s; *p; p++) {
      if (*p == delim) {
        string a(s,p-s);
        result.push_back(a);
        s = p + 1;
        if (*s == '\0') result.push_back("");
      }
    }
    if (*s) result.push_back(s);
  }

  return result;
}

vector<int> map_atoi(vector<string> nums)
{
  vector<int> vals(nums.size());
  for (int i=nums.size()-1; i>=0; i--) vals[i] = atoi(nums[i].c_str());
  return vals;
}

string join(vector<string> strs, const string &delim="")
{
  int n=strs.size(); if (n==0) return "";
  stringstream ss;
  ss << strs[0];
  for(int i=1;i<n;i++) { ss << delim << strs[i]; }
  return ss.str();
}

#define infty 987654321
int maximumFlow(const vector<vector<int> >& capacity, int s, int t) {
  int w = capacity.size();
  // residual networks
  vector<vector<int> > resid(w, vector<int>(w,0));
  for(int j=0; j<w-1; ++j){
    for(int k=j+1; k<w; ++k){
      resid[j][k] = capacity[j][k];
      resid[k][j] = 0;
    }
  }
  // find another way
  for (int total=0; ;++total) {
    bool another_way = false;
    vector<int> prev(w, infty);
    queue<pair<int,int> > q; q.push(pair<int,int>(s,-1));
    while (!q.empty()) {
      pair<int,int> p = q.front();
      int node = p.first, prev_node = p.second;
      q.pop();
      prev[node] = prev_node;
      if (node==t) { another_way = true; break; }
      rep(i,w) {
        if (resid[node][i] == 0) continue;
        if (prev[i] < infty) continue;
        q.push(pair<int,int>(i,node));
      }
    }
    // no more ways
    if (!another_way) return total;
    for (int node=t; node!=s; node=prev[node]) {
      int prev_node = prev[node];
      resid[prev_node][node]--;
      resid[node][prev_node]++;
    }
  }
  return 0;
}

//ll gcd(ll m, ll n)
//{
//  if (m == 0 || n == 0) return 0;
//  if (m == 1 || n == 1) return 1;
//  if (m == n) return m;
//  while (1) {
//    if (m == 0) return n;
//    if (n == 0) return m;
//    if (m > n) m %= n; else n %= m;
//  }
//}

class PythTriplets {
 private:
  ll sq(ll zz){
    ll zd = (ll)sqrt((double)zz);
    return (zd*zd == zz);
  }
  bool pyth(ll x, ll y){
//  if(gcd(x,y)>1) return false;
    return sq(x*x + y*y);
  }
 public:
  int findMax(vector <string> stick) {
    vector<int> st=map_atoi(split(join(stick)));//1-999999 x 1-200
    int n=sz(st);
    int w = 1+n+n+1;
    vector<vector<int> > capacity(w, vector<int>(w,0));
    rep(i,n) capacity[0][1+i] = capacity[1+n+i][1+n+n] = 1;
    rep(i,n)rep(j,n){
      if(i==j)continue;
      if(pyth(st[i],st[j])) capacity[1+i][1+n+j]=1;
    }
    int maxflow = maximumFlow(capacity, 0, 1+n+n);
    return maxflow/2;
  }
};
トラックバック - http://topcoder.g.hatena.ne.jp/n4_t/20100730