cafelier@SRM

SRM460

SRM | 13:36 |

SRM460 の成績・ソース (要ログイン) : AC/AC/- : もっと素直に考えよう素直に

500開く

• 『JさんとBさんがN個の町からそれぞれK個ランダムに選んで訪れます。i番目の町でJさんが会える人数はmJ[i]～MJ[i]人の中からランダムに決まります。Bさんも同様にmB[i]～MB[i]。二人が会った人数が等しくなる確率は。』
  • NもKもmJ,MJ,mB,MBも40以下
  • 追加したテストデータ:
    • mJ,MJ=40,40; mB,MB=40,40; k=1 (N=1の例は元々サンプルにあったので、一番極端な例を追加)
    • mJ,MJ=1*40,40*40; mB,MB=1*40,40*40; k=40 (最大)

• 各町ごとに独立に会う人数が決まるんだから、
• ええと、i番目の町でJさんが会う人数の期待値はeJ[i]=(mJ[i]+MJ[i])/2で
• 要は、eJ から K 個選んだ和と eB から K 個選んだ和が等しくなる確率を求めれば。
• 全部/2がかかってるから/2しないでeJ[i]=(mJ[i]+MJ[i])でいいか

• って、俺は何を言っているのだ。期待値とる意味がわかりません。
  • mJ,MJ={1,9} と mB,MB={5,5} が100%同じ人数に合うみたいな計算になってしまう
  • 寝ぼけすぎだ。落ち着こう。

• 最大で、40×40=1600人に会うことになる。
  • てことは、Jさんが0人に会う確率、1人に会う確率…、1600人に会う確率、を求めて
  • 同様に Bさんが0人に会う確率、1人に会う確率…、1600人に会う確率、を求めて
  • それぞれ pJ[i], pB[i] とすると
    • Σ_{j=0～1600} pJ[i]*pB[i]
  • が答えだな。

• その確率どうやって求めようか。
  • 町が1番からN番まであるとして、端から順番に訪れる場合
    • N-1番目まで訪れた時点で
      • q[0..1600] = 0人に会う確率、1人に会う確率…、1600人に会う確率
    • とすると、N番目を訪れた時点では、
      • さらにmJ[N]人からMJ[N]人がランダムで追加されるわけだから
      • p[j] = (q[j-mJ[n + q[j-mJ[n]+1] + ... + q[j-MJ[n) / (MJ[n]-mJ[n]+1)
      • だ。j<MJ[n] の場合とかは適当に和を途中で打ち切ればいい</li>

• ただ「ちょうどK個の町を訪れる」条件も考えなきゃいけないので、
  • 「i番目までの町を試して、その中でvis個の町を訪れたときに、s人に出会っている確率」
  • みたいにもう一個表の次元を増やして考える。DP。

• 表のサイズが40*40*1600で、１マスの更新に40かかるから、
• 40^5のオーダか。1億。まあなんとかなるんじゃないでしょうか
• というわけでガリガリと実装。

• できた。
• サンプル出力より確率すっごい小さい。なぜ…
• あ、
  • 「N番目までの町を試して、ちょうどK個訪れたとき」に、s人に出会っている確率
• が欲しいのに、このDPの表に入ってるのは
  • 「N番目までの町を試したときに、「ちょうどK個訪れてて、s人に会ってる確率
• だ。訪れた町がK個じゃない場合まで含めた確率になってしまっている。

• これを補正するには、まず、「ちょうどK個の町を訪れている確率」を先に表から和を取って求めて
• それで割ればいい。条件付き確率とかいうんだっけ。しらない。

• よし、サンプルと合った！
• しかしこれ凄い回数doubleの演算くり返すけど精度大丈夫かな。
• 全部整数で、場合の数を正確に計算して最後に割り算しないと精度足らないというオチでは…
• しかしなんだかかなり時間かかってしまったし
• これで大丈夫ということにしよう。時間余ったらあとで戻ってくる。
• submit!

250開く

• 「Q個のYes-No式の質問を用意しました。それを同じ人にN(≧Q)回訪ねた答えのリストがあります。だけど、何回目にどの質問をしたのか忘れてしまいました。何回目にどの質問をした可能性があるか、可能なパターン数を求めてね」
  • 前提:Q個のそれぞれは最低1回は質問している
  • 前提:同じ質問には必ず同じYes/Noで答える
  • 2≦Q≦9、Q≦N≦9
  • 追加したテストデータ:
    • 2, {"Yes", "Yes"}
    • 2, {"No", "No"}
    • 2, {"Yes", "No"}
    • 2, {"No", "Yes"} (最小例全部)
    • 9, {"Yes","Yes","Yes","Yes","Yes","Yes","Yes","Yes","Yes"} (最大)
    • 8, {"Yes","Yes","Yes","Yes","Yes","Yes","Yes","Yes","Yes"}
    • ...
    • 2,

{"Yes","Yes","Yes","Yes","Yes","Yes","Yes","Yes","Yes"} (最大は自明に9!なのでこの辺の方が時間かかりそう)

• 全探索で間に合うかな。つまり、
  • N問ぜんぶに、Q個の質問のどれであるか割り当ててみる (Q^N通り)
  • Q個全部使ってるか確かめる
  • 同じ質問に同じ答え返してるか確かめる
• をQ^N通り全部くり返してカウント。計算量O(Q^N N)くらいか。
• 9^9*9 = 30億以上あるなあ。ダメか。

• むむう。するとまったくわからない。
• どうすればいいんだ。
• （※ 数式をいじりまわして20分悩む。二晩経ったら何考えてたか忘れてしまった…）

• こういうのはどうだろう。
  • 質問のうち、答えがYesになるものがy個、Noになるものがn=(Q-y)個と仮定する
  • このようになる場合の数は、Q個からy個選ぶ場合の数、C(Q,y)通り
  • 与えられたYesNo配列から、Y=(Yesの数) と N=(Noの数) を数える
  • すると、このY個のYesのそれぞれはy個の質問のどれかで、N個のNoのそれぞれはn個の質問のどれかなので、
    • d(n,k) = n個のものをk個に割り振る場合の数。ただしk個のそれぞれに1個以上は割り振る
  • としたとき、d(Y,y)*d(N,n) が求めたい場合の数。
• というわけで、答えは Σ_{y=0～Q} C(Q,y)*d(Y,y)*d(N,Q-y) だ！

• d(n,k) は、なんか気合いで再帰とかで計算して間に合いそうな気がする
• 必要なメモ化も入れれば確実に O(nk*α) で求まるでしょう

• 実装
• できた。特にメモ化等しなくても間に合ってる
• submit！

1000開く

• 『無向グラフが与えられます。これにいくつか辺を付け足して、"どの2点間にも1つはパスがあるが、3つの異なるパスはない"状態にするやり方は何通りありますか。mod (32-bits singedにおさまる程度)』
  • 頂点数20以下

• 簡単なようなら残り20分で挑戦したいけど、無理なら500のチェックに戻った方が無難かな。
• まだ誰も解いてないっぽい。無理かな。しかし面白そうなので15分考える

• 200個くらい辺があるから、全探索は 2^200 で全然無理。当たり前ですが。
• しかしこれ全探索でもどうやってやればいいのかな。
• 問題が最小全域木（どの2点間にも"2つの"異なるパスはない）なら、Kruskulのアルゴリズムの途中状態をステートに深さ優先探索でできそうだけど。
• それの応用でできないかな。
  • Kruskulのためのunion-findデータ構造に、各同値類がツリーである(0)、サイクル1個(1)、それ以上(2)
  • という状態を持たせておく。unionするときにこの値を足し算すする。
  • 2のができたら、そこに3つ以上必ずパスがあるので、探索失敗。バックトラック。

• 書いてみた。

    LL cnt = rec(uf, i, j+1, N, map);  // i-j の辺を特に増やさない場合
    if( map[i][j] == 'N' )  // 増やす場合は
    { 
      UnionFind uf2(uf); //cycle情報付きunion-findの状態を保存して
      if( uf2.Union(i,j) < 2 ) 
        cnt = (cnt + rec(uf2,i,j+1,N,map)) % MODVAL; //再帰探索
    } 

• おお、小さいデータなら全部答え合った。面白いなー。

• 面白がっている場合ではない。20点のグラフでどうするんだこれ。
• わからない
• タイムアップ

撃墜タイム

• 250は普通にdfsで真っ向から全探索するだけだったっぽい…

感想

• 250、何を難しく考えているんだろうなあ僕は。
• 素直になりましょうもっと。

SRM460 250

あとで | 13:51 |

書いてみたら意外とTimeLimitシビアだった。

class TheQuestionsAndAnswersDivOne { public:
   int find(int questions, vector <string> answers) 
   {
      vector<int> Q(questions, -1);
      return rec(0, answers, Q, questions);
   }
   int rec(int i, const vector<string>& A, vector<int>& Q, int R)
   {
      if( R > A.size()-i ) return 0; // これ
      if( i == A.size() )  return 1;

      int cnt = 0;
      for(int q=0; q<Q.size(); ++q)
         if( Q[q] == -1 )
         {
            Q[q] = (A[i]=="Yes");
            cnt += rec(i+1, A, Q, R-1);
            Q[q] = -1;
         }
         else if( Q[q] == (A[i]=="Yes") )
         {
            cnt += rec(i+1, A, Q, R);
         }
      return cnt;
   }
};

この枝刈りがないと通らない。これは一発で気づけなくても自分を許せる気がしてきました。