【数え上げ】L, Rのマッチング。Lを溜め込んで歩いてRとぶつかったら

f:id:peroon:20190825022212p:plain

  • https://youtu.be/JTH27weC38k?t=2936 この辺の話題
  • LとRをペアにする方法は何通りあるか？
  • これは左から人間が右に歩いていき、Lがあれば溜め込み、Rとぶつかったら溜め込んだLのどれかとマッチングさせてLを1減らすことを繰り返せばいい
  • 具体的に数えてみる（下記）

f:id:peroon:20190825023240p:plain

  • 左端のLに対し、Rは3パターンあり、どれを選んでも破綻しない
  • 選んだ後に他のペアも作ることを考えると、中・右の場合はペアが強制的に1通りとなる
  • そういう場合の数え上げが、「Lを溜め込んで歩いてRとぶつかったら~」である
  • これは https://atcoder.jp/contests/jsc2019-qual/tasks/jsc2019_qual_c の解法で必要となる知識の一部なのだが、知らなかったので覚えておこう

「別のクラスの人と3人組を作ってきてください」

動機

  • codeforcesでこの問題が解けなかった
  • https://codeforces.com/contest/1201/problem/B
  • 内容：数列Anからどれか2つを選んで-1することを繰り返し、数列を全ゼロにできるか
    • i != j
  • 解答は、max x 2 > sum のときNo, それ以外でYes
  • maxが飛び抜けちゃうとダメということ

f:id:peroon:20190805081441j:plain

一般化

  • これを一般化したのが下のmisteerの記事 & 熨斗袋さんの証明
  • 絵で描くとこういうことだろう

f:id:peroon:20190805082225j:plain

参考

https://misteer.hatenablog.com/entry/stone-cleaner

D - Gathering Children

f:id:peroon:20190805072240j:plain

Quiz

https://atcoder.jp/contests/abc136/tasks/abc136_d

AC Code

https://atcoder.jp/contests/abc136/submissions/6718753

解法

  • ダブリングやDPを使わない方法です
  • 大量に移動した後は、どこかのRLに落ちて振動します
  • 全てのRLの位置を調べておく
  • 各子供について、Rなら右側のRLに落ち、Lなら左側のRLに落ちる
  • lower_boundすれば、行き先のindexが求まるので、移動量の偶奇を見て、RLのどちらかが決まる

Code

    string s; cin >> s;
    ll L = s.size();
 
    set<ll> se;
    // RLなるi
    FOR(i, 0, L-1){
        if(s[i]=='R' && s[i+1]=='L'){
            se.insert(i);
        }
    }
 
    vector<ll> C(L, 0); // 位置ごとに子供をカウント
    FOR(i, 0, L){
        if(s[i]=='R'){
            auto it = se.lower_bound(i);
            ll index = *it; // 最終的に落ちるRLの位置
            ll diff = abs(index - i);
            if(diff%2==0){
                C[index]++;
            }else{
                C[index+1]++;
            }
        }
        else{
            auto it = se.lower_bound(i);
            it--; // 自分より左側のRL
            ll index = *it;
            ll diff = abs(index - i);
            if(diff%2==0){
                C[index]++;
            }else{
                C[index+1]++;
            }
        }
    }
    vprint(C);

スターリング数 stirling number (& ベル数 bell number)

ライブラリ

意味

  • N人をKグループに分割する方法
    • N>=K
    • グループは区別しない（箱に名前はない）し、箱の順番もない ( (1,3,1)と(1,1,3)などは同じものとする)

AC

計算量

  • O(NK)

読んだ（すごい）

検索用タグ

starling (間違い)

code

// スターリング数
// k個へのグループ分け
const int N_MAX = 1050;
ll memo[N_MAX][N_MAX];
bool stirling_memo_initialized=false;
void reset(){
  stirling_memo_initialized=true;
  rep(i,N_MAX){
    rep(j,N_MAX){
      memo[i][j]=-1;
    }
  }
}
ll stirling_number(ll n, ll k){
  if(!stirling_memo_initialized){
    cerr<<"need initialize"; exit(0);
  }
  if(memo[n][k]!=-1)return memo[n][k];
  if(n<k)return 0;
  if(n==0)return 0;
  if(k==0)return 0;
  if(n==k)return 1;
  return memo[n][k] = (stirling_number(n-1,k-1) + k * stirling_number(n-1,k)) % mod;
}

// ベル数
ll bell_number(ll n, ll k){
  mint m = 0;
  rep(i,k+1){
    m += stirling_number(n,i);
  }
  return m.x;
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    // input
    ll n,k;cin>>n>>k;

    reset();
    ll ans = stirling_number(n,k);
    p(ans);
    
    return 0;
}

ついでにベル数も