草体にぼ日記

だらだらと

12月4日　精進

12月4日

  • 解いた問題

ABC028c - 数を三つ選ぶマン

ABC136d - Gathering Children

  • ABC028c - 数を三つ選ぶマン

abc028c problem

解法

A,B、C,D,Eの上二つとAを足せばいいのかと思った… う～ん。不思議な問題だな。 5C3だから10通り全部試せばいいけど、制約が大きくなったら解法通りの解きかたが求められそうなので頑張ってね。

  • ABC136d - Gathering Children

abc136d problem

int main()
{
    cout << setprecision(10);
    cin >> s; 
    //Rの左端、Lの右端を取得する操作を繰りかえす
    int startR = 0  ,lastL;
    vector<int> Rdepo(0) , Ldepo(0);
    vector<int> Mdepo(0);
    for(int i = 0 ; i < s.size() ; i++){
        //Rが出てきたときにその左がLならいい
        //右端のLを取得する
        if(s[i] == 'L' &&s[i-1] == 'R'){
            Mdepo.push_back(i-1);
            //値が集まる左側を保持しておく
        }
        if(i!= 0 && s[i] == 'R' && s[i-1] == 'L'){
            lastL = i-1;
            Rdepo.push_back(startR);
            Ldepo.push_back(lastL);
            startR= i ;
        }
    }
    Rdepo.push_back(startR);
    Ldepo.push_back(s.size() - 1 );


    vector<int> ans(s.size(),0);
    //startR,lastL,Mを使って勝てそうな気がする
    for(int i = 0 ; i < Mdepo.size() ; i ++ ){
        int sum =   Ldepo[i]- Rdepo[i]+ 1; 
        int left = sum / 2 ;
        int right = sum / 2 ;
        if(sum %  2 == 1){
            right ++ ;
        }
        //範囲が奇数なら、もう一個は＋１

        if(sum %2 == 1){
            //範囲が奇数だったら、片方が大きい数字、片方が小さい数字
            //Mdepo[i] - Rdepo[i] + 1 でRの個数
            //sum - ↑で　Lの個数
            int tmp = Mdepo[i] - Rdepo[i] + 1;
            int num = max( tmp  , sum - tmp) ;
            if(num == tmp){
                //Rのほうが多い
                int path = num - 1;
                if(path % 2 == 0){
                    swap(left,right);
                    //leftのほうが大きくなる
                }
            }else{
                int path = num - 1 ;
                if(path %2 == 0){
                    //rightのほうが大きいのでそのまま
                }else{
                    swap(left,right);
                }
            }
        }
        ans[Mdepo[i]] = left;
        ans[Mdepo[i]+1] = right;
    }
    for(auto x : ans){
        cout << x << " " ;
    }
    cout << endl;
}
解法

公式の解説を聞くとめちゃくちゃわかりやすいので、この記事よりもそっちを見たほうがいいよ(ここは僕の考えた解きかたの垂れ流しで、解説を聞いた後の完璧な解法ではないので）

区間ごとに見る。 操作回数が10100ってバカでかいから、なんとなく偶数か奇数化で何かが起こりそうな気がする。

手を動かしてみると、Rの左端とLの右端を取得して、その区間の中のある場所に子供たちが集まることがわかり、その集まる位置は、Rの右端とLの左端の二か所になっている。

区間ごとの子供がいる人数が偶数なら集まる位置に半分ずつ、そうじゃないなら片方に一人多く入る。

さて、今片方に一人多くの人が入るとき、それはどうやって判別すればいいのだろう。 区間ごとにLとRのうち、多いほうの数をkとすると、Rを繋ぐ道はk-1 個である。つまり、k－1回の操作で、人々は集まる位置に集まり終わって、あとは二つの値の入れ替えを行い続けるだけである。 つまり、k-1が偶数なら、集まり終わった瞬間の値、そうじゃないなら集まり終わった瞬間の値のswapを行う。 例えば RRRLLのとき、（1インデックスとして） 3番目と4番目に子供は集まり、多いほうの数はRの3で、 Rを繋ぐ道は2個。 つまり、2回操作したら 00320(集まり終わった瞬間っていう） となり、残りの操作回数は10100 - 2 ＝偶数回なので

00230(集まり終わった瞬間の次の並び）

00320(集まり終わった瞬間から2回（偶数回）あとの並び） って感じになる。