CODE FESTIVAL 2017 qual A C - Palindromic Matrix

解けそうでWA出してたから、３日くらいかかってしまった。 これも一種のバケット方なのかも。

問題

全部の行、列が回文になっている回文行列を作れ、とのことです。

atcoder.jp

考えたこと

行列を全部回文にするので、H * Wの１マスを決めるとすると、プラス３マスは同時に決まる。 ４マスは一蓮托生になっている。

ここから除外されるのは、唯一真ん中の行（もしくは列）で、これは２マスともが同時に決まる。

最後に中央のマスは、１マスだけ、決めても他のマスが勝手に決まらない。

解説

真ん中の行（列）と中心マスは特殊ケースなので場合分けをする。

• a0 : 4つまとめて入れるべきマスの数
• a1 : 2つまとめて入れるべきマスの数
• a2 : ど真ん中のマスの個数（行列ともに奇数のときに１）

行列ともに偶数
　a1、a0 は0、a2はH*W

行列どちらかが奇数
　a1 は偶数側の長さ。
　a0 はH * W - a1、a2 は 0。

行列どちらとも奇数
　a1 は、（H - 1) + (W - 1)
　a2 は、１。 　a0 は、(H * W) - a1 - a2。

行列の文字数を数えておいて、１文字ずつグループに割り振って（a0 ~ a1から引いて）いき、最後にすべて０になっているか確認する。 このやり方だと、４の倍数個ある文字しかなかった場合に、本来２マスグループに割り振るものまで4マスグループに行くことがあるので、最後に調整する。

#include <bits/stdc++.h>

using namespace std;

#define rep(i,n)      for(long long(i)=0;(i)<(n);(i)++)

int main(){

    long h,w;
    cin >> h >> w;

    vector<string> s(h);
    rep(i,h) cin >> s[i];

    map<long,long> m;
    rep(i,h) rep(j,w) m[s[i][j]]++;

    long type = 0; // 0:両方偶数 1:片方奇数 2:両方奇数
    vector<long> a(3, 0);

    // 片方が奇数なら、hを奇数ということにする。
    if( (h + w) & 0x01 && !((h * w) & 0x01) ){
        type = 1;
        // 片方が奇数
        if(w & 0x01){
            swap(h,w);
        }
    } else if((h * w) & 0x01){
        // 両方奇数
        type = 2;
    }

    if(type == 1){
        a[1] = w;
    } else if(type == 2){
        a[1] = h - 1 + w - 1;
        a[2] = 1;
    }

    a[0] = h * w - a[1] - a[2];

    // いらない数を消して言く
    for(auto it : m){
        long buf = it.second - it.second % 4;
        a[0] -= buf;

        buf = it.second % 4;
        a[1] -= buf - buf % 2;

        buf = buf % 2;
        a[2] -= buf;
    }

    if(a[0] < 0){
        long buf = a[1];
        a[0] += buf;
        a[1] -= buf;
    }

    if(a[0] == 0 && a[1] == 0 && a[2] == 0){
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }

    return 0;
}

学んだこと

バケツの使い方が少し成長した気はしますね。 あとは混乱したときはコメント書いたりして丁寧にソースを書くといいなと思いました。

感想

AtCoderProblemsのBoot camp for Beginnersの残すはあと１問です。 ようやくチュートリアルが終わります。