tags: HUPC2021

E - 正四面体転がし 解説

原案: olphe, Nerve | 解説: Nerve

黒い面が底面に来るマスを黒マスと表すことにします。
まず、どのような経路で移動しても黒マスの集合は変化しません。

$(i_g,j_g,k_g)$ が黒マスである条件を考えます。

$(i_s,j_s,k_s)$ から最も近い黒マスは、対頂角を含む向かい側の3マスです。
同様に、これらの黒マスの対頂角を含むマスも全て黒マスであり、この操作によって下図のような黒マスの集合が得られます。

実は上記の操作で得られた黒マスの集合が座標全体の黒マスの集合と一致します。
これは以下の性質から示せます。

• 黒マスと隣接するマスは黒マスにならない
• 上記の操作で得られた黒マス以外のマスは必ずいずれかの黒マスと隣接している

あとは得られた黒マスの集合に

$(i_g,j_g,k_g)$ が含まれるか判定をすればよいです。

三角の黒マスから最近の逆三角の黒マス3つへ行くには

$(-1,+1,+1),(+1,-1,+1),(+1,+1,-1)$、
逆三角の黒マスから最近の三角の黒マス3つへ行くには

$(+1,-1,-1),(-1,+1,-1),(-1,-1,+1)$
だけ移動することで辿りつくことができます。

つまり、

$(i_s,j_s,k_s)$ からこの移動を繰り返すことで辿りつくことができる黒マスの座標は

$(i_s+2a,j_s+2b,k_s+2c)$ か

$(i_s+2a+1,j_s+2b+1,k_s+2c+1)(a,b,c\mathrm{は}\mathrm{整}\mathrm{数},\mathrm{各}\mathrm{軸}\mathrm{の}\mathrm{和}\mathrm{は}0\mathrm{か}1)$
と表すことができます。
逆に、このように表せる座標で黒マスでないマスは存在しません。

この条件を簡潔に表すと、

$|i_s-i_g|,|j_s-j_g|,|k_s-k_g|$ について、各値が全て奇数または全て偶数ならYes、そうでないならNoになります。

また、制約から正四面体を転がすシミュレーションを書いて解くこともできます。

以下実装例

#include <bits/stdc++.h>
using namespace std;

int main(){
    int is, js, ks, ig, jg, kg;
    cin >> is >> js >> ks >> ig >> jg >> kg;
    int iodd = abs(is - ig) & 1, jodd = abs(js - jg) & 1, kodd = abs(ks - kg) & 1;
    if (iodd == jodd and jodd == kodd)
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
}