2019-04-13

フロイドの循環検出法 Floyd's cycle-finding algorithm

f:id:peroon:20190413020858j:plain

始点からうさぎ(fast)と亀(slow)を走らせる
- fast += 2;
- slow += 1;
出発からm秒後に出会ったとする
ループがあるときは上記の状態になっている
ループの始点をOとする
ループの一周の長さ：μ
ループに入るまでの道の長さ：λ
Oからd進んだところでうさぎと亀が出会ったとする
- この時まだOもdも不明
- 0<= d <= μ-1
出会った位置からλだけ移動すると、d+λ = m = aμ なので（！？）Oに(何週かするかもしれないが)到達する
- ∵ d = m - λ
- そこからλ進むとmなので、Oからm進んだことになる
- m = aμなので、Oに到着する
これらの考察を用いると、下記の値 λ, μが求まる

λの求め方

出会った位置と始点に速度1で動く人を置き、衝突するまで進める
- Oで衝突する
- ぶつかった時までにかかった時間がλである

μの求め方

もう1度出会うまでの時間を数えればいい
出会った位置(O+d)からさらに継続して
- fast += 2;
- slow += 1;
を続けると、μ秒後にまた出会うので、
- μ = 2回目に出会った時間 - 1回目に出会った時間

参考：Wikipedia

https://ja.wikipedia.org/wiki/%E3%83%95%E3%83%AD%E3%82%A4%E3%83%89%E3%81%AE%E5%BE%AA%E7%92%B0%E6%A4%9C%E5%87%BA%E6%B3%95

Floyd's Tortoise and Hare

とも言われる。https://en.wikipedia.org/wiki/Cycle_detection

2019-04-12

No.726 Tree Game

Quiz

https://yukicoder.me/problems/no/726

Submit

https://yukicoder.me/submissions/337152

解法

Xの次の素数を見つけ、pxとする。間隔(動けるスペース)はpx - X - 1
Yも同様
(1)+(2)の偶奇で勝敗が決まる

公式解法

X, Yの偶奇を見るだけでよいそう
これについてはパッと分からなかったので補足
Xが偶数の時、その隣は
- 奇数（素数）
- 奇数（合成数）
のどちらか。その隣は偶数なので素数ではない
よって、素数にぶつかるとしたら、その時の間隔は偶数に限られる
Xが奇数の時は同様に考えて、素数にぶつかった時の間隔は奇数に限られる

2019-04-09

No.477 MVP

yukicoder 二分探索

Quiz

https://yukicoder.me/problems/no/477

Submit

https://yukicoder.me/submissions/336588

解法

他の人は数式で解いていたが、私は二分探索で解いた
二分探索
- left = 0 (絶対にMVPが取れない)
- right = inf (絶対にMVPが取れる)
- center = (left + right) / 2
centerダメージを与えた時、MVPに入れるかを返す関数を作る
計算量はlog(N)となり、解くことができました

Code

const ll inf = 1e18;

ll N, K;

bool can_beat(ll damage){
    ll rest_HP = N - damage;
    if(rest_HP<=0){
        return true;
    }

    ll n = rest_HP/K;
    if(n<damage){
        return true;
    }else{
        return false;
    }
}

int main(){
    // input
    cin >> N >> K;

    if(N<=K){
        p(1);
        return 0;
    }

    ll left = 0;
    ll right = inf;

    while(left+1!=right){
        ll center = (left+right)/2;    
        if(can_beat(center)){
            right = center;
        }else{
            left = center;
        }
    }
    p(right);
    
    return 0;
}

2019-04-09

No.123 カードシャッフル

Quiz

https://yukicoder.me/problems/no/123

Submit

https://yukicoder.me/submissions/336529

解法1

そのままに実装する
- 制約が緩いので通る

解法2

操作を逆順にたどる
- この解法で解いた
- 解法1より速い
- 星1.5よりは難しい

Code

int main(){
    // input
    cin >> N >> M;
    A.resize(M);
    
    FOR(i, 0, M){
        cin >> A[i];
    }
    
    ll index = 1;

    // うしろから
    for(int i=M-1; i>=0; i--){
        ll a = A[i];
        if(index==1){
            index = a;
        }
        else{
            if(a<index){
                //
            }
            else if(a>=index){
                index--;
            }
        }
    }

    p(index);
    
    return 0;
}

サンプル4

 1  2  3  4  5  6  7  8  9 10 
6番目を動かした結果
 6  1  2  3  4  5  7  8  9 10 
10番目を動かした結果
10  6  1  2  3  4  5  7  8  9 
4番目を動かした結果
 2 10  6  1  3  4  5  7  8  9 
2番目を動かした結果
10  2  6  1  3  4  5  7  8  9 
7番目を動かした結果
 5 10  2  6  1  3  4  7  8  9 
1番目を動かした結果
 5 10  2  6  1  3  4  7  8  9 
4番目を動かした結果
 6  5 10  2  1  3  4  7  8  9 
3番目を動かした結果
10  6  5  2  1  3  4  7  8  9