Codeforces Round #259 (Div. 1): B. Little Pony and Harmony Chest

https://codeforces.com/problemset/problem/453/B

問題概要

N要素の正整数列Aが与えられる。すべての相異なる2要素が互いに素であるようなN要素の正整数列であって、Σ(abs(A[i]-B[i])) が最小となるような数列Bを構成せよ。

N <= 100

Ai <= 30

解法

相異なる2要素が互いに素であるという条件から「1は何回でも使える」「1以外の数は最大でも1回しか使えない」ことがいえる。またAiが最大でも30までという制約の小ささに注目すると、1が何回でも使えることからBに対して59以上の数は使う意味がないということがわかる(代わりに1を使えば必ずAとの差は小さくなるので)。さらに最小性の条件から、Bにおける各要素の大小関係はAと同じとしてよい(Ai > Aj かつ Bi < Bj だった場合、BiとBjをswapすれば必ず最終スコアは小さくなる)。また互いに素の条件から、ある数を使ったときそれとのGCDが1でない数は以降使えなくなる。使える数はたかだか60なのでどの数がもう使えないかは64bit型整数で管理することができる。

以上の条件をすべて踏まえると、【今見ているインデックス、使える数の最大値、もう使えない数のビットマスク、現在の差の合計】あたりの値をもってDFSで全探索していくことができ、制限時間も長いのでこれで十分間に合う。

感想

計算量がまったくわからない

参考にした記事

Codeforces #259 Div1 B. Little Pony and Harmony Chest - kmjp's blog

コード (D言語)

import std.stdio, std.array, std.string, std.conv, std.algorithm;
import std.typecons, std.range, std.random, std.math, std.container;
import std.numeric, std.bigint, core.bitop, core.stdc.stdio;

void main() {
    auto s = readln.split.map!(to!int);
    auto n = s[0];
    auto A = readln.split.map!(to!int).array;

    auto B = n.iota.map!(i => tuple(A[i], i)).array;
    B.sort!"a[0] > b[0]";

    auto C = new int[](n + 1);
    foreach (i; 0..n) C[i + 1] += C[i] + A[i];

    auto mask = new long[](60);
    foreach (i; 2..60) foreach (j; 2..60) if (gcd(i, j) != 1) mask[i] |= 1L << j;

    int[] ans;
    int[] tmp = new int[](n);
    tmp[] = 1;
    int minv = 1 << 29;

    void dfs(int idx, int num, long used, int val) {
        if (idx == n) {
            if (val < minv) {
                minv = val;
                ans = tmp.dup;
            }
            return;
        }
        if (num == 1) {
            int fval = val + C[n] - C[idx] - (n - idx);
            if (fval < minv) {
                minv = fval;
                ans = tmp.dup;
            }
            return;
        }
        foreach_reverse (v; 1..num+1) {
            if (used & (1L << v)) continue;
            tmp[B[idx][1]] = v;
            dfs(idx+1, max(1, v-1), used | mask[v], val + abs(B[idx][0] - v));
            tmp[B[idx][1]] = 1;
        }
    }

    dfs(0, 58, 0, 0);
    ans.map!(to!string).join(" ").writeln;
}