mayoko’s diary

プロコンとかいろいろ。

SRM 487 div1 med: BunnyExam

解法

答えが -1 でないとすると, 答えは m/k となります。

答えが -1 でない時, RandomAnser は 1 〜 k の答えを等確率で出力します(x 番目の答えとして選ばれる数字は 1 〜 k すべて等確率であり得る。対称性から言える)。これらはすべて独立なので, RandomAnser の x 番目に対する正答確率は 1/k です。

上のように考えると, すべての問題は独立に正解/不正解が決まるので, 答えは m/k です。

ということで, 答えが -1 になるかならないかという, Yes/No 問題であることがわかりました。

linkage にあるような情報に矛盾がないかを確かめるのは, グラフ彩色問題に帰着します。
この問題の場合, i 問目と i+1 問目の答えが異なるので, 頂点 i と 頂点 i+1 の間に辺を引くと, 「隣接した頂点は色が異なるように, たかだか k 色の色でグラフを塗れるか」という問題ですね。
あと, この問題では linkage の情報で「i と j は同じ色になる」という情報もあります。こちらは, 「i と j を同じ頂点にする」と解釈すれば良いです。

この問題では, 上のようにして作ったグラフは, すべての頂点の次数はたかだか 4 です。なので, k >= 5 の場合は, 明らかにグラフを塗れます(隣接する頂点の色と異なる色を必ず選べるので)。後は k=1, 2, 3, 4 ですね。

k = 1, k = 2 の場合は単純で, k=1 の時は m=1 かどうかで判定できます。k=2 の時は 0, 1, 0, 1, ... というような解答しかありえないので, linkage[2*i], linkage[2*i+1] の偶奇がすべて一致しているかどうかで判定できます。

k = 3, k = 4 の場合は単純ではないですが, m が大きい場合殆どの頂点が次数 2 であることを考えると, 次数 3 の頂点のみで構成されたグラフで, グラフを彩色出来るかどうか, という問題と同じになります(次数 3 のグラフだけ考えた時点で彩色できないなら当然グラフ全体の彩色も出来ない。逆に, 次数 3 のグラフだけで彩色出来たとすると, 次数 3 の頂点の間に存在する次数 2 の各頂点は, 必ず 3 色以内で彩色することが出来る)。

次数 3 になる頂点の候補は linkage に出てきた頂点しかなく, これらの頂点はたかだか 20/2 = 10 個しかないので, 色の塗り方について全探索すればよいでしょう。O(3^(n/2)) ないし O(4^(n/2)) で計算できます。

bool adjacent[12][12];
int color[12];

bool dfs(int now, int k, int n) {
    if (now == n) return true;
    for (int i = 0; i < k; i++) {
        bool ng = false;
        for (int j = 0; j < n; j++) {
            if (adjacent[now][j] && color[j] == i) ng = true;
        }
        if (ng) continue;
        color[now] = i;
        if (dfs(now+1, k, n)) return true;
        color[now] = -1;
    }
    return false;
}

bool ok(int m, int k, vi linkage) {
    int n = linkage.size();
    n /= 2;
    if (k == 1) return (m==1);
    if (k == 2) {
        for (int i = 0; i < n; i++) {
            if (linkage[2*i]%2 != linkage[2*i+1]%2) return false;
        }
        return true;
    }
    memset(adjacent, false, sizeof(adjacent));
    for (int i = 0; i < n; i++) {
        int x1 = linkage[2*i], y1 = linkage[2*i+1];
        for (int j = 0; j < n; j++) {
            int x2 = linkage[2*j], y2 = linkage[2*j+1];
            if (abs(x1-x2) == 1 || abs(x1-y2) == 1 || abs(y1-x2) == 1 || abs(y1-y2) == 1) adjacent[i][j] = true;
        }
    }
    for (int i = 0; i < n; i++) if (adjacent[i][i]) return false;
    if (k >= 5) return true;
    memset(color, -1, sizeof(color));
    return dfs(0, k, n);
}

class BunnyExam {
public:
    double getExpected(int m, int k, vector <int> linkage) {
        if (ok(m, k, linkage)) return 1.*m/k;
        else return -1;
    }
};