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; }