cafelier@SRM

TCO09 Round1

SRM | 04:13 |

TCO09 Round1 の成績・ソース (要ログイン) : AC/-/- : もう通ればいいんだ…

250開く

• Round1は250をじっくり解きさえすれば通るだろーと甘く見て、普段の500から開きをやめて250に集中することにした。日和ってます。
• 『L個以上100個以下の連続する自然数の和でNになるもののうち一番短い列を求めよ』

• 最初「L個の」と読んでた
  • 和の公式を考えると、先頭をaとすると (a+a+L-1)*L/2 = N になるので
  • そういう a を求めればよい

• 求めた。答え合わない。
  • 「L個以上100個以下」って書いてあるじゃん！
  • 急遽引数名をLLに変え for(int L=LL; L<=100; ++L){...} で周りを囲う。
  • よし答え合った。submit。

• Lは2以上と書いてあるので、変なコーナーケースもないと思う…

500開く

• 『区間 [lower,upper] から独立に M 回自然数を取ってくるとき、sortしてK番目の数がNになる確率は？』

• えーとえーと。
• for(a,b,c) if(a<K<=a+b) p += "N未満がa個、Nがb個、Nより大きいのがc個になる確率" だよね</li>
• "..." の部分は
  • (N-lo)/(up-lo+1)のa乗 × 1/(up-lo+1)のb乗 × (残り)/(up-lo+1)のc乗 × C(M,a)×C(b+c,b)
  • とかだ

• (1/1000)の100乗とか、とてもワイドレンジな浮動小数点数が大量に混ざるんだけどこれ、これだと精度足りなそうな気がする

• うーむ。DPで綺麗に行ったりするかなあ

• M個中K番目がNになる確率 ==
  • 1個目がN未満な確率 × M-1個中K-1番目がNになる確率
  • ＋ 1個目がNより大きい確率 × M-1個中K番目がNになる確率
  • ＋ 1個目がNになる確率 × M-1個中...何？
    • K-1番目かK番目がNになる確率、とか？

• とりあえずそれでプログラム書いてみた。
  • K-1<1になったりK>M-1になったりするパターンのクリップがめんどいなー
• 書けた。全然合わない。
• えー。
  • 「K-1番目かK番目がNになる確率」って嘘じゃん！一個Nが奇譚だから左右上手く分かれればあとはひとつもN要らないよ
  • だめだわからん

• うううう残り20分…あきらめて1000やろう

1000開く

• 『300×300のチェス盤のそれぞれのマスにA～Zの文字が振ってあります。それとは別にA～Zからなる50文字の文字列wordがあたえられます。wordに書いてある文字を順番に踏むように"Unicorn"という駒を動かす動かし方は何通り？ mod 100..07 で』
  • Unicornは、「3マス以上前後左右に進む→垂直に曲がって2マス以上進む」という動きが出来るナイトが飛びすぎた感じのもの

• 行列乗算…だと90000×90000の行列だ。それはない

• いやしかし、Unicornは実はほとんどのマスに行けるので、各ステップで全マスたどって動き方を足し算する必要はなくて、
  • 全マス to 全マス行けると仮定していったん総和を足して、あとで行けないマスからの動き方を引くと速い
  • 1800 マスくらいしか行けないマスはないので。

• 90000*18000*50ってきついか。
  • O(RC(R+C)|word|)
  • しかし時間がない
  • 入力はランダムデータのみだから、多少いい具合にバラけると思うんだよ、たぶん。やってみよう
    • （あとで思うに全部A一色のデータは作れるのでそれだと全然困りますね）

• 書けた。サンプル通った！
• しかし同時にタイムアップ。うわあああもう数分早く500をあきらめていれば！
  • しかし、休憩時間中に300×300のデータを入れてみたら5秒前後。こりゃ無理だ。

感想

• うーむ500全然わからないぞ…まずい
• 1000はそうか、行けないゾーンはあらかじめ各行と列の和を計算しておけばあとは定数時間か。なるほど。

TCO Round1 500

あとで | 11:21 |

わーいDPだ

class KthProbableElement {
public:
  double probability(int M, int lowerBound, int upperBound, int N, int K) 
  {
    double dp1[101][101]={0}, dp2[101][101], (*P)[101]=dp1, (*Q)[101]=dp2;

    P[0][0] = 1.0;
    for(int i=0; i<M; ++i)
    {
      memset( Q, 0, sizeof(double)*101*101 );
      for(int a=0; a<=i; ++a)
        for(int b=0; a+b<=i; ++b)
        {
          Q[a+1][b] += P[a][b] * (N-lowerBound) / (upperBound-lowerBound+1);
          Q[a][b+1] += P[a][b] * 1 / (upperBound-lowerBound+1);
          Q[a][b]   += P[a][b] * (upperBound-N) / (upperBound-lowerBound+1);
        }
      swap(P, Q);
    }

    double p = 0.0;
    for(int a=0; a<=M; ++a)
      for(int b=0; a+b<=M; ++b)
        if( a<K && K<=a+b )
          p += P[a][b];
    return p;
  }
};

P[a][b] @ i == M個中i個目まで値を選んだとき、N未満の値がa個、Nがb個、(Nより大きいのがi-a-b個)、になっている確率。なんでこれが時間内で書けないかな自分は…

TCO Round1 1000

あとで | 11:49 |

普段mod演算は念のためlong longでやってるのだけど、それだとTLEした。intに変えて通しました。これは本番でいくら時間があっても気づけなかった予感。

static const int MODVAL = 1000000007;
int ADD(int x, int y) { return (x+y)%MODVAL; }
int SUB(int x, int y) { return (x-y+MODVAL)%MODVAL; }

class Unicorn {
public:
  int countWays(int R, int C, int L, int seed, string word) 
  {
    // input...
    char B[300][300];
    {
      int x = seed;
      int d = (65535 / L)+1;
      for (int r=0; r<R; r++)
        for (int c=0; c<C; c++) {
          x = (x * 25173 + 13849) % 65536;
          B[r][c] = (65+(x / d));
        }
    }

    // solve
    vector<int> cnt(C*R);
    for(int r=0; r<R; ++r)
    for(int c=0; c<C; ++c)
      if( B[r][c] == word[0] )
        cnt[r*C+c] = 1;

    for(int i=1; i<word.size(); ++i)
    {
      int total_cnt = 0;
      vector<int> c_cnt(C);
      vector<int> r_cnt(R);
      for(int r=0; r<R; ++r)
      for(int c=0; c<C; ++c)
        r_cnt[r]  = ADD( r_cnt[r], cnt[r*C+c]),
        c_cnt[c]  = ADD( c_cnt[c], cnt[r*C+c]),
        total_cnt = ADD(total_cnt, cnt[r*C+c]);

      vector<int> cnt2(C*R);
      for(int r=0; r<R; ++r)
      for(int c=0; c<C; ++c)
        if( B[r][c] == word[i] )
        {
          int x = total_cnt;

          for(int rr=r-1; rr<=r+1; ++rr) if(0<=rr && rr<R)
            x = SUB(x, r_cnt[rr]);
          for(int cc=c-1; cc<=c+1; ++cc) if(0<=cc && cc<C)
            x = SUB(x, c_cnt[cc]);

          for(int rr=r-1; rr<=r+1; ++rr) if(0<=rr && rr<R)
          for(int cc=c-1; cc<=c+1; ++cc) if(0<=cc && cc<C)
            x = ADD(x, cnt[rr*C+cc]);

          for(int rr=r-2; rr<=r+2; rr+=4) if(0<=rr && rr<R)
          for(int cc=c-2; cc<=c+2; cc+=4) if(0<=cc && cc<C)
            x = SUB(x, cnt[rr*C+cc]);

          cnt2[r*C+c] = x;
        }
      cnt.swap(cnt2);
    }

    int live = 0;
    for(int r=0; r<R; ++r)
    for(int c=0; c<C; ++c)
      live = ADD(live, cnt[r*C+c]);
    return live;
  }
};

ユニコーンのいけないところを列単位行単位でまとめておいて数えるとO(1)でひとつの遷移を計算できる