# **[2021/01/26 TPC](https://codeforces.com/group/9f55GySeDA/contest/313870)**
# **A. Case of Fake Numbers**
## 読解
$A + (1,\ -1,\ 1,\ -1,\ \cdots)x \equiv (0,\ 1,\ 2,\ \cdots) \pmod N$ を満たす $x$ があるか判定する.
## 解法
全探索する. $O(N^2)$.
## ソースコード

ll N;
cin >> N;
ll A[N];
rep(i, N) cin >> A[i];

rep(i, N) {
    ll f = 1;
    rep(j, N) if (A[j] != j) f = 0;
    if (f) {
        cout << "Yes" << rt;
        return 0;
    }
    rep(j, N) A[j] = (A[j] + (j % 2 ? 1 : N - 1)) % N;
}
cout << "No" << rt;

# **B. Case of Matryoshkas**
## 読解
適当に入れ子になっているマトリョーシカを、分解・合体を繰り返してひとつにするまでの最小回数を求める. ただし合体は一番外側にひとつ追加することしかできない.
## 解法
大きさ $1$ から繋がっている部分があれば残して, 残りは全て分解する. $O(N)$.
## ソースコード

ll N, M, res = 0, cnt = 0;
cin >> N >> M;
vector<ll> A[M];
rep(i, M) {
    ll K, X, c = 0;
    cin >> K;
    rep(j, K) cin >> X, A[i].pb(X);
    if (A[i][0] == 1) {
        rep(j, K) {
            if (A[i][j] + 1 == A[i][j + 1]) c++;
            else
                break;
        }
    }
    res += K - c - 1;
    cnt += K - c;
}
cout << res + cnt - 1 << rt;

# **C. Case of Fugitive**
## 読解
島を表す一次元区間たちと橋の長さたちが与えられるので, 全ての島 $i$, 島 $i + 1$ 間に橋をかける方法を求める. これは, 適切に変形すると $N - 1$ 個の区間 (すなわち橋の長さの上限・下限) と $N - 1$ 個の数の完全二部マッチングになる.
## 解法
区間はソートすると貪欲にできることが多い. この問題でも, 例えば区間を上限でソートして小さい順にループを回し, Set に上限以下のものを順次入れていって, 下限以上で Set 内最小のものをマッチングする, という貪欲法で求められる. $O(N\log NM + M)$.
## ソースコード

ll N, M;
cin >> N >> M;
ll L[N], R[N], A[M];
rep(i, N) cin >> L[i] >> R[i];
rep(i, M) cin >> A[i];
vector<pair<ll, ll>> a;
rep(i, M) a.pb(mp(A[i], i));
sort(all(a));
set<pair<ll, ll>> S;
vector<pair<pair<ll, ll>, ll>> v(N - 1);
rep(i, N - 1) {
    v[i] =
        mp(mp(max(R[i] - L[i + 1], R[i + 1] - L[i]), max(L[i] - R[i + 1], L[i + 1] - R[i])), i);
}
sort(all(v));
ll t = 0, res[N - 1];
rep(i, N - 1) {
    while (t < M and a[t].fi <= v[i].fi.fi) S.insert(a[t]), t++;
    auto lb = S.lower_bound(mp(v[i].fi.se, -1));
    if (lb == S.end()) {
        cout << "No" << rt;
        return 0;
    } else {
        res[v[i].se] = (*lb).second + 1;
        S.erase(lb);
    }
}
cout << "Yes" << rt;
rep(i, N - 1) cout << res[i] << rt(i, N - 1);

# **D. Case of Chocolate**
## 読解
正方形グリッドの左上半分 + 対角線上のマスを使用して, 以下のクエリを処理する.
- 対角線上のマスと方向が指定されるので, 何もないマスに当たるまでマスを削除する. このとき削除されたマスの個数を求める.
## 解法
実質 [AtCoder ABC 179 F - Simplified Reversi](https://atcoder.jp/contests/abc179/tasks/abc179_f). オフラインでいいので座圧してセグ木を貼るだけ. オンラインなら実装がちょっと大変. ちなみに私は Latte-Tree 派. $O(M\log M)$.
## ソースコード

ll N, M;
cin >> N >> M;
ll X[M], Y[M];
char D[M];
rep(i, M) cin >> Y[i] >> X[i] >> D[i];
vector<ll> zx = {0}, zy = {0};
rep(i, M) zx.pb(X[i]), zy.pb(Y[i]);
uniq(zx), uniq(zy);

rep(i, M) {
    if (D[i] == 'U') {
        cout << X[i] - seg1.result(bis(zy, Y[i])) << rt;
        seg2.combine(bis(zx, seg1.result(bis(zy, Y[i]))), bis(zx, X[i]) + 1, Y[i]);
        seg1.combine(bis(zy, Y[i]), bis(zy, Y[i]) + 1, X[i]);
    } else {
        cout << Y[i] - seg2.result(bis(zx, X[i])) << rt;
        seg1.combine(bis(zy, seg2.result(bis(zx, X[i]))), bis(zy, Y[i]) + 1, X[i]);
        seg2.combine(bis(zx, X[i]), bis(zx, X[i]) + 1, Y[i]);
    }
}

# **E. Case of a Top Secret**
## 読解
一次元上に杭がたくさんあるので, 以下のクエリを処理する.
- 指定した杭から, 与えられた長さの振り子を垂らし, 反時計回りに回転させる. すると, ある時間が存在してその時間以降特定の杭の周りを永遠に回り続けるので, その杭がどれなのか求める.
## 解法
ずっと $2$ つの杭の周りを回っているタイミングがあるので, それを剰余演算で計算すると, よくあるやつ (剰余を取ることにより, 各ステップで大きさが半分未満になる) によってステップ数が $\log L$ になる. その各ステップに二分探索を用いることで全体で $O(N + M\log N\log L)$ になる.
## ソースコード

ll N, M;
cin >> N >> M;
ll X[N], A[M], L[M], F[N];
pvector<ll> v;
map<ll, ll> to, from;
rep(i, N) cin >> X[i], v.eb(X[i], i);
sort(all(v));
rep(i, N) {
    to[v[i].se] = i;
    from[i] = v[i].se;
    F[i] = v[i].fi;
}
rep(i, M) cin >> A[i] >> L[i];

rep(i, M) {
    ll p = to[A[i] - 1], l = L[i];
    ll a = 0, b = N - 1, d = 0;

    while (b - a >= 1) {
        l %= 2 * (F[b] - F[a]);
        if (d == 0) {
            auto n = lower_bound(F + a, F + b + 1, F[p] + l + 1);
            if (n == F + a) break;
            n--;
            l -= (*n) - F[p];
            b = p = n - F;
            d = 1;
        } else {
            auto n = lower_bound(F + a, F + b + 1, F[p] - l);
            if (n == F + b) break;
            l -= (*n) - F[p];
            a = p = n - F;
            d = 0;
        }
    }
    cout << from[p] + 1 << rt;
}

# **感想**
全部典型とはいえ 1:59 全完, やったね!