読者です 読者をやめる 読者になる 読者になる

はまやんはまやんはまやん

hamayanhamayan's blog

クラス替え [yukicoder 396]

問題

http://yukicoder.me/problems/no/396

N人の生徒をMクラスに分ける。
順位によってクラスに分けられ、1位から順に1組, 2組, ..., m組と分けられる。
m組まで行ったら、次の順位の人から、m組, m-1組, ..., 1組と逆順に分けられる。
この昇順逆順を繰り返してクラスを決定する。
花子ちゃんがX位、太郎君がY位の時、二人が同じ組なら"YES"、そうでないなら"NO"を出力

2 <= N <= 10^9
1 <= M <= 10^9
1 <= X,Y <= N
X != Y

考察

1. 愚直にシミュレートすると、max(X,Y)までかかるので死ぬ
2. 計算で求められそう

3. 必要な考察としては、k位とk+2m位は同じ組となる
4. そのため、XもYも2mを法にして考えてOK

X %= 2m;
Y %= 2m;

5. こうすると、1 <= X,Y <= 2m となる
6. これで1~mがそのままの組に対応していて、m+1~2mが(2m+1-i)組に対応してる感じになる
7. これを利用して判定する

実装

http://yukicoder.me/submissions/103897

int N, M, X, Y;
//-----------------------------------------------------------------
int main() {
    cin >> N >> M >> X >> Y;

    X--; Y--;

    //cout << X << "," << Y << endl;

    X = X % (2 * M);
    Y = Y % (2 * M);

    //cout << X << "," << Y << endl;

    if (M <= X) X = M - 1 - (X % M);
    if (M <= Y) Y = M - 1 - (Y % M);

    //cout << X << "," << Y << endl;

    if (X == Y)
        cout << "YES" << endl;
    else
        cout << "NO" << endl;
}