C. Game with Chips (Educational Codeforces Round 84)

よく考えず後ろの問題を解きにいったことを海より深く反省・・・。

問題

https://codeforces.com/contest/1327/problem/C

問題概要

n * mの碁盤の目の上にk個の石が置かれている。

すべての石を同時に上下左右いずれかの隣接するマスに動かす、という操作を2nm回までおこなうことができる。 この際、それ以上動かせない場所にある石は動かさないものとする。

上記の操作を行った上で、それぞれの石に対して指定されたマスを最低一度訪れたい。可能なら移動順を示せ。2nm回で不可能なら-1を出力せよ。

考察

2nm回という上限があります。実はこれ、四隅のどこかからジグザグにまんべんなくすべてのマスを通過して、さらに同じ経路を辿って元の地点に戻ってくることが可能な大きさなのです。

例えば3*3の碁盤の場合で考えてみると、左上隅からRRDLLDRRですべてのマスを通って右下隅に行くことができ、LLURRULLですべてのマスを通って左上隅に戻ることができます。

この時石はどうなっているかというと、前半の操作ですべての石が右下に集まり、後半の操作ですべての石がすべてのマスを移動しています！！

なので、与えられた石と訪問場所の座標は一切関係なく、上記の操作をすると条件を必ず満たすことができるので、その操作をsubmitするとACとなります！！　なんだそりゃ。

ちなみに、前半の石を集めるパートについてはすべてのマスを通過する必要もなく、上記の例だとRRDDで事足ります。この場合、すべての石を右に寄せてそれをすべて下に寄せるという操作が実現できています。

#include <bits/stdc++.h>
using namespace std;
 
int main() {
    int n, m, k;
    cin >> n >> m >> k;

    // 石の座標、どうでもいいです
    int x, y;
    for (int i = 0; i < k * 2; i++) cin >> x >> y;

    // 以下は実装の簡単のため余分な操作が2つ混じりますが、結果に影響はありません
    string ans;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m - 1; j++) ans += (i % 2 == 0 ? 'R' : 'L');
        ans += "D";
    }
    for (int i = 0; i < n; i++) {
        // nの偶奇によって右下で終わるか左下で終わるかが異なります
        for (int j = 0; j < m - 1; j++) ans += (i % 2 == n % 2 ? 'R' : 'L');
        ans += "U";
    }
    cout << ans.size() << endl << ans << endl;
}