Hatena::Grouptopcoder

cafelier@SRM

cafelier のSRM参加記録です。コンテスト中に考えてたことを執拗に全部書き残すとどうなるだろうかという試み本番中にこういうコードが書きたかったなあ、という後で書いた反省コードを書き残す試み

スパムが来たのでしばらくコメント欄をはてなユーザ限定にしています、すみません、

2012-10-20

SRM558 275

| 00:57 | はてなブックマーク -  SRM558 275 - cafelier@SRM

重ね塗りを考慮するのややこしいので、重ね塗りを考えないのが多分一番良い解き方だと思う。

「長さピッタリ L のスタンプ。1回押すのに pushCost。色があってれば重ね塗りしても良い」の代わりに「長さ L 以上の可変長スタンプ。長さ W にして1回押すのに ((W+L-1)/L)*pushCost。重ね塗り禁止」と考える。

(W+L-1)/L というのは、(L,2L]なら2回、(2L,3L]なら3回、…というあれです。

class Stamp { public:
   int getMinimumCost(string desiredColor, int stampCost, int pushCost)
   {
      const int N = desiredColor.size();

      int best = 0x7fffffff;
      for(int L=1; L<=N; ++L) {
         vector<int> dp(N+1, 999);
         dp[0] = 0;
         for(int e=1; e<=N; ++e) {
            // desiredColor[0,e) を塗るのに何回で塗れるか。
            set<char> colors;
            for(int s=e-1; s>=0; --s) {
               if(desiredColor[s] != '*')
                  colors.insert(desiredColor[s]);
               if(colors.size()<=1 && e-s>=L) {
                  int nPush = (e-s+L-1)/L;
                  // desiredColor[0,s) を巧く塗って desiredColor[s,e) を可変スタンプ1発で塗る
                  dp[e] = min(dp[e], dp[s]+nPush);
               }
            }
         }
         best = min(best, L*stampCost + dp[N]*pushCost);
      }
      return best;
   }
};
トラックバック - http://topcoder.g.hatena.ne.jp/cafelier/20121020

2012-02-25

Codeforces 109 Div1 C

| 13:58 | はてなブックマーク - Codeforces 109 Div1 C - cafelier@SRM

  • ハッシュしなくても漸近計算量は O(N log N) ではあると思うんですよ、と思って
  • 2970ms! (不毛な努力)
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdio>
using namespace std;
typedef long long LL;

int main()
{
   // Input ------------------------------------------------------
   int V,E; scanf("%d%d",&V,&E);

   vector<pair<int,int>> edges(E); // edges
   vector<vector<int>>   ne(V);    // neighborhood of each node
   int                   deg0 = V; // number of degree-0 nodes

   for(auto& e : edges)
   {
      int a,b; scanf("%d%d",&a,&b); --a, --b;
      e = make_pair(a,b);
      if(ne[a].empty()) --deg0;
      if(ne[b].empty()) --deg0;
      ne[a].push_back(b);
      ne[b].push_back(a);
   }
   for(auto& n : ne)
      sort(n.begin(), n.end());

   // Solve -------------------------------------------------------
   LL total = 0;

   auto sorted_ne = ne;
   sort(sorted_ne.begin(), sorted_ne.end());
   for(int i=0; i<V; ) {
      int k=i+1;
      while( k<V && sorted_ne[i]==sorted_ne[k] )
         ++k;
      total += LL(k-i)*(k-i-1)/2;
      i = k;
   }

   for(int i=0; i<V; ++i)
      ne[i].insert(lower_bound(ne[i].begin(), ne[i].end(), i), i);

   if( V-deg0 < 10000 ) { // may be dense
      sort(ne.begin(), ne.end());
      for(int i=0; i<V; ) {
         int k=i+1;
         while( k<V && ne[i]==ne[k] )
            ++k;
         total += LL(k-i)*(k-i-1)/2;
         i = k;
      }
   }
   else // sparse
      for(auto e : edges)
         if( ne[e.first] == ne[e.second] )
            ++total;

   // Output -------------------------------------------------------
   cout << total << endl;
}
トラックバック - http://topcoder.g.hatena.ne.jp/cafelier/20120225

2012-02-18

Codeforces 107 Div1 C

| 12:12 | はてなブックマーク - Codeforces 107 Div1 C - cafelier@SRM

  • 最終的には、書いてみるとすごく普通だった。
  • セグメント木、区間に対する効率の良いupdateが可能なパターン(まとめて正負反転とか)まで込みでどうライブラリ化すると綺麗になるか考えきれないでいる(今回の問題には関係ないですが)
template<typename Node>
class SegmentTree
{
public:
   template<typename Seq>
   SegmentTree(const Seq& s) {
      int N = 1;
      while( N < s.size() )
         N <<= 1;

      tree.resize(tree.size()+1); tree.back().resize(N);
      for(int i=0; i<N; ++i)
         tree.back()[i] = i<s.size() ? Node::One(s[i]) : Node::Zero();

      while(N>>=1) {
         tree.resize(tree.size()+1); tree.back().resize(N);
         for(int i=0; i<N; ++i)
            CalcMidNode(tree.size()-1, i);
      }
   }

   Node Query(int s, int e) { // compute h( seq[s,e) ) : O(log n)
      return QueryRec(s, e, tree.size()-1, 0, tree[0].size());
   }
/*
   template<typename Value>
   void Set(int s, int e, Value v) { // seq[s,e):=v : O(log n・|e-s|)
      SetRec(s, e, Node::One(v), tree.size()-1, 0, tree[0].size());
   }
*/
private:
   void CalcMidNode(int lv, int idx)
   {
      tree[lv][idx] = Node::Concat(tree[lv-1][idx*2], tree[lv-1][idx*2+1]);
   }

   Node QueryRec(int s, int e, int lv, int idx, int stride)
   {
      const int myL = stride*idx;
      const int myR = stride*(idx+1);
      if( e<=myL || myR<=s )
         return Node::Zero();
      if( s<=myL && myR<=e )
         return tree[lv][idx];
      return Node::Concat(QueryRec(s,e,lv-1,idx*2,stride/2),
                          QueryRec(s,e,lv-1,idx*2+1,stride/2));
   }
/*
   void SetRec(int s, int e, const Node& n, int lv, int idx, int stride)
   {
      const int myL = stride*idx;
      const int myR = stride*(idx+1);
      if( e<=myL || myR<=s )
         return;
      if( stride == 1 ) {
         tree[lv][idx] = n;
      } else {
         SetRec(s,e,n,lv-1,idx*2,stride/2);
         SetRec(s,e,n,lv-1,idx*2+1,stride/2);
         CalcMidNode(lv, idx);
      }
   }
*/
   vector< vector<Node> > tree;
};

// Any homomorphism from the original array structure can be used as segtree nodes.
struct Node
{
   double sum;
   double maxLeft;
   double maxRight;
   double maxSum;
   static Node Zero()
   {
      Node c = {0, 0, 0, 0};
      return c;
   }
   static Node One(double v)
   {
      Node c = {v, max(0.0,v), max(0.0,v), max(0.0,v)};
      return c;
   }
   static Node Concat(const Node& l, const Node& r)
   {
      Node c = {
         l.sum + r.sum,
         max(l.maxLeft, l.sum+r.maxLeft),
         max(l.maxRight+r.sum, r.maxRight),
         max(max(l.maxSum, r.maxSum), l.maxRight+r.maxLeft),
      };
      return c;
   }
};

//---------------------------------------------------------

double solve(
   const vector<int>& X,
   const vector<int>& P,
   const vector< pair<int,int> >& AB,
   int C
){
   vector<double> gain(X.size()-1);
   for(int i=0; i<gain.size(); ++i)
      gain[i] = (X[i+1]-X[i])/2.0 - C/100.0*P[i];

   SegmentTree<Node> st(gain);

   double total = 0.0;
   for(int i=0; i<AB.size(); ++i)
      total += st.Query(AB[i].first, AB[i].second).maxSum;
   return total;
}

int main()
{
   for(int N,M,C; cin>>N>>M>>C; )
   {
      vector<int> X(N);
      for(int i=0; i<N; ++i) cin >> X[i];
      vector<int> P(N-1);
      for(int i=0; i<N-1; ++i) cin >> P[i];
      vector< pair<int,int> > AB(M);
      for(int i=0; i<M; ++i) {cin >> AB[i].first >> AB[i].second; AB[i].first--; AB[i].second--;}

      cout << setiosflags(ios::fixed) << setprecision(9) << solve(X, P, AB, C) << endl;
   }
}
トラックバック - http://topcoder.g.hatena.ne.jp/cafelier/20120218

2012-02-05

Facebook Hacker Cup 2012 R2 Road Removal

| 21:49 | はてなブックマーク -  Facebook Hacker Cup 2012 R2 Road Removal - cafelier@SRM

今回はUnionFind祭りだった。

  • 長いので重要な都市を「黒」と重要でない都市を「白」とする。
struct UnionFind
{
   vector<int> uf, sz;
   int nc;

   UnionFind(int N): uf(N), sz(N,1), nc(N)
      { for(int i=0; i<N; ++i) uf[i] = i; }
   int size()
      { return nc; }
   int Find(int a)
      { return uf[a]==a ? a : uf[a]=Find(uf[a]); }
   bool Union(int a, int b)
      {
         a = Find(a);
         b = Find(b);
         if( a != b )
         {
            if( sz[a] >= sz[b] ) swap(a, b);
            uf[a] = b;
            sz[b] += sz[a];
            --nc;
         }
         return (a!=b);
      }
};

typedef int vert;
typedef tuple<vert,vert> edge;

int solve(const vector<edge>& edges, int N, int K)
{
   int removed = 0;

   // とりあえず白白辺を全部結ぶ
   UnionFind uf(N);
   for(edge e : edges) {
      vert a = get<0>(e);
      vert b = get<1>(e);
      if( a >= K && b >= K )
         uf.Union(a,b);
   }

   // 他の辺はサイクル作らないように結ぶ
   for(edge e : edges) {
      vert a = get<0>(e);
      vert b = get<1>(e);
      if( a < K || b < K )
         if( !uf.Union(a,b) )
            ++removed;
   }
   return removed;
}

int main()
{
   int T; cin >> T;
   for(int C=1; C<=T; ++C)
   {
      int N, M, K; cin >> N >> M >> K;
      vector<edge> edges;
      for(int i=0; i<M; ++i) {
         int a,b; cin >> a >> b;
         edges.emplace_back(a, b);
      }
      cout << "Case #" << C << ": " << solve(edges, N, K) << endl;
   }
}
  • 仮定1: 白白辺はgreedyに全部結んじゃって良い
    • 白白辺 e を含まない最適解が存在したとする
    • その解に e を足すと(最適性より)黒ノードを含むサイクルができる
    • そのサイクル中の白黒辺を消して代わりに e を入れてもサイクルなしなので(※)これも最適解になる
      • ※: eを足した結果できるサイクルは1つだけ。2つ一気にできたとすると絵を描いてみると元々サイクルがあったことになってしまうことがわかる。
  • 仮定2: 白白辺で結んだ同値類を1点とみなして、あとは普通に最小全域森を作るのが最適
    • 森なら新しくサイクル作ってないので条件は満たす。
    • それより枝を多く入れると必ずサイクルができてしまう。もう白白辺は存在しないので、この段階でできてしまったサイクルは必ず黒ノードを含むから失格。
    • 故に最小全域森が最適
トラックバック - http://topcoder.g.hatena.ne.jp/cafelier/20120205

2011-12-24

SRM526.5 250

| 13:56 | はてなブックマーク -  SRM526.5 250 - cafelier@SRM

  • 同じ部屋のxiaowuc1さんの解がかっこよかった
class MagicCandy { public:
   int whichOne(int n)
   {
      // r が最後まで生き残るかどうか…?
      int r = n;
      while( n > 1 ) {
         const int sn = int(sqrt(n));
         // sn*sn == n だったら平方数になってるので死んでる
         // r-1 は生きてるはずなので引き続きそれの生き残りチェック
         r -= (sn*sn == n);
         n -= sn;
      }
      return r;
   }
};
  • n = k*k+1 の形だったら2歩で k*k+1-k = (k-1)*(k-1)+k → (k-1)*(k-1)+1
  • と進むので、一度平方数+1になったら最後まで死なないので、rがそこまで生きてたらr-1も生きてる
  • ほげー

HiHi2011/12/24 14:24同じ解答だった。

cafeliercafelier2011/12/24 20:11cool.

トラックバック - http://topcoder.g.hatena.ne.jp/cafelier/20111224

presented by cafelier/k.inaba under CC0