cafelier@SRM

SRM476

SRM | 15:20 |

SRM476 の成績・ソース (要ログイン) : AC/-/- : 確実に回避できなきゃいけないタイプの穴から這い出せなかった

250開く

• 250-550-1000だったのでLv2を警戒
• 『k匹集まって食事をしているときは f[i]+(k-1)*g[i] のエサを食べるもっふもふの生き物がN匹います。財政上の都合で totalFood までしかエサをあげることができません。最大何匹飼えますか』
  • N≦50

• テストケース作成
  • 小さいの
  • 大きいの
  • あとfが小さいけどgが大きい（またはその逆）がややこしいケースかな。適当に小さいの作っておく

• for(x in 1..N) x匹飼えるか？
• を判定する。yesになる最大値が答え
• x匹が決まれば、g[i]にかかる係数が固定されるので、それぞれ
• v[i] = f[i] + (x-1)*g[i]
• 食べることが確定するので、
• これが小さい順にx匹選んで、totalFoodを超えてなければOK

• できた
• 書いた
• 通った
• submit

550開く

• 『SNSの"friend"のリンクをたどって自分の友達全員のページを訪問できる確率を最大化してください。』
  • SNSの登録者数はN≦36人
  • friendページを見ると、実際のfriendのうちK人がランダムに選ばれて表示されるのでそこからクリックしないといけない
    • K人以下しかfriedがいない場合は常に全員表示される
  • 自分(IDが1番の人)の友達以外のページは訪れない
  • 同じ友達のページを２回訪れることもない
  • 最適行動をとった場合に全員行ける確率を求めてね

• テストケース作成
  • 最小ケース
  • 最大ケース…はなんだろう、とりあえず完全グラフ作って K を色々変えておく

• 「今誰のページ見てるか * 今まで誰のページを見たか集合」を状態にDP
  • って、それは N * 2^N 状態だから N=36 では無理だ…
  • それでよければ簡単なんだけど、そうじゃないから550なんだろうなあ

• N=36ってことは、O(N * 2^(N/2)) くらいか、せいぜい
• 両側探索的にスタートからとゴールからで半分までの確率を求めて掛け算…
  • 仮に、スタートから18歩行った先全状態の最適確率が計算済みとする
  • するとさっきのDPで、18歩までしか見ないから、状態数が 18 * 2^18 に…
  • 逆に、全部訪れ状態から逆に18歩戻る方を計算すれば同じ理屈で18*2^18個しか計算しなくていいので
  • これを足し算して…

• これか！書こう
• よし、えーと最大18個訪れた状態を2^18のビットにエンコードs…
• ！！
• これ、状態数 2^18 じゃなくて 36C18 じゃん
  • 18/36のうちどの18個を訪れるか全通り考えなきゃいけないから
  • それは、37倍すれば確実に2^36を超える数だから、どう考えても2^18より遙かに大きい
• 無理だ

• ううむ。
• 逆に考えて、2^18 にするにはどうであればいいかというと、
  • 「ID 1～18 までを訪れた訪れてないフラグ」と「ID 19～36 フラグ」みたいに
  • 完全にIDを分けて半分個できればいい。
  • そんなDPになるような漸化式は…思いつかない…

• DP全体の構造を考えるより先に、個々の更新式を考えてみるか。
• 以外と、そっちからヒントが見つかるかも。
• つまり
  • 「今誰のページ見てるかv * 今まで誰のページを見たか集合m」での最適確率P(v,m)を
  • vから行けてmに含まれてないページuにおける確率P(u,m+{u})から求めるにはどういう式で計算すればいいか考える

• vから行ける友達がK人以下の場合
  • これは、P(u,m+{u}) が最大の友達uのページに行くのが最適
• というか、誰のページに行く方がいいかの順序関係は、Kとか関係なく一定だな
• vから{u1, u2, ..., ux} に行ける場合
  • pi = P(ui,m+{ui}) が大きいところに行けるならそっちに行った方がお得
• というわけで、{u1, ..., ux} を {p1, ..., px} の値でまずソートしておく
  • ui∈m のところには行けないので0としておくか
  • あと、uiが元々のスタートID1番さんの友達でない場合も行かないので0としておく

• で、ソートした後を改めて {(u1,p1), ..., (ux,px)} とすると
  • u1 さんが K 人のリストの中に入っていれば必ずそこに行くのが良い
    • 入っている確率は 1 - C(x-1,K)/C(x,K) だから
    • つまりこの確率で u1 さんの方に行く。p += (1 - C(x-1,K)/C(x,K)) * p1;
  • u1さんが入ってなくてu2さんが入っていればそこに。
    • この確率は C(x-1,K)/C(x,K) * (1 - C(x-2,K)/C(x-1,K)) だから
    • 簡略化すると (C(x-1,K) - C(x-2,K)) / C(x,K) こう。
  • 以下同様に
    • (C(x-i,K) - C(x-i-1,K)) / C(x,K) * pi;
  • の和をとれば答えが求まります

• だよね。
• でもこれを見てもDPの高速化のアイデアは浮かばない…

• 無理だ。あきらめて1000の問題読もう

1000開く

• 要は
• 『最大50頂点、50辺の無向グラフがあります。ただし、すべての頂点は高々１個のサイクルにしか所属していない、という特殊な形のグラフです。辺eの両端にはあらかじめ一人乗り移動用マシンがae個be個と置いてあって、こっちからそっちには最大ae人、あっちからこっちにはbe人動ける状態になってます。N人の人が任意のノードにばらまかれても全員0番ノードに集合できるようにするには、最低何個移動用マシンを増やせばいいですか』
  • N≦10万

• という問題文を読解するのに結構時間がかかった
• えーと、まずグラフをサイクルに分解する
• するとこのサイクルはツリー状になっているから、必ず0番(ルート)あるサイクル方向に向かっていく旅をしなければいけない
• サイクル間の橋は１個しかないから、そこで全員同じノードに集結するので結局
• １サイクルにN人ばらまかれたとき、各自左回りと右回りをどうするか適切に選択すればサイクル出口にN人行けるようにするにはどうすればいいですか
• という問題をサイクル別に解けばよい

• なんとかなりそうな気がするけど…
• 残り30分でこの「サイクル別に分ける」処理を正しく実装する自信がそもそもない…
• 550に戻った方がまだ望みがある気がする

550に戻る

• 20分考える
• やっぱりわからん

• 「ID1番の人の友達しか訪れない」って重要なのかなあ。
• 結局1番と全員が友達なら全員訪れなきゃいけないのだから、わざわざ足す必要のある条件とは思えないけれど…
• 待て
• 「結局1番と全員が友達」
• ってあり得ないのではないか？
• 入力フォーマットを確かめる
  • 友達リストは36"文字"の文字列で、整数をスペース区切りした形で与えられる
• ！！！！！！
• これ、数字とスペースが交互にくるから、せいぜい友達数は最大で18人なのでは…！！！！！
• 厳密にはもっと減るか、"1 2 3 ... 9 10 11 .." で、最大15人！

• うおおこれなら楽勝問題じゃないですか。36人かと思っていたら15人だった
• 実装
• 実装
• 実装
• 実装
• よっしサンプル通っtタイムアップ！
• orz

感想

• 550は気づけなければいけない問題だった
  • テストデータを作る時に、入力制約をちゃんと満たしているか確認すれば36"文字"には気づけたはず
  • ちょっと考えればハミルトンパス問題を還元できることがわかるので、N=36のハミルトンパスはLv2に要求するにはヒューリスティック的すぎることから考えて36頂点はありえないと見切れるべき
• 特に前者かなー。次はこれにははまらんぞ。

SRM476 550

あとで | 18:12 |

• 方針はあってた

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

class FriendTour { public:
   double tourProbability(vector <string> friends, int K) 
   {
      int N = (int)friends.size();
      vector< vector<int> > f(N);
      for(int i=0; i<N; ++i)
      {
         stringstream sin( friends[i] );
         for(int v; sin>>v; )
            f[i].push_back(v-1);
      }

      map<int,int> rename;
      rename[0] = 0;
      for(int k=0; k<f[0].size(); ++k)
      {
         int newid = rename.size();
         rename[f[0][k]] = newid;
      }

      vector< vector<int> > ff(rename.size());
      for(int i=0; i<N; ++i)
         if( rename.count(i) )
         {
            int k = rename[i];
            for(int j=0; j<f[i].size(); ++j)
               if( f[i][j]!=0 && rename.count(f[i][j]) )
                  ff[k].push_back( rename[f[i][j]] );
               else
                  ff[k].push_back( -1 );
         }
      return solve(ff, K);
   }

   double solve(vector<vector<int> >& f, int K)
   {
      memo = DP2<double>(f.size(), 1<<f.size(), -1);
      return rec(f, K, 0, 1);
   }

   double C(int N, int K)
   {
      double p = 1.0;
      for(int i=0; i<min(K,N-K); ++i)
         p = p * (N-i) / (1+i);
      return p;
   }

   DP2<double> memo;
   double rec(vector<vector<int> >& f, int K, int v, int mask)
   {
      if( memo(v,mask) != -1 )
         return memo(v,mask);

      if( mask == (1<<f.size())-1 )
         return 1.0;

      vector<double> nxt;
      for(int i=0; i<f[v].size(); ++i)
         if( f[v][i]==-1 || (mask & (1<<f[v][i])) )
            nxt.push_back(0);
         else
            nxt.push_back( rec(f,K,f[v][i],mask|(1<<f[v][i])) );
      sort(nxt.rbegin(), nxt.rend());
      int N = nxt.size();
      if( N == 0 )
         return memo(v,mask) = 0.0;

      if( N <= K )
         return memo(v,mask) = nxt[0];

      double p = 0.0;
      for(int i=0; i<nxt.size(); ++i) {
         if( N-1-i < K ) {
            p += C(N-i,K) / C(N,K) * nxt[i];
            break;
         }
         p += (C(N-i,K) - C(N-1-i,K)) / C(N,K) * nxt[i];
      }
      return memo(v,mask) = p;
   }
};

• 状態数 N・2^N、１状態ごとの計算に N 回 C(N,K) を呼んでいるので
• O(K・N^2・2^N) かな。たぶんC(N,K)の計算をもっとまともに高速化しないと本当は時間が危ないけど通ったからいいや