AGC 013 C - Ants on a Circle 解法

atcoder.jp

解法

向きを と書きましょう。

2 つのものを求めます。まずは順不同で蟻さんの位置を計算です。 これは、 をソートした結果です。

それとは別に、この配置が上記のものを何回 rotate したものであるのかを計算です。 頭にありさんを思い浮かべてください。展開して、線分です。端っこに行くとワープです。 位置は良いのです。順番だけを見つめてください。何かがわかりませんか？ そうです。ありさんワープのタイミングで +1 / -1 の rotate が起きています。 この回数をカウントすると良いです。

実装

まずは入力です。

i64 n;
i64 L, T;
std::cin >> n >> L >> T;

これはとても気づきづらい（←素晴らしい正当化）のですが、32 ビット整数型を使うとオーバーフローをします。また、符号なし整数型をまぜると剰余演算で「「よしなに」」変換がされてしまい、無事謎の WA に苦しめられることになります。

つぎに、順不同の配置を ans に格納していきつつありさんワープの回数を cnt でカウントです。

vec<i64> ans(n);
i64 cnt = 0;
for (i64 i=0; i<n; i++) {
    i64 x, w;
    std::cin >> x >> w;

    i64 y = x + (w==1 ? T : -T);
    i64 r = (y % L + L) % L;
    i64 q = (y - r) / L;
    ans.at(i) = r;
    cnt += q;
}

最後にソートと回転で、AC です。（ここの % n が曲者です。みなさん、64 ビットを使いましょう！（泣））

cnt = (cnt % n + n) % n;
std::sort(ALL(ans));
std::rotate(ans.begin(), ans.begin() + cnt, ans.end());

for (i64 x: ans) {
    std::cout << x <<'\n';
}

atcoder.jp