問題

問題文

https://atcoder.jp/contests/abc111/tasks/arc103_b

問題概要

N 個座標 (X_i, Y_i) が与えられる.

正整数 d_1, d_2, d_3, .. d_m を用意し, それぞれに対して

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

のいずれかを加算することで, (X_i, Y_i) を全て作ることができるか.

不可能ならば -1 と出力せよ.

制約

$1 \leqq N \leqq 10000$
$-10^{9} \leqq X_i \leqq 10^{9}$
$-10^{9} \leqq Y_i \leqq 10^{9}$
$1 \leqq m \leqq 40$
$1 \leqq d_i \leqq 10^{9}$

解答例

解説

できない条件を考える. これはなんとかして気づくしかないらしい.

アームを定めたとき, (x + y) mod 2 の値はモードによらず一定となる. したがって与えられた座標 (X_i, Y_i) に対して, (X_i + Y_i) mod 2 が一定であるかを調べればできるかどうか判定できる.

部分点解法

$-10 \leqq X_i \leqq 10$
$-10 \leqq Y_i \leqq 10$

X, Y が小さいときは d_i = {1, 1, 1, 1, 1, 1, 1 ... 1} を用意すればよい.

// submission: https://atcoder.jp/contests/abc111/submissions/3880444
// Language: C++14 (GCC 5.4.1)
// Time: 4 ms
// Memoly: 256 KB
// Result: WA

#include <iostream>
#include <cmath>
 
using namespace std;
 
int main() {
    int N, m;
    int X[1003], Y[1003];
 
    cin >> N;
 
    int even = 0, odd = 0;
    for (int i = 0; i < N; i++) {
        cin >> X[i] >> Y[i];
        if ( ( abs(X[i]) + abs(Y[i])) % 2 == 0) {
            even++;
        } else {
            odd++;
        }
        if (abs(X[i]) > 10 || abs(Y[i]) > 10) {
            cout << -1 << endl;
            return 0;
        }
    }
    if (even && odd) {
        cout << -1 << endl;
        return 0;
    }
 
    if (even) { m = 22; }
    else { m = 21; }
    cout << m << endl;
    for (int i = 0; i < m; i++) {
        cout << 1;
        if (i == m-1) { cout << endl; }
        else { cout << " "; }
    }
    for (int i = 0; i < N; i++) {
        if (X[i] <= 0) {
            for (int j = 0; j < abs(X[i]); j++) {
                cout << "L";
            }
        } else {
            for (int j = 0; j < X[i]; j++) {
                cout << "R";
            }
        }
        if (Y[i] <= 0) {
            for (int j = 0; j < abs(Y[i]); j++) {
                cout << "D";
            }
        } else {
            for (int j = 0; j < Y[i]; j++) {
                cout << "U";
            }
        }
        for (int j = 0; j < m - abs(X[i]) - abs(Y[i]); j++) {
            if (j % 2 == 0) { cout << "RL"; }
        }
        cout << endl;
    }
    return 0;
}

満点解法

2の冪乗で構成される d_i = {1, 2, 4, 8, 16, ... 2ⁱ} を用意すると任意の (x + y) % 2 == 1 の座標を表現できる.

d_i = {1} のとき表現できる座標は下の図である.

f:id:kira000:20181227182252p:plain

d_i = {1, 2} のときは

f:id:kira000:20181227182303p:plain

となり, d_i = {1, 2, 4, 8, ... 2³²} のときは今回の制約内のうち x_i + y_i % 2 == 1 を満たす全ての座標を表現できる.

x_i + y_i % 2 == 0 のときは, d_i = {1, 2, 4, 8, ... } に 1 をひとつ追加するだけでいい.

任意の座標を表すには大きい要素から見ていき, 原点に最も近くづくような方向を選び続ける貪欲法のようなことをすればよい.

C++ による実装例

// submission: https://atcoder.jp/contests/abc111/submissions/3881483
// Language: C++14 (GCC 5.4.1)
// Time: 5 ms
// Memoly: 256 KB

#include <iostream>
#include <cmath>

using namespace std;

typedef long long ll;

void solve(ll x, ll y, ll v[], int m) {
    int dx[4] = {-1, 0, 0, 1};
    int dy[4] = {0, -1, 1, 0};
    char mode[4] = {'R', 'U', 'D', 'L'};
    for (int i = 0; i < m; i++) {
        int dir = 0;
        ll t = abs(x + v[i] * dx[0]) + abs(y + v[i] * dy[0]);
        for (int j = 0; j < 4; j++) {
            ll nx = x + v[i] * dx[j];
            ll ny = y + v[i] * dy[j];
            if (abs(nx) + abs(ny) < t) {
                t = abs(nx) + abs(ny);
                dir = j;
            }
        }
        x = x + v[i] * dx[dir];
        y = y + v[i] * dy[dir];

        cout << mode[dir];
    }
    cout << endl;
    return;
}

int main() {
    int N, m = 34;
    ll X[1003], Y[1003];
    ll d[34];
    ll  t = 1;
    for (int i = 0; i < 33; i++) {
        d[32-i] = t;
        t *= 2;
    }
    d[33] = 1;

    cin >> N;

    int even = 0, odd = 0;

    for (int i = 0; i < N; i++) {
        cin >> X[i] >> Y[i];
        if ( ( abs(X[i]) + abs(Y[i])) % 2 == 0) {
            even++;
        } else {
            odd++;
        }
    }
    if (even && odd) {
        cout << -1 << endl;
        return 0;
    }

    if (odd) { m -= 1; }
    cout << m << endl;

    for (int i = 0; i < m; i++) {
        cout << d[i];
        if (i == m-1) { cout << endl; }
        else { cout << " "; }
    }
    for (int i = 0; i < N; i++) {
        solve(X[i], Y[i], d, m);
    }
    return 0;
}

Python3 による実装例

# submission: https://atcoder.jp/contests/abc111/submissions/3881508
# Language: Python3 (3.4.3)
# Time: 114 ms
# Memoly: 3188 KB

def solve(x, y, d, m):
    ret = ""
    dx = [-1, 0, 0, 1]
    dy = [0, -1, 1, 0]
    mode = ['R', 'U', 'D', 'L']
    for i in range(m):
        dir = 0
        t = abs(x + d[i] * dx[0]) + abs(y + d[i] * dy[0])
        for j in range(4):
            nx = x + d[i] * dx[j]
            ny = y + d[i] * dy[j]
            if abs(nx) + abs(ny) < t:
                t = abs(nx) + abs(ny)
                dir = j
        x = x + d[i] * dx[dir]
        y = y + d[i] * dy[dir]
        ret += mode[dir]

    print (ret)


def main():
    m = 34
    X, Y, d = [], [], []

    for i in range(32, 0, -1):
        d += [2**i]
    d += [1]

    N = int(input())
    even, odd = 0, 0

    for i in range(N):
        x, y = map(int, input().split())
        X += [x]; Y += [y]

        if (abs(x) + abs(y)) % 2 == 0:
            even += 1
        else:
            odd += 1

    if even and odd:
        print(-1)
        return 0

    if odd:
        m -= 1
    else:
        d += [1]

    print(m)
    print(" ".join(map(str, d)))

    for i in range(N):
        solve(X[i], Y[i], d, m)

main()

kira924age’s note

AtCoder Beginner Contest 111: D - Robot Arms

問題

問題文

問題概要

制約

解答例

解説

部分点解法

満点解法

参考文献