Mister雑記

競プロやります。

AGC001-D 「Arrays and Palindrome」 (1000)

自力AC最高得点。

問題リンク

概要

総和 N、長さ Mの数列 Aが与えられる。これの順列 aについて、以下を満たすような bが存在するものがあれば a, bを両方とも出力せよ。

  •  bの総和は Nである。
  • 以下の2つを同時に満たす長さ Nの任意の文字列は全て同じ文字からなる。
    • 先頭から a_1文字、 a_2文字、...と区切ってできた部分文字列は全て回文である。
    • 先頭から b_1文字、 b_2文字、...と区切ってできた部分文字列は全て回文である。

制約

  •  1 \leq N \leq 10^5
  •  1 \leq M \leq 100

解説

まず、回文という条件は「対称の位置にある文字を同じにする一種の縛り」と見ることができる。 そこで「文字を頂点として同じ文字同士に辺が張られたグラフ」というのを考えると、「全ての文字が同じ」というのは「グラフが連結である」ことと同値になる。

f:id:misteer:20180915161616p:plain

これでUnion-Findなり使えばジャッジはできるようになったが、今回は構築の方なのでもっと深く考える必要がある。

まず M = 1のときを考えてみる。このとき、天下り的だが以下のように b = (N - 1, 1)とすれば上手いこと連結になる。

f:id:misteer:20180915161629p:plain

この発想は M \gt 1でも使える。というのも、右端の余った1頂点を使って隣に繋げればいい。

以下に隣の回文領域の頂点数が偶数の場合と奇数の場合を示す。見ての通り、偶数の場合は上手くいくのだが奇数の場合は上手くいかない。

f:id:misteer:20180915161641p:plain

実は両端以外に奇数頂点の回文領域がある場合は全体を連結にできない。というのも、全体を連結にするには辺の数が足りないのだ。

というわけで、奇数の要素数が3以上ならImpossibleを返し、そうでなければ奇数要素を両端に移動させて上の構築方法を実行すればいい。

実装例

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int N, M;
    cin >> N >> M;

    int a[M], odd = 0;
    for (int i = 0; i < M; ++i) {
        cin >> a[i];
        odd += a[i] % 2;
    }

    if (M == 1) {
        cout << a[0] << endl;
        if (a[0] == 1) {
            cout << 1 << endl;
            cout << a[0] << endl;
        } else {
            cout << 2 << endl;
            cout << a[0] - 1 << " " << 1 << endl;
        }
        return 0;
    }

    // 可能性判定
    if (odd > 2) {
        cout << "Impossible" << endl;
        return 0;
    }

    // 奇数要素を両端に持っていく
    odd = 0;
    for (int i = 0; i < M; ++i) {
        if (a[i] % 2 == 1) {
            ++odd;
            if (odd == 1) {
                swap(a[i], a[0]);
            } else if (odd == 2) {
                swap(a[i], a[M - 1]);
            }
        }
    }

    // 数列aを出力
    for (int i = 0; i < M; ++i) {
        if (a[i] > 0) {
            cout << a[i] << " ";
        }
    }
    cout << endl;

    // 数列bを構築
    vector<int> b;

    --a[0];
    ++a[M - 1];
    for (int i = 0; i < M; ++i) {
        // 0を出力してはいけないことに注意
        if (a[i] > 0) b.push_back(a[i]);
    }

    // 数列bを出力
    cout << b.size() << endl;
    for (int c : b) {
        cout << c << " ";
    }
    cout << endl;
    return 0;
}

上では複雑な話をしたが、要はaの先頭を1減らして末尾を1増やすだけで構築できてしまう。実装自体は非常に軽い。

類題の話

この問題と傾向が似てる問題として、ARC048-C「足の多い高橋君」が挙げられる。 アブノーマルな問題設定で有名な問題だが、この問題同様「どれが同じ文字になるか」を考えるのが鍵となる(多分)。

感想

  • 運良く方針が正解へ向いていた。
  • 回文をグラフと見るのは結構重要な発想かもしれない。
  • 今夜のAGCもこれくらい調子が良いといいなぁ。