AtCoder ABC 111 D - Robot Arms (ARC 103 D) (橙色, 600 点)

くやしい

問題へのリンク

問題概要

個の座標 () が与えられる。 今、40 本以下の正の整数 を用意して、それぞれについて

(), (), (), ()

をうまく選択して加算することで、() をすべて作れ。できないときは -1 とせよ。

各 について共通の を用いなければならない。

制約

• 
• 

考えたこと

そもそも 40 個くらいの値の足し引きでもって、1000 個の -10⁹ 〜 10⁹ の値を作れるかというと、

1, 2, 4, 8, 16, ...

というのがとりあえず思い浮かぶ。しかし x 座標, y 座標両方頑張ろうと思うと、60 個くらい欲しくなる。で、困っていた。

とりあえず必要条件として、

• abs(x_i) + abs(y_i) のパリティがすべて等しいこと

が条件なのはわかっていて、逆にパリティがすべて等しければ、長さ 1 のベクトルを無限に使えば絶対できるので、これが必要十分条件なのは OK。

そして、ものすごく驚いたのだが、

---

1, 2, 4, 8, 16, 32, ...

を上手く四方向に組み合わせると、任意の市松模様が作れる (x + y が奇数のところにはすべて行ける)

---

というのだ！！！！！

結論から言えば、マンハッタン距離は 45 度回すテクを使えば証明ができる。全体を 45 度回転してみると

• ()

を

• R: ()
• T: ()
• L: ()
• D: ()

の重ね合わせで作るゲームになる。これはよく見ると、x 座標と y 座標を独立にみればよいことを意味している。注意点として、これだと とかは奇数しか作れないので、これが偶数のときは、d_i = 1 をもう 1 個追加すれば OK。

あとは、

1, 2, 4, 8, 16, 32, 64, ..., 2ⁿ

を使って、任意の奇数を作る方法を考える。これは大きい方から順に Greedy に足し引きするので OK。

コード

#include <iostream>
#include <vector>
using namespace std;

using pll = pair<long long, long long>;

int main() {
    int N; cin >> N;
    vector<pll> pos(N);
    for (int i = 0; i < N; ++i) cin >> pos[i].first >> pos[i].second;
    
    int par = (abs(pos[0].first) + abs(pos[0].second)) % 2;
    for (int i = 0; i < N; ++i) {
        int par2 = (abs(pos[i].first) + abs(pos[i].second)) % 2;
        pos[i] = pll(pos[i].first + pos[i].second, pos[i].first - pos[i].second);
        if (par2 != par) {
            cout << -1 << endl;
            return 0;
        }
    }
    
    vector<long long> d;
    for (int i = 30; i >= 0; --i) d.push_back(1LL<<i);
    if (par % 2 == 0) d.push_back(1);
    cout << d.size() << endl;
    for (int j = 0; j < d.size(); ++j) cout << d[j] << " ";
    cout << endl;
        
    for (int i = 0; i < N; ++i) {
        int xdir, ydir;
        long long xsum = 0, ysum = 0;
        for (int j = 0; j < (int)d.size(); ++j) {
            if (xsum <= pos[i].first) xdir = 1, xsum += d[j];
            else xdir = -1, xsum -= d[j];
            if (ysum <= pos[i].second) ydir = 1, ysum += d[j];
            else ydir = -1, ysum -= d[j];
            
            if (xdir == 1 && ydir == 1) cout << "R";
            else if (xdir == 1 && ydir == -1) cout << "U";
            else if (xdir == -1 && ydir == -1) cout << "L";
            else cout << "D";
        }
        cout << endl;
    }
}

考えられる解法 2

マンハッタンに気づかなくても、2 冪だけで市松模様を全部作れそうだというのが

• 実験
• 手計算

などによって思い至ればまだ可能性はあった。そして、「x 方向と y 方向のうち、より必要差分大きい方に動かしていく」という適当な Greedy で通ってしまうっぽい。

この Greedy でよい理由は、マンハッタン距離の背景がわかっていればそれはそうではある。

#include <iostream>
#include <vector>
using namespace std;

using pll = pair<long long, long long>;

int main() {
    int N; cin >> N;
    vector<pll> pos(N);
    for (int i = 0; i < N; ++i) cin >> pos[i].first >> pos[i].second;
    
    int par = (abs(pos[0].first) + abs(pos[0].second)) % 2;
    for (int i = 0; i < N; ++i) {
        int par2 = (abs(pos[i].first) + abs(pos[i].second)) % 2;
        if (par2 != par) {
            cout << -1 << endl;
            return 0;
        }
    }
    
    vector<long long> d;
    for (int i = 30; i >= 0; --i) d.push_back(1LL<<i);
    if (par % 2 == 0) d.push_back(1);
    cout << d.size() << endl;
    for (int j = 0; j < d.size(); ++j) cout << d[j] << " ";
    cout << endl;
        
    for (int i = 0; i < N; ++i) {
        long long xt = pos[i].first, yt = pos[i].second;
        long long x = 0, y = 0;
        for (int j = 0; j < (int)d.size(); ++j) {
            if (abs(x - xt) >= abs(y - yt)) {
                if (x >= xt) x -= d[j], cout << "L";
                else x += d[j], cout << "R";
            }
            else {
                if (y >= yt) y -= d[j], cout << "D";
                else y += d[j], cout << "U";
            }
        }
        cout << endl;
    }
}

300 点解法

今回は冷静に部分点とりに行ったのはよかった。x, y 座標値が小さければ、ベクトルの長さを全部 1 にして 40 個用意して、直接 (x, y) へ向かって行って、余った部分は LRLRLR... みたいにすれば OK

#include <iostream>
#include <vector>
using namespace std;

using pll = pair<long long, long long>;
int N;
vector<pll> pos;

int main() {
    while (cin >> N) {
        pos.resize(N);
        for (int i = 0; i < N; ++i) {
            cin >> pos[i].first >> pos[i].second;
        }
        
        bool ok = true;
        long long maxd = 0;
        int par = (abs(pos[0].first) + abs(pos[0].second)) % 2;
        for (int i = 0; i < N; ++i) {
            int par2 = (abs(pos[i].first) + abs(pos[i].second)) % 2;
            if (par2 != par) ok = false;
            
            chmax(maxd, abs(pos[i].first) + abs(pos[i].second));
        }
        
        if (!ok) {
            cout << -1 << endl;
            continue;
        }
        
        if (maxd > 40) {
            cout << -1 << endl;
            continue;
        }
        
        cout << maxd << endl;
        for (int i = 0; i < maxd; ++i) cout << 1 << " ";
        cout << endl;
        
        for (int i = 0; i < N; ++i) {
            for (int j = 0; j < abs(pos[i].first); ++j) {
                if (pos[i].first > 0) cout << "R";
                else cout << "L";
            }
            for (int j = 0; j < abs(pos[i].second); ++j) {
                if (pos[i].second > 0) cout << "U";
                else cout << "D";
            }
            for (int j = 0; j + abs(pos[i].first) + abs(pos[i].second) < maxd; j += 2) {
                cout << "LR";
            }
            cout << endl;
        }
        
    }
}