Hatena::Grouptopcoder

shnyaの参戦記録

2011-06-06練習&一部本番

SRM 508 Div2 Easy CandyShop 23:18  [http://www.topcoder.com/stat?c=problem_statement&pm=11439&rd=14437:title=SRM 508 Div2 Easy CandyShop] - shnyaの参戦記録 を含むブックマーク はてなブックマーク -  [http://www.topcoder.com/stat?c=problem_statement&pm=11439&rd=14437:title=SRM 508 Div2 Easy CandyShop] - shnyaの参戦記録

場所がわからなくなったキャンディショップを、記憶を頼りに探す問題。具体的には、過去に訪れた場所(x,y)と半径何m以内(マンハッタン距離)の場所にあったかという情報を、訪れた回数分与えられる。

キャンディショップの候補となる場所は、上記の情報で得られたポイント(整数の格子状の点)の積集合である。

候補となる場所の数を答えよ。

これほんとにDiv 2 Easy?という感じに難しかった。

ポイント
1 <= R <= 100なので、各回ごとに1万ポイントが候補としてあげられる。普通にO(n^2)で積集合をとるとTLE。

模範解答としては、先に300x300の地図の中から、条件に合致しない点(候補とならない点)にダメマークをつけていき、生き残った場所を数える。

下は単純にシミュレーションをした回答。

上記のTLEな問題(Div2 EASYでTLEが問題になるとは思わなかった)に加えてset_intersectionの前にsortを忘れて3回もサブミットしちまった。。。

class CandyShop {
public:
  int countProbablePlaces( vector <int> X, vector <int> Y, vector <int> R ) {
    int n = X.size();
    vector<pair<int,int> > s;
    for(int i = 0; i < n; i++){
      int x = X[i];
      int y = Y[i];
      int r = R[i];
      vector<pair<int,int> > s2;
      for(int j = -r; j <= r; j++){
        for(int k = -r; k <= r; k++){
          if(abs(j) + abs(k) > r) continue;
          int newx = x + j; int newy = y + k;
          s2.push_back(make_pair(newx,newy));
        }
      }
      if(i == 0){
        s = s2;
      }else{
        set<pair<int,int> > s3;
        sort(s.begin(),s.end());
        sort(s2.begin(),s2.end());
        set_intersection(s.begin(),s.end(),s2.begin(),s2.end(),inserter(s3,s3.begin()));
        s = vector<pair<int,int> >(s3.begin(),s3.end());
      }
    }
    return s.size();
  }
};

SRM 508 Div2 Medium DivideAndShift 23:18  [http://www.topcoder.com/stat?c=problem_statement&pm=11434&rd=14437:title=SRM 508 Div2 Medium DivideAndShift] - shnyaの参戦記録 を含むブックマーク はてなブックマーク -  [http://www.topcoder.com/stat?c=problem_statement&pm=11434&rd=14437:title=SRM 508 Div2 Medium DivideAndShift] - shnyaの参戦記録

N個のポイント上のM個目の場所に目的の石がある。

これをなんとか1個目に持って行きたい。

ただし、行うことができる操作は全体を素数で割ること(目的の石が含まれる区間だけ抜き出される)と、左か右にシフトすることのみ。

最小の操作回数を答えよ。


最初は素数リストを作るところから始める。でも素数なんていらないやと思って全部消す。

なんだかんだやって、とりあえず約数で割ってから左右に移動しても答えは同じじゃないかと考える。要は、左右の移動と割る操作の順序が可換かどうかということだけど、自信は全くないもののいけそうかなと思ってとりあえず組む。答え合わない。試合終了。


方針は合ってたっぽいけど、バグが取れなかった。慌てちゃダメ。

class DivideAndShift {
public:
  int count_div(int n){
    int target = n;
    int j = 2;
    int res = 0;
    while(target != 1){
      while(target % j == 0){
        target /= j;
        res++;
      }
      j++;
    }
    return res;
  }

  int getLeast( int N, int M ) {
    int minn = numeric_limits<int>::max();
    for(int i = 1; i <= N; i++){
      if(N % i != 0) continue;
      int x = count_div(i);
      int m = M % (N / i);
      if(m == 0) m = N / i;
      minn = min(minn,x+min(abs(m - 1), abs((N / i) + 1 - m)));
    }
    return minn;
  }
};

SRM 449 Div2 Medium OddDivisors 23:18  [http://www.topcoder.com/stat?c=problem_statement&pm=1854:title=SRM 449 Div2 Medium OddDivisors] - shnyaの参戦記録 を含むブックマーク はてなブックマーク -  [http://www.topcoder.com/stat?c=problem_statement&pm=1854:title=SRM 449 Div2 Medium OddDivisors] - shnyaの参戦記録

ふと、知り合いの参加記録を読んでいて気になった問題。

f(x)はxの最大の奇数を返す関数とした時、Nが与えられた場合に、f(1)+f(2)+...+f(n-1)+f(n)の計算結果を返せ。

ただしNは1000,000,000とする。


Nが大きいので工夫がいる。

思いついた解き方は、

1,2,3,...Nまでの数字を奇数のものと偶数のものを分ける。

Nが奇数の場合は、

1,3,5...N
2,4,6....N-1

のように分けることができる。

下段のf(x)の値は以下と等価だから、これを2^k > Nとなるまで繰り返していけばOK。

f(1),f(2),f(3),...,f((N-1)/2)

実はループもなく解析的に解ける、というかまぁ各段階の合計値は階差数列になるはずなので、普通に計算するだけだろうけど、本番だとそれが正しいことを示す(具体的な値をいくつかいれて試す)のが面倒なのでやっぱり下のように解いてたと思う。

ただ、これも各回ごとの最後の値を求めるのに手間取った。

やっぱりこういう問題は紙とペンが欲しい。

class OddDivisors {
public:
  long long findSum( int _N ) {
    LLI N = _N;
    LLI sum = 0;
    for(LLI i = 2; i <= N*2; i *= 2){
      LLI n = N / i;
      LLI an = n * i;
      LLI d = (i/2);
      if(an + d <= N){
        n++;
        an += d;
      }else{
        an -= d;
      }
      sum += n*(an/d + 1) / 2;
    }
    return sum;
  }
};

SRM 463 Div1 Easy RabbitNumbering 23:18  [http://www.topcoder.com/stat?c=problem_statement&pm=10697&rd=14148:title=SRM 463 Div1 Easy RabbitNumbering] - shnyaの参戦記録 を含むブックマーク はてなブックマーク -  [http://www.topcoder.com/stat?c=problem_statement&pm=10697&rd=14148:title=SRM 463 Div1 Easy RabbitNumbering] - shnyaの参戦記録

N匹のウサギがいて、それぞれのウサギを見分けるために数字を割り振ろうとしている。

ただし、ウサギは割り当てられる数字にこだわりがあって、各ウサギごとに最大a_i以下の数字(a_iはそれぞれ異なる)でなければならない。


数字の割り当て方は何通りか?

例を見るとなんとなく方針がわかる。

{5,8}が与えられた時の答えは35通り。

2番目のウサギは1-8までの候補があるが、1番目のウサギが1-5までの数のどれかを取るので実際は7通りしかない。

1番目のウサギは5通りのとり方があるので、7 * 5 = 35

つまり大きい方から順番に計算していけばいい。


class RabbitNumbering {
public:
  int theCount( vector <int> maxNumber ) {
    vector<LLI> s(maxNumber.begin(), maxNumber.end());
    int n = maxNumber.size();
    LLI k = n - 1;
    LLI res = 1;
    LLI m = 1000000007LL;
    for(int i = 0; i < n; i++){
      vector<LLI>::iterator itr = max_element(s.begin(), s.end());
      res *= *itr - k;
      res %= m;
      s.erase(itr);
      k--;
    }
    return res;
  }
};

SRM 463 Div1 Medium Nisoku 23:18  [http://www.topcoder.com/stat?c=problem_statement&pm=10760&rd=14148:title=SRM 463 Div1 Medium Nisoku] - shnyaの参戦記録 を含むブックマーク はてなブックマーク -  [http://www.topcoder.com/stat?c=problem_statement&pm=10760&rd=14148:title=SRM 463 Div1 Medium Nisoku] - shnyaの参戦記録

1.5 <= ai <= 10からなるN個の実数値からなる配列ある。

それらの中から2個のペアを取り出してそれぞれの和か積を計算し、結果を元の配列に戻す。

この操作を残り1個まで繰り返した場合に、残った数が最大となる時の値を答えよ。


むずかった。Eulerで全探索で解く似た問題があったが、1 <= N <= 50のため、それもできない。DPとかも考えたけど厳しい。


1.5という数字に着目して、足した時にかけた値よりも大きくなる場合はどういう場合か考えてみる。

a + b > abなので、1/a + 1/b > 1となる場合。a,bは大きければ大きいほど1/a + 1/bは小さくなるので、1/a + 1/b > 1が成り立つのは、a=1.5, b=3などの小さい値の時だけ。こういう数字は大きくて3, 小さくて1.5となる。

なので、足した方が大きくなる数字を先に計算。残った数字をかけていけばいいのかなーと思ったけどやっぱりダメだった。システムテスト通らず。一応努力の結果として下記に記す。


足した方が大きくなる数字はどの順番に足していく方がいいかわからなかったので、とりあえず最小の2つ、最大の2つを試すがサンプルは通らない。数字の差が開くような組み合わせを選んでやるとうまくいったので、このパターンでやってみた。

class Nisoku {
public:
   double theMax( vector <double> cards ) {
     while(1){
       long double maxd = numeric_limits<long double>::min();
       int maxi = -1, maxj = -1;
       for(int i = 0; i < int(cards.size()); i++){
         for(int j = i+1; j < int(cards.size()); j++){
           if(cards[i] + cards[j] + EPS > cards[i] * cards[j]){
             if(abs(cards[i] - cards[j]) + EPS > maxd + EPS){
               maxi = i;
               maxj = j;
               maxd = abs(cards[i] - cards[j]);
             }
           }
         }
       }
       if(maxi < 0.0) break;
       cards[maxi] += cards[maxj];
       swap(cards[maxj],cards.back());
       cards.pop_back();
     }
     long double res = 1.0;
     for(int i = 0; i < int(cards.size()); i++){
       res *= cards[i];
     }
     return res;
   }
};

Editorialを見ると、先にsortしてから、足した方がいい数の境界を確認しながら最大となる値を探索していた。

以下、Editorialを見てから書いたコード。

class Nisoku {
public:
  double theMax( vector <double> cards ) {
    sort(cards.begin(), cards.end());
    int n = cards.size();
    long double maxn = numeric_limits<int>::min();
    for(int i = 0; i <= n; i+=2){
      long double res = 1.0;
      for(int j = 0; j < i/2; j++){
        res *= cards[j] + cards[i-j-1];
      }
      for(int j = i; j < n; j++){
        res *= cards[j];
      }
      if(maxn < res){
        maxn = res;
      }
    }
    return maxn;
  }
};

SRM 464 Div1 Easy ColorfulStrings 23:18  [http://www.topcoder.com/stat?c=problem_statement&pm=10724&rd=14149:title=SRM 464 Div1 Easy ColorfulStrings] - shnyaの参戦記録 を含むブックマーク はてなブックマーク -  [http://www.topcoder.com/stat?c=problem_statement&pm=10724&rd=14149:title=SRM 464 Div1 Easy ColorfulStrings] - shnyaの参戦記録

"263"のような0-9の数字からなる文字列がある。

この時、全ての部分文字列を考えると、"2","6","3","26","63","263"があり、各文字列の各桁の積が全て異なるとき、Colorfulな文字列であるという。

文字列の長さNが与えられた時、長さNのColorfulな文字列を、辞書順に並べた場合に、K番目にくる文字列を答えよ。

入力のパラメータは、以下の範囲とする。

1 <= N <= 50

1 <= K <= 1,000,000,000


最近は、電車に乗っている間に携帯で問題見ながら考えたりするんだけど、この問題は22:58に問題を開いてから23:18にヒントが思いついたのを覚えている。黄色な人たちは3~5分ぐらいで思いつくと思うけど、やっぱ手間取った。。


とにかくNやKが大きいので、全探索は難しい。かといって、K番目にくる文字列ということでDPやGreedyといったアルゴリズムも使えない。


ちょうど20分間考えたら、各数字は1回しか出ないことに気づく。

それならカラフルな文字列は最長で8文字まで。

N>8の時は存在しないということで空文字列を返せばOK。

N<=8なら全探索で求めることができる、ので帰ってから書いた。

見事にN=1の場合にはまった。

class ColorfulStrings {
  int k;
  string res;
  int N,K;
  void rec(int l, vector<int> &path, set<LLI> &exists){
    if(res.size() > 0) return;
    if(l == N){
      k++;
      if(k == K){
        res = string(path.begin(),path.end());
        transform(res.begin(),res.end(),res.begin(),
                  bind2nd(plus<char>(), '0'));
      }
      return;
    }
    for(int i = 2; i < 10; i++){
      int m = 1;
      int siz = path.size();
      for(int j = 0; j < siz; j++){
        if(i == path[j]) goto fail;
      }
      path.push_back(i);
      for(int j = siz; j >= 0; j--){
        m *= path[j];
        if(exists.find(m) != exists.end()){
          path.pop_back();
          goto fail;
        }
      }
      m = 1;
      for(int j = siz; j >= 0; j--){
        m *= path[j];
        exists.insert(m);
      }
      rec(l+1,path,exists);
      m = 1;
      for(int j = siz; j >= 0; j--){
        m *= path[j];
        exists.erase(exists.find(m));
      }
      path.pop_back();
    fail:;
    }
  }

public:
  string getKth( int _N, int _K ) {
    N = _N;
    K = _K;
    k = 0;
    res = "";
    if(N > 8) return "";
    if(N == 1){
      if(K > 10) return "";
      return string(1,K-1 + '0');
    }
    set<LLI> s;
    vector<int> path;
    rec(0,path,s);
    return res;
  }
};

SRM 465 Div1 Medium GreenWarfare 23:18  [http://www.topcoder.com/stat?c=problem_statement&pm=10792&rd=14182:title=SRM 465 Div1 Medium GreenWarfare] - shnyaの参戦記録 を含むブックマーク はてなブックマーク -  [http://www.topcoder.com/stat?c=problem_statement&pm=10792&rd=14182:title=SRM 465 Div1 Medium GreenWarfare] - shnyaの参戦記録

前回解いてなかった最大フローの問題。

プログラミングコンテストチャレンジブック読んで、最大フローを理解しながらちゃんと書いてみた。かなり高速に計算できて、すげーとか思った。

これでライブラリが1つ増えた。

class MaxFlow {
  struct edge {
    int to,cap,rev;
    edge(int t, int c, int r) : to(t),cap(c),rev(r) {}
  };

  int dfs(int s, int t, int f){
    if(s == t) return f;
    used[s] = true;
    int n = G[s].size();
    for(int i = 0; i < n; i++){
      edge &e = G[s][i];
      if(!used[e.to] && e.cap > 0){
        int d = dfs(e.to, t, min(f, e.cap));
        if(d > 0){
          e.cap -= d;
          G[e.to][e.rev].cap += d;
          return d;
        }
      }
    }
    return 0;
  }
public:

  MaxFlow(int n, int snum = 1, int tnum = 1){
    G.resize(n+snum+tnum+1); used.resize(n+snum+tnum+1);
    for(int i = 1; i <= snum; i++)
      sources.push_back(n+i);
    for(int i = 1; i <= tnum; i++)
      targets.push_back(n+snum+i);
  }

  void add(int from , int to, int cap){
    G[from].push_back(edge(to,cap,G[to].size()));
    G[to].push_back(edge(from,0,G[from].size()-1));
  }

  const vector<int> &source() const { return sources; }
  const vector<int> &target() const { return targets; }

  int flow(){
    int sum = 0;
    for(size_t i = 0; i < sources.size(); i++){
      for(size_t j = 0; j < targets.size(); j++){
        int s = sources[i];
        int t = targets[j];
        while(1){
          fill(used.begin(),used.end(),0);
          int f = dfs(s,t,INF);
          if(f == 0) break;
          sum += f;
        }
      }
    }
    return sum;
  }
  const static int INF = (int)1E+10;
private:
  vector<vector<edge> > G;
  vector<bool> used;
  vector<int> sources;
  vector<int> targets;
};

class GreenWarfare {
public:
  int minimumEnergyCost( vector <int> canonX, vector <int> canonY, vector <int> baseX, vector <int> baseY, vector <int> plantX, vector <int> plantY, int energySupplyRadius ) {
    MaxFlow G(baseX.size() + plantX.size());
    int basesiz = baseX.size();
    int plsiz = plantX.size();
    int cansiz = canonX.size();

    for(int i = 0; i < basesiz; i++){
      int minn = numeric_limits<int>::max();
      for(int j = 0; j < cansiz; j++){
        minn = min(minn, ((canonX[j] - baseX[i]) * (canonX[j] - baseX[i])
                          + (canonY[j] - baseY[i]) * (canonY[j] - baseY[i])));
      }
      G.add(G.source()[0],i,minn);
    }

    for(int i = 0; i < plsiz; i++){
      int minn = numeric_limits<int>::max();
      for(int j = 0; j < cansiz; j++){
        minn = min(minn, ((canonX[j] - plantX[i]) * (canonX[j] - plantX[i])
                          + (canonY[j] - plantY[i]) * (canonY[j] - plantY[i])));
      }
      G.add(basesiz+i,G.target()[0],minn);
    }

    for(int i = 0; i < basesiz; i++){
      for(int j = 0; j < plsiz; j++){
        if(sqrt((plantX[j] - baseX[i]) * (plantX[j] - baseX[i])
                + (plantY[j] - baseY[i]) * (plantY[j] - baseY[i]))
           < energySupplyRadius + EPS){
          G.add(i,basesiz+j,MaxFlow::INF);
        }
      }
    }
    return G.flow();
  }
};

SRM 271 Div2 Easy CheckFunction 23:43  [http://www.topcoder.com/stat?c=problem_statement&pm=4788&rd=8068:title=SRM 271 Div2 Easy CheckFunction] - shnyaの参戦記録 を含むブックマーク はてなブックマーク -  [http://www.topcoder.com/stat?c=problem_statement&pm=4788&rd=8068:title=SRM 271 Div2 Easy CheckFunction] - shnyaの参戦記録

"032"といった文字列をデジタル数字で表現した時に、何本の線が必要かを数える問題。

ただカウントするだけ。

class CheckFunction
{
public:
  int newFunction(string code)
  {
    vector<int> v(10);
    v[0] = 6;
    v[1] = 2;
    v[2] = 5;
    v[3] = 5;
    v[4] = 4;
    v[5] = 5;
    v[6] = 6;
    v[7] = 3;
    v[8] = 7;
    v[9] = 6;
    int n = code.size();
    int res = 0;
    for(int i = 0; i < n; i++){
      res += v[code[i] - '0'];
    }
    return res;
  }
};

SRM 271 Div2 Medium BlackWhitePlane 23:43  [http://www.topcoder.com/stat?c=problem_statement&pm=4497&rd=8068:title=SRM 271 Div2 Medium BlackWhitePlane] - shnyaの参戦記録 を含むブックマーク はてなブックマーク -  [http://www.topcoder.com/stat?c=problem_statement&pm=4497&rd=8068:title=SRM 271 Div2 Medium BlackWhitePlane] - shnyaの参戦記録

N個の円があり、いくつかの円は、さらに大きな円の内部に完全に内包されている。

最初の背景は黒で、その上にある円は白で塗られる。円の中にさらに円がふくまれている場合は、背景が白の場合は黒、背景が黒の場合は白で塗っていく。

白で塗られた面積を答えよ。


深さは最大2段だとばかり思っていて、System Test Failed。。。

 class BlackWhitePlane
 { 
   typedef pair<int,pair<int,int> > circle;

   long double dist(int x, int y){
     return sqrt(x * x + y * y);
   }

 public: 
   double area(vector <string> circles) 
   { 
     vector<circle> v;
     int n = circles.size();
     for(int i = 0; i < n; i++){
       int x,y,r;
       sscanf(circles[i].c_str(), "%d %d %d", &x, &y, &r);
       v.push_back(make_pair(r,make_pair(x,y)));
     }
     sort(v.begin(),v.end(),greater<circle>());
     vector<int> info(n,-1);
     for(int i = 0; i < n; i++){
       for(int j = i+1; j < n; j++){
         if(dist(v[j].second.first - v[i].second.first, 
         v[j].second.second - v[i].second.second) < v[i].first + EPS){
           if(info[i] >= 0){
             info[j] = info[i] + 1;
           }else{
             info[j] = 1;
           }
         }
       }
     }
     long double res = 0.0;
     for(int i = 0; i < n; i++){
       if(info[i] < 0 || info[i] % 2 == 0){
         res += (v[i].first * v[i].first) * PI;
       }else{
         res -= (v[i].first * v[i].first) * PI;
       }
     }

     return res;
   } 
};