cafelier@SRM

SRM431 Div1

SRM | 13:15 |

SRM431 の成績・ソース (要ログイン) : AC/-/- : 問題文はちゃんと読みましょう

250開く

• 『第一と第四象限にy軸に平行な線分がたくさん与えられるので、-pi/2～pi/2 の範囲にランダムに一発貫通レーザー撃ったときに当たる本数の期待値は？』

• 最後まで読まずに『1本以上当たる確率は？』を求めるコードを書き始める
  • atan2で-pi/2～pi/2の区間グラフに落としてソートしてスイープ(笑)
    • いっつもatan2の引数の順番と値域の記憶が曖昧で毎回調べてるのをいい加減覚えたい
  • 答え合わない

• 問題ちゃんと読んだら「当たる本数の期待値は？」だった！
  • スイープするコードで重みを掛け算するように変更
  • 250にしてはタフな問題だなあ

• まあ答えはあった…
• 待て。本数の期待値ならそれぞれ独立でいいに決まっとるやん！
  • 区間グラフとかソートとか要らないそれぞれ独立に当たる確率計算して足すだけ！！！！！
  • 要らんコード全部消してSubmit。
  • おそろしく時間かかってしまった。何をやっているんだろう自分は…

500開く

• 『10進N桁の数値で、桁をA個のグループに区切るとそれぞれのグループ内で桁の数値が等差数列になってて、でも全グループ等差数列にするようなA-1個の切り方は不可能で、しかも桁は(広義の)昇順になってるようなのは何個ありますかmod 1000000007で』

• 「A個に切ったグループのまとまりを一つの数と見なして全体が等差数列」と考え始めてA-1個に切れない制約の反映の仕方がまったく思いつかなくて困る (10分)
• 「桁が昇順になってる」を「グループ内で桁が昇順になってる」と勘違い (40分)
  • しかも 123789 みたいなケースを考えて無くてグループの切れ目では常に桁が減る場合ばっかり考えてた

• と無駄に時間を費やしていました。何をやっているんだろう自分は…
• 終了10分弱前に数値は「全体で昇順」なことに気づく
  • てかこの時点で始めてサンプルの2,2のヤツをちゃんと見た。もうどうしようもない。
  • 間に合わねー。
  • 一応書いてみたけど 13|56|9 を 135|69 と分けられるのに気づかないようなコードができた辺りでタイムアップ
  • これはちゃんと最初から問題理解して取り組んでたらどうとでも解ける問題だった気がする…ぬぬぬ

1000開いてない

感想

• 問題サンプルマジメに読め。以上

SRM431 Div1 500

あとで | 14:53 |

やっぱり電車の待ち時間で解けるくらい何の変哲もないDPだった…；；

static const long long MODVAL = 1000000007;
int memo[10][11][1001][9];

class MegaCoolNumbers
{
public:
  int count(int N, int A)
  {
    memset(memo, 0xff, sizeof(memo));
    return rec(1, 10, N, A);
  }

  int rec(int D, int F, int N, int A)
  {
    if( A==0 )     return N==0 ? 1 : 0;
    if( N < A )    return 0;
    if( N==1 )     return 10-D - (F==10 ? 0 : 1);
    if( 10-D < A ) return 0;
    if( memo[D][F][N][A] != -1 )
      return memo[D][F][N][A];

    long long ans = 0;
    for(int d=D; d<=9; ++d) if(d!=F)
      for(int k=2; k<=N; ++k)
        for(int q=0; d+(k-1)*q<=9; ++q)
          ans += rec(d+(k-1)*q, min(10, d+k*q), N-k, A-1);
    return memo[D][F][N][A] = int(ans % MODVAL);
  }
};

SRM431 1000

あとで | 11:15 |

あまりの美しくなさに死にそう。RMQなしで書けますよねこれ多分。まあいいや

template<typename T>
struct RMQ
{
  vector< vector<int> > rm;
  T*  d;
  int n;

  RMQ( T* d, int n ) : d(d), n(n) {
    rm.push_back( vector<int>(n) );
    for(int x=0; x<n; ++x)
      rm[0][x] = x;
    for(int k=1; (1<<k)<=n; ++k) {
      rm.push_back( rm[k-1] );
      for(int x=0; x+(1<<k-1)<n; ++x)
        if( d[rm[k][x]] > d[rm[k-1][x + (1<<k-1)]] )
          rm[k][x] = rm[k-1][x + (1<<k-1)];
    }
  }

  int operator()(int L, int R) const { // d[L]..d[R] (inclusive) の最小値の最左インデックスを返す
    int k=0;
    for(; L+(1<<k) < R-(1<<k)+1; ++k) {}
    LL i = rm[k][L];
    LL j = rm[k][R-(1<<k)+1];
    return (d[i]<=d[j] ? i : j);
  }

  vector<int> all(int L, int R) const { // 同、全列挙
    vector<int> ans;
    int minValue = d[(*this)(L, R)];
    while( L <= R ) {
      int C = (*this)(L, R);
      if( minValue < d[C] )
        break;
      ans.push_back(C);
      L = C+1;
    }
    return ans;
  }
};

int B[2048][2048];
int U[2048][2048];
int D[2048][2048];

class PerfectRectangles
{
public:
  int numberOfRectangles(int N, int M, int X0, int A, int _B, int Y0, int C, int _D) 
  {
    // input
    int x=X0%N, y=Y0%N;
    memset(B, 0, sizeof(B));
    for(int i=0; i<M; ++i) {
      B[x][y] = 1;
      x = (x*A+_B)%N;
      y = (y*C+_D)%N;
    }

    // up (上に何マス進んだら黒マスがあるか)
    for(int y=0; y<N; ++y)
      for(int x=0; x<N; ++x)
        U[y][x] = (B[y][x] ? 0 : y==0 ? 1 : U[y-1][x]+1);

    // down (下に何マス進んだら黒マスがあるか)
    for(int y=N-1; y>=0; --y)
      for(int x=0; x<N; ++x)
        D[y][x] = (B[y][x] ? 0 : y==N-1 ? 1 : D[y+1][x]+1);

    // solve
    int cnt = 0;
    for(int y=0; y<N; ++y) {
      RMQ<int> rmU(U[y], N);
      RMQ<int> rmD(D[y], N);

      stack< pair<int,int> > S;
      S.push( make_pair(0, N-1) );
      while( !S.empty() ) {
        // RMQによる再帰探索。[y][L]から[y][R]までを下辺とする長方形は取れるか
        int L = S.top().first;
        int R = S.top().second;
        S.pop();

        int d = rmD(L,R);
        if( D[y][d] == 1 )
          ++cnt; // すぐ下に黒マスがある場合、下辺になれる
        if( D[y][d] <= 1 ) {
          vector<int> m = rmU.all(L, R);
          m.push_back(R+1);
          for(int i=0; i<m.size(); L=m[i++]+1)
            if( L <= m[i]-1 )
              S.push( make_pair(L, m[i]-1) ); // 上に伸ばせる限界の高さで分割
        }
      }
    }
    return cnt;
  }
};