AtCoder Regular Contest 109 D - く

問題: D - L

問題概要

二次元の平面上の点 $(0, 0), (0, 1), (1, 0)$ に石が一つずつ並んでいる。このような石の置き方をくの字であると呼ぶ (詳細な条件は問題文参照) 。

3つの石の中から1つ選んで好きな位置に移動させる操作を好きだけ行うことができる。ただし、各操作の後、石はくの字になっていなければならない。

石が点 $(\mathit{ax},\mathit{ay}),(\mathit{bx},\mathit{by}),(\mathit{cx},\mathit{cy})$ にひとつずつ石が置かれている状態になるまでに必要な最小の操作回数を求めよ。

$T$ 個 ($T \lt 10^3$) のテストケースが与えられるので、それぞれ答えよ。

解法概要

くの字となる並び方は、くの字の中心 (または左下など) の座標が定まっても一意には定まらない。

そこで、x, y 各座標の値の和を考えてみると、

同じ「く」の形のまま x 座標またはy座標の方向に+1/-1 だけ平行移動すると平行移動した座標に対応する和は +3/-3 する
中心を変えないまま他2つの石の位置を変えると、x 座標またはy座標の和が +2/-2 する

というわけで、x, y 座標の値の和と3つの石の位置を対応付ければ良さそうである。

x, y座標の値の和と、1回の操作で和がどのように変化するかをグラフで表したものが下の図である。

f:id:noimin:20201206213129p:plain

(グラフの画像は https://csacademy.com/app/graph_editor/ で作成)

一応、くの字の向きで塗り分け (囲み分け？) してある。

私の場合はこれだけ見ても立式できそうになかったので、範囲を限って必要な移動回数を手で求めてみた。

(0 のところが初期状態 $(0, 0), (0, 1), (1, 0)$ に対応する)

なんとなく法則性が見えてきた。座標の和が取りうる値 $\cdots, 0, 1, 2, 4, 5, \cdots$ を $\cdots, 0, 1, 2, 3, 4, \cdots$ のように対応づけ、その値を x, y 座標について $x^{\prime}, y^{\prime}$ とする。すると、多くの場合について必要な移動回数は $\max (\left| x^{\prime} \right|, \left| y^{\prime} \right|)$ となるが、$x^{\prime} = y^{\prime}$ の場合のみ $+1$ する必要があることがわかる (ただし $\max (x^{\prime}, y^{\prime})$ が 0 または 1 の場合を除く。)

あとは「座標の和が取りうる値 $\cdots, 0, 1, 2, 4, 5, \cdots$ を $\cdots, 0, 1, 2, 3, 4, \cdots$ のように対応づけ」の部分をコードに落とし込む。

座標の和が取りうる値は 0 以外は 3 で割ったときに (1 または 2 の) あまりが出る値なので、変換前の和を $x$ $y$ とすると

$x^{\prime} = \lfloor \frac{x}{3} \rfloor \times 2 + (x \%3 - 1) $

のようになる。 $y$ についても同様。

ただし、これをそのままコードにすると座標の値の和が負になったときに正しく計算できない。

たとえば C++ では (-1) / 3 のような計算は -1 ではなく 0 になる。今回の場合は割られる数が負でかつ割り切れない場合にはより絶対値の大きい方の値を出してほしいので、割られる数が負の数の場合のみ $2 = 3-1$ を引くことで調整している。また、負の余り $-2, -1$ はそれぞれ $1, 2$ に対応づけてほしいので、あまりが正となるような調整も入れている。

ソースコード

#include <iostream>
#include <algorithm>

using namespace std;

using ll =  long long;

void solve() {
    ll gx = 0, gy = 0, x, y;
    for(int i=0;i<3;++i) {
        cin >> x >> y;
        gx += x; gy += y;
    }

    ll xx = (gx + (gx < 0 ? -2 : 0)) /3 * 2 + ((gx%3 + 3) % 3 - 1);
    ll yy = (gy + (gy < 0 ? -2 : 0)) /3 * 2 + ((gy%3 + 3) % 3 - 1);
    ll ans = max(abs(xx), abs(yy));
    if(xx == yy) {
        if(xx >= 2 || xx < 0) {
            ++ans;
        }
    }
    cout << ans << endl;
}

int main() {
    int t;
    cin >> t;
    while(t--) solve();
}

所感

「和でくの字を区別できる」ことに気づくのが第一関門、実験をして法則性を見つけるところが第二関門。

私は本番では第一関門も突破できませんでした……。