Hatena::Grouptopcoder

cafelier@SRM

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

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

 | 

2010-04-20

SRM468

| 00:08 | はてなブックマーク -  SRM468 - cafelier@SRM

SRM468 の成績・ソース (要ログイン) : AC/MLE/- : この過ちは二度と繰り返さぬ…

500開く

  • 『都市0番から都市N番まで一直線に順番に都市がつながってます。0からNまで行きたいです。i~i+1の間は陸路だとrt[i]、飛行機で飛ぶとft[i]時間がかかります。離着陸すると危険なので、離陸回数をK回以下に抑えて最短時間で目的地まで行くには?』
    • 要は 0~1 と 1~2 を両方飛行機で行くと 0~2 の一繋がりのフライトとしてよいので離陸回数は1回みたいな
    • N≦40万
    • K≦40
    • 時間は32bitにおさまる程度。答えは64bitになるかも

  • 常識的に考えて0~Nまで飛んでいく方が速いだろ…なんだこの問題設定……

  • とそれはさておき、
  • すごくDPに見える。
  • n番目まで、k回の離陸で行く最短時間を dp[n][k] とする
    • 答えは dp[N][0] ~ dp[N][K] の最小値
    • dp[n][k] = 以下の最小値
      • 陸路でnに到着する場合 : dp[n-1][k] + rt[n-1]
      • 0から飛んでnに到着する場合 : dp[0][k-1] + ft[0]+ft[1]+...+ft[n-1]
      • 1から飛んでnに到着する場合 : dp[1][k-1] + ft[1]+...+ft[n-1]
      • ...
      • n-1から飛んでnに到着する場合 : dp[n-1][k-1] + ft[n-1]

  • ちょっと待ってこれは O(N^2 K) かかるからダメだ
  • O(NK) なら1600万だから想定解だろうなあ
  • つまり、do[n][k] のそれぞれの値を定数時間で埋めないといけない
  • さっきのやつは
  • どう考えてもほとんど同じ ...+ft[n-1] を毎回やってるのは無駄だ…
  • えーと、
    • dp[n-1][k-1] が「どっかから飛んでnに到着する場合」だったとすると、
    • それにさらにft[k-1]を足すと、「(n-1)より前のどっかから飛んでnに到着する場合」の最小値が当然出る。
    • 「n-1から飛んでnに到着する場合」は別途計算すればよろし

  • つまり、dp[n][k] を求める時の場合分けだけじゃなくて、
  • dpの表自体を陸路で着いた場合と飛んで着いた場合に分けて管理した方が表の更新が速い。
  • dp[n][k][f] = 都市n番に、k回の離陸で、(f=0 陸路で到着 : f=1 空路で到着)
  • とする。
    • 陸路で到着する場合は、1個前の都市に最短で着いてから歩く
    • dp[n][k][0] = min(dp[n-1][k][0], dp[n-1][k][1]) + rt[n-1]
    • 空路で到着する場合は、1個前の都市に歩いて着いてた場合にのみkが変わる
    • dp[n][k][1] = min(dp[n-1][k-1][0], dp[n-1][k][1]) + ft[n-1];

  • できた。
  • この二つの代入文のまわりに n と k のループを書いて
  • n-1 と k-1 を見ているところは n==0, k==0 だと溢れるので、そこだけ分岐して特別処理を埋める
  • できた。

  • サンプル通った。
  • 最大ケースの実行時間も手元で700msec程度。問題ない。Submit!
  • あれ、360点台。結構時間喰ってしまった…。

250開く

  • スコア表見ると今日も苦戦しているひとが多い
  • ってか、問題文ながっ!
  • 『とある携帯電話の入力方式で文章を入力しています。キー入力列が与えられるので、どんな文章が入力されたか求めてね。』
    • 方式の詳細は以下の通り
    • 入力: part = {"abc", "def", ...} みたいな9要素の配列
    • "1" を押したら part[1] の文字のどれかが入る。2~9 も同様
    • "0" を押したら半角スペースが入る
    • これだけだと1~9を押したときに何を書いたのか決まらないので、単語ごとに、IMEの変換みたいにして決める
      • たとえば "123#" と入力すると、part[1]+part[2]+part[3] の形の文字列で、辞書順1番目(0-originで)のもの
      • たとえば "123##" と入力すると、part[1]+part[2]+part[3] の形の文字列で、辞書順2番目のもの
      • ...
      • 以下同様。# が多すぎるので、* を入れると # 5個と同じ効果
    • 単語は必ずスペースで区切られてるので
      • "450" だと part[4]+part[5] のうち辞書順先頭のもの+" "
      • みたいな
    • 入力: dict = 50要素以下の文字列配列。これが辞書
    • 出力の長さはたかだか1000文字

  • ええと、長いけど、辞書も小さいし、出力も小さいし、地道に実装するだけだよね。
    • 単語 [1-9]+[#*]* 毎にくぎる
    • [#*]* の部分を数値cに直す
    • 辞書を辞書順にソートしておいて、
      • [1-9]+ の部分にマッチするものを先頭から順に探して、
      • c番目を返す

  • できた
  • よしサンプルも通った。
  • まあ特にコーナーケースもないよなあ…
    • ソートされてない辞書もサンプルに入ってるし
  • submit!

1000開く

  • 『N階建ての建物があります。隣り合う階を何本かのエスカレータが結んでます。ついでに、1階とN階の直通エスカレータもあります。警備員はエスカレータのどっちかの端点に1人配置できます。でも両端に置くとお客様が怖がるのでダメです。できるだけ多く警備員を配置すると何人置ける?』
    • 2本のエスカレータが端点を共有していたりする
      • 入力は、「C階のA番目のエスカレータホールとC+1階のB番目のエスカレータホールが繋がってます」を意味する(A,B,C)の三つ組みのリストで与えられる
    • 10≦N≦50
    • エスカレータホールの数は全部で100
    • エスカレータだけをたどってどこからどこへも行けるようになってる

  • テストケースは…
  • 最小ケース 10≦N ?なんだこれ。作るのめんどくさいぞ…
    • 10以上じゃないと問題として意味をなさなかったりするんだろうか。
    • 先に少し解き方考えてみないとわからないなー。
    • (※ ここでもっと深く考えておくべきだった…orz

  • まあ、エスカレータホールをnode、エスカレータをedgeとしてグラフを書いてみる。
3F ・ ・  ・
    \|   \
2F   ・ ・ |
    /|/  | ←1Fと最上階を繋ぐスーパーエスカレータ
1F ・ ・---+
  • これの…なんだろう。
  • えーと、できるだけ多く点数を選んで、
  • しかも、一つの辺の両端を同時に選んではいけない
  • 「最大独立点集合」だ!
  • NP-hard だ!

  • いやしかし、この「何階建て」グラフは明らかに特殊なグラフだ。
  • というかほとんど二部グラフだ
  • スーパーエスカレータのことを一旦忘れると
  • あたりまえだけど
    • 偶数階のエスカレータホールは奇数階としか繋がってない
    • 奇数階は偶数階としか
  • まさに二部グラフ
  • ついでに、階数が偶数なら、上と下を直結するエスカレータがあっても↑↑の関係は成り立つので、やっぱり二部グラフ

  • 二部グラフなら、最大独立点集合は求まる
    • 頂点の数v - 最大マッチングのサイズm
  • だ。
  • だったよね。
  • ええとググる。うむ確かにそう書いてあるページがひっかかる。
  • 一応証明しとこう
    • この値より大きい独立点集合nがあったとする。
      • v-m < n
      • すると、独立点集合に含まれない頂点の個数はv-n<m個だから、
      • 最大マッチングに関与している2m個の頂点のうち、<m個しか独立点集合に入ってない点がない
      • 逆にいうとm+1個以上独立点集合に入ってる。
      • でもそれはおかしい。マッチングということは辺で結ばれているはずなので。ダメ。矛盾。
    • 逆に、最低でも v-m 個の独立点はとれることを示す
      • 二部グラフの場合「最大マッチング=最小点カバー」である
      • 要は、最小点カバーなので、m個の頂点を抑えれば、他のv-m個の頂点は全部繋がっていないようにできる
      • ということで、そのv-m個がまさに独立点集合

  • よし

  • よくない。Nが奇数のときどうするんだ。

  • うーむ。二部グラフではないけど、とても近いんだよなー。
  • N階建てだったら、N個のnode集合にわけられて、トーラス状につながってる感じ
  • N部グラフと名付けよう。
  • こういう場合も、二部グラフと同じで「最大マッチング=最小点カバー」が成り立ったりするんじゃないか?
  • 考える…
  • 考える…
  • 考える…
  • そもそも二部グラフでこの双対性が成り立つのってなんでだっけ…
  • ぬぬぬぬぬ…
  • わからない

  • そもそも「グラフが連結である」という制約が入っているけど、
  • これはなんで必要なんだろう。さっきの解法だと使っていないはずだ。
  • うううむ。
  • 考える…
  • 考える…
  • 考える…
  • わからない

  • 「N部グラフ」じゃなくて、「2部グラフなんだけど片側がちょっと微妙に内部でつながってるグラフ」と考えて2部グラフのアルゴリズムを応用
    • 「微妙に繋がっている」部分を同一視して単一頂点に潰して考えるとか。
    • いや、それはダメだなあ。すぐ反例が思いつく
  • わからない
  • タイムアップ

撃墜タイム

  • 500はシンプルなDPだし
  • 250は実装問題でサンプルも十分だし
  • 落としどころがわからないなあ。

  • と思ってたら自分の500がいきなり落ちた
  • ええー!
  • 落とした人のソースと自分のを見比べる。
  • ええとDPなのは同じで…
  • そうか、dp[n-1] しかみないから、N*K*2 の表じゃなくて、2*K*2の表でいいのか、賢い。

  • ううむ、でも、それ以外に違いはないぞ。合ってると思うんだけど…
  • って、これか、違いは!!
  • N*K*2*sizeof(long long)はSRMのメモリ制限64MBを溢れている!
  • うわーそれは気づかなかった
  • 手元だけじゃなくて最大ケースはarenaでテストするべきなのか…めんどうだ…

  • いや落ち込んでいる場合ではない、同じミスをしている人がいるはずだ。
  • 探さねば…
  • 幸い、ICPC でチームを組んでいたので思考の方向をある程度把握できている mayahjp が同じ部屋にいます
  • やつはこんなDPでメモリをケチった実装などしないはずだ!open!
  • よし N*K の配列取ってる!
  • あれ?でも? N*K*2 じゃないのか。
  • へー
  • ほー
  • それでもうまく書けるのかー。
  • ええと最悪ケースはなんだっけ N=10万 と K=40だっけ。
    • 10万×40×8 は … 32MB!足りてる!
    • さらに×2すると64MB行ってしまう。絶妙なバランスだ。無念。
    • (※ …と思ったけど実際には最大はN=40万でした。普通に落とせたのに…!!)

感想

  • 500はこれは仕方ない。
  • 次から同じことをやらないように対策すればよい。
  • というわけでDP用テンプレコードを書き換えてサイズチェックのassertを追加
    • たぶんDP以外で問題になることはないはず…
      • 「速度的には解けちゃうけどメモリ的に解けない」時だけ問題なので
      • 64MBサイズのグラフとか作ったらだいたいのグラフアルゴリズムでしんどそうだし
      • そもそもそれでダメな時にメモリを簡単に減らせるのはDPで1個前だけ見れば済む時くらいだろう
      • しかし一応64MBは気にするようにしよう…

  • 1000はwataさんの"N≧10が怪しすぎてすぐ気付けた"を見てやっと気づけた
    • そうだ、確かに言われてみれば怪しすぎる
    • 10階建て以上で、全部で100個までしかエスカレータホールないので、一番少ない階を見れば、10個以下
    • なので、そこへの警備員配置を2^10通り全部試すと、
    • 残りは二部グラフなので解ける
  • で、いいと思う。あとで解いてみる。
  • 500よりこっちが悔しいなあ。次頑張ろう。次。

SRM468 500

| 00:08 | はてなブックマーク -  SRM468 500 - cafelier@SRM

DPテンプレート改を投入

typedef long long LL;

template<typename T>
struct DP3x
{
   int N1, N2, N3;
   vector<T> data;
   DP3x(int, int N2, int N3, const T& t = T())
      : N1(2), N2(N2), N3(N3), data(N1*N2*N3, t) { assert(data.size()*sizeof(T) < (1<<26)); }
   T& operator()(int i1, int i2, int i3)
      { i1&=1; return data[ ((i1*N2)+i2)*N3+i3 ]; }
   void swap(DP3x& rhs)
      { data.swap(rhs.data); }
};

static const LL inf = (1LL << 60);

class RoadOrFlightHard { public:
   long long minTime(int N, int roadFirst, int roadProd, int roadAdd, int roadMod,
                     int flightFirst, int flightProd, int flightAdd, int flightMod, int K) 
   {
      vector<LL> rt(N), ft(N);
      {
         rt[0] = roadFirst % roadMod;
         for(int i=1; i<N; ++i)
            rt[i] = (rt[i-1]*roadProd + roadAdd) % roadMod;

         ft[0] = flightFirst % flightMod;
         for(int i=1; i<N; ++i)
            ft[i] = (ft[i-1]*flightProd + flightAdd) % flightMod;
      }

      DP3x<LL> dp(N+1, K+1, 2);
      for(int n=0; n<=N; ++n)
      for(int k=0; k<=K; ++k)
         if( n == 0 ) {
            dp(n,k,0) = 0;
            dp(n,k,1) = inf; // ※追記:この行抜けてた。酷い。MLE以前の問題だ…
         }
         else {
            dp(n,k,0) = min(dp(n-1,k,0), dp(n-1,k,1)) + rt[n-1];
            if( k == 0 )
               dp(n,k,1) = inf;
            else
               dp(n,k,1) = min(dp(n-1,k,1), dp(n-1,k-1,0)) + ft[n-1];
         }

      LL ans = inf;
      for(int k=0; k<=K; ++k)
         ans = min(ans, min(dp(N,k,0), dp(N,k,1)));
      return ans;
   }
};

SRM468 1000

| 12:33 | はてなブックマーク -  SRM468 1000 - cafelier@SRM

上に書いた方針で。結構長くなってしまった。

typedef int           vert;
typedef vert          edge;
typedef vector<edge>  edges;
typedef vector<edges> graph;

bool augment( graph& G, int v, vector<vert>& matchTo, bool visited[] )
{
   for(int i=0; i<G[v].size(); ++i) {
      vert u = G[v][i];
      if( visited[u] ) continue;
      visited[u] = true;

      if( matchTo[u]<0 || augment(G, matchTo[u], matchTo, visited) )
         { matchTo[v]=u, matchTo[u]=v; return true; }
   }
   return false;
}

template<int NV>
int biMatch( graph& G, int L ) // [0,L):left, [L,?):right
{
   vector<vert> matchTo(G.size(), -1);
   int ans = 0;
   for(vert v=0; v<L; ++v) {
      bool visited[NV] = {};
      if( augment(G, v, matchTo, visited) )
         ++ans;
   }
   return ans;
}

int bitcnt(LL x)
{
   int c = 0;
   for(; x; x>>=1)
      c += x&1;
   return c;
}

class MallSecurity { public:
   pair<graph, int> generateBipartiteGraph(
      const vector<int>& As, const vector<int>& Bs, const vector<int>& Cs, const vector<int>& Ds,
      const vector<int>& Ks, int msf, int mask )
   {
      // construct a bipartite graph representation, in which
      //   - "even"-floor stations go to the left
      //   - "odd"-floor stations go to the right
      // here floor number is normalized by rotating the msf-th floor to zero
      #define LR(f) (((f)>msf ? (f)-msf : Ks.size()-msf+(f))%2)

      // assign interger-ID for each "choosable" station, i.e.,
      // a station which is not at msf and is not connected to a 'mask'ed station on msf
      map<pair<int,int>,int> ID;
      int nextID[2] = {0,0}; // use different sets of IDs for even/odd floors
      {
         for(int f=0; f<Ks.size(); ++f) if( f != msf )
         for(int i=0; i<Ks[f]; ++i)
         {
            bool can_use = true;
            for(int j=0; j<As.size(); ++j)
               if( Cs[j]==f && As[j]==i && Ds[j]==msf && (mask & 1<<Bs[j])
                || Ds[j]==f && Bs[j]==i && Cs[j]==msf && (mask & 1<<As[j]) )
                can_use = false;
            if( can_use )
               ID[make_pair(f,i)] = nextID[LR(f)]++;
         }
      }

      // then create the graph
      graph G( nextID[0] + nextID[1] );
      for(int j=0; j<As.size(); ++j)
      {
         pair<int,int> p(Cs[j], As[j]);
         pair<int,int> q(Ds[j], Bs[j]);
         if( ID.count(p) && ID.count(q) )
         {
            int pid = ID[p] + (LR(Cs[j]) ? nextID[0] : 0);
            int qid = ID[q] + (LR(Ds[j]) ? nextID[0] : 0);
            G[pid].push_back(qid);
            G[qid].push_back(pid);
         }
      }
      return make_pair(G, nextID[0]);
   }

   int maxGuards(int N, vector <string> escDescription) 
   {
      // parse the input
      vector<int> As, Bs, Cs, Ds, Ks(N);
      {
         stringstream sin;
         copy( escDescription.begin(), escDescription.end(), ostream_iterator<string>(sin,"") );

         for(int A,B,C; sin>>A>>B>>C; )
         {
            {char comma; sin>>comma;}
            --A, --B, --C; int D=(C+1)%N; // to 0-orign
            As.push_back(A);
            Bs.push_back(B);
            Cs.push_back(C);
            Ds.push_back(D);
            Ks[C] = max(Ks[C], A+1);
            Ks[D] = max(Ks[D], B+1);
         }
      }

      // the most simple floor, where the number Ks[msf] of stations is the least
      int msf = min_element(Ks.begin(), Ks.end()) - Ks.begin();

      // try all possibilities at the msf-th floor
      size_t answer = 0;
      for(int mask=0; mask<(1<<Ks[msf]); ++mask)
      {
         // then the rest of the part becomes a bipartite graph
         pair<graph, int> G = generateBipartiteGraph(As,Bs,Cs,Ds,Ks,msf,mask);

         // |MaxIndenepdentSet| == |V|-|MinCover| =(for bipartite graphs)= |V|-|MaxMatch|
         answer = max(answer, G.first.size() - biMatch<100>(G.first,G.second) + bitcnt(mask));
      }
      return answer;
   }
};

cafeliercafelier2010/04/21 09:47証明こんな面倒くさくする必要なかったなー
・点被覆(=どの辺もどっちかの頂点はカバーされてる)の補集合は独立点集合(=どの辺もどっちかの頂点はカバーされてない)
・独立点集合の補集合は点被覆
・よって、 最小点被覆←補集合→最大独立点集合
・二部グラフの場合は、|最小点被覆| = |最大マッチング|
・よって二部グラフの場合は、|最大独立点集合|=|V|-|最大マッチング|

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

presented by cafelier/k.inaba under CC0