けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ARC 103 D - Robot Arms (600 点)

くやしい

問題へのリンク

問題概要

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

( d_i, 0), ( -d_i, 0), ( 0, d_i), ( 0, -d_i)

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

 i について共通の  d_1, d_2, ..., d_m を用いなければならない。

制約

  •  1 \le N \le 1000
  •  -10^{9} \le x_i, y_i \le 10^{9}

考えたこと

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

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 度回転してみると

  • ( x_i + y_i, x_i - y_i)

  • R: ( d_i, d_i)
  • T: ( d_i, -d_i)
  • L: ( -d_i, -d_i)
  • D: ( -d_i, d_i)

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

あとは、

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

を使って、任意の奇数を作る方法を考える。これは大きい方から順に 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;
        }
        
    }
}