はまやんはまやんはまやん

hamayanhamayan's blog

テトラへドロン [パソコン甲子園2020 予選 F]

https://onlinejudge.u-aizu.ac.jp/challenges/sources/PCK/Prelim/0433

解説

https://onlinejudge.u-aizu.ac.jp/solutions/problem/0433/review/5788439/hamayanhamayan/C++14

かなり複雑な問題で何から手を付けたものかという感じだと思うが、規則性を見つけていこう。

規則性

まずは、△型のタイルは少し扱いにくいし、答えるときもxy座標で答えるので例で与えられている配色を
普通のタイルに当てはめて眺めてみよう。

y=5  YGRBYGRBYGRBYGRBYGRB  
y=4  BRGYBRGYBRGYBRGYBRGY  
y=3  YGRBYGRBYGRBYGRBYGRB  
y=2  BRGYBRGYBRGYBRGYBRGY  
y=1  YGRBYGRBYGRBYGRBYGRB  
y=0  BRGYBRGYBRGYBRGYBRGY  

さて、これを見て、何か思う所がないだろうかということなのだが、ここから規則性を見つけ出せないと
解くのは難しい。
簡潔でなくても、ある程度使えそうな規則性が見つかればそれをうまく使って答えることができる。
今回自分が見つけた規則性について説明する。

規則性①

y座標の偶奇が同じものは全く同じパターンを持つ。
よって、y=0,2,4は同じような並びだし、y=1,3,5も同じような並び。
なので、y座標は2で割った余りを使ってy=0,1のどちらかに移した状態で答えてしまっていい。

y=1  YGRBYGRBYGRBYGRBYGRB  
y=0  BRGYBRGYBRGYBRGYBRGY  

規則性②

x座標に着目すると4個毎に同じパターンがどちらも連続している。
よって、x座標も4で割った余りにして考えてしまって問題ない。

y=1  YGRB YGRB YGRB YGRB YGRB  
y=0  BRGY BRGY BRGY BRGY BRGY  

みたいな感じだったのが、

y=1  YGRB  
y=0  BRGY  

だいぶ簡潔になった。
もう少し言うとy=1はy=0を左右ひっくり返した形になっているのでyの偶奇を見て、
必要ならひっくり返した状態で答えてあげればいいので、特徴点だけあえて取り出すと

y=0  BRGY  

これが連続しているような感じになる。

そして、この2つの規則性は初期の色が何であっても成り立つ性質となる。
ここまで分かれば、次に問題になるのが初期の色が2つ分かっているときにy=0のx=0..3の配色が分かれば
高速に答えが出せることになる。

初期配色

この部分を自分はgetTable関数で実装している。
ここが正直一番説明が難しい。
やり方は色々あると思う。

初期配色の組み合わせは12通りしかないので、最悪根性で書き上げてもいいが、
手動全列挙はケアレスミス紙一重であることを忘れてはいけない。
自分は多少の手間があっても全列挙部分を減らすように努力することを勧める。

自分の実装では三菱の形で色をメモっておいて特定する方法で実装した。
dic配列を手動で作って定義している。
dic[c] := 色cを中心としたときに以下のような順番で色を記録したもの

 2  
1c3  

ちょうど左下にこの図形が現れて1に当たるのがc1で、cに当たるのがc2になる。
よって、dic[c2]を使って、この配色を回転させながらc1が1になるとき、回転させてc1が2になるとき、
c1が3になるときをループで確認していって、色を探していく。
これで色が

 b  
acd  

のように特定できたら、y=0の状態に合わせるためにacdbの順番で答えてやれば目的の初期配置が得られる。

char c1, c2;
int N, x[101], y[101];
//---------------------------------------------------------------------------------------------------
string getTable() {
    map<char, string> dic;
    dic['R'] = "BYG";
    dic['G'] = "YBR";
    dic['B'] = "RGY";
    dic['Y'] = "GRB";

    string res = "";
    res += c1;
    res += c2;
    rep(i, 0, 3) if (dic[c2][i] == c1) {
        res += dic[c2][(i + 2) % 3];
        res += dic[c2][(i + 1) % 3];
    }
    return res;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> c1 >> c2;
    cin >> N;
    rep(i, 0, N) cin >> x[i] >> y[i];

    auto table = getTable();

    rep(i, 0, N) {
        x[i] %= 4;
        
        if (y[i] % 2 == 0) cout << table[x[i]] << endl;
        else cout << table[3 - x[i]] << endl;
    }
}