Approach 貪欲法 + 焼きなまし法を使いました。

  • 貪欲法
    • sub grid のパターンを繰り返す
  • 焼きなまし法
    • 点の数が0の状態から、無効な状態を許容する焼きなまし法をやってみたけど、有効な状態にするのが難しかった。sub grid のパターンを繰り返す貪欲法で有効な状態の初期解が作れることに気づいて、無効な状態を許容する焼きなまし法を諦めた。
    • 近傍1 : 点をフリップする(使う、使わないを入れ替える)
    • 近傍2 : 点をランダムに移動する(ある点を使わなくするのと同時に別の点を使う)
    • 近傍3 : 点を近くに移動する
      • sub grid で、使っている点の数が変化するものが減って、Kmin,Kmax の制約を違反することが少なくなって、探索空間がなだらかになります。
    • 温度管理、多スタート : ats さんの100回焼きなましても、1回の焼きなましの機能保つ手法を使いました。hakomo さんの多スタートの記事に期待。
    • 温度 : 2 -> 0 で線形に減少。Kmax-Kmin<=2 のときは 2.5 -> 0.2 で線形よりゆっくり減少させる。
    • 近傍選択の重み付け : (フリップ : ランダムに移動 : 近くに移動) = (1 : 1 : 1)。Kmax-Kmin<=2 のときは (1 : 1 : 10)。hakomo さんの近傍選択の重み付けの記事に期待。

感想 Kmax-Kmin>=3 のときは、最適解を出さないといけなくてきつかった。逆に Kmax-Kmin==1 のときは、999k以上の人でも、だいぶ差があると思う。例えば、H = 50, W = 50, h = 25, w = 25, Kmin = 311, Kmax = 312 のときは、私の焼きなまし法では、中央のほうが初期解から全く変化してなくて、もっと良くする余地がありました。
今回参加者が、100人を超えたのがよくわからなかった。
久しぶりに逆走するくらい余裕があった。





source code

pimport java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.PriorityQueue;

public class PointsOnGrid {
private int R;
private int C;
private int subR;
private int subC;
private int minK;
private int maxK;
private int[][] numbers;
private int[][] subGridToNumPoints;

private int numUsedPoints;

private boolean[][] used;
private double score;

private boolean[][] bestUsed;
private double bestScore;

static final XorShift rng = new XorShift(System.nanoTime());
static final Watch watch = new Watch();
private SAState sa = new SAState();

private int kR;
private int kC;

private int[] countAC = new int[10];
private int[] sumDeltaScore = new int[10];

private int n;

private IntSet usedPointSet;
private IntSet unusedPointSet;

public String[] findSolution(int H, int W, int h, int w, int Kmin, int Kmax, String[] grid) {
init(H, W, h, w, Kmin, Kmax, grid);
solve();
Utils.debug("countAC", countAC);
Utils.debug("sumDeltaScore", sumDeltaScore);
return makeSolution();
}

private void init(int H, int W, int h, int w, int Kmin, int Kmax, String[] grid) {
R = H;
C = W;
subR = h;
subC = w;
minK = Kmin;
maxK = Kmax;
numbers = new int[R][C];
for (int r = 0; r < R; r++) {
for (int c = 0; c < C; c++) {
numbers[r][c] = grid[r].charAt(c) - '0';
}
}
numUsedPoints = 0;
used = new boolean[R][C];
score = -1e9;
bestUsed = new boolean[R][C];
bestScore = -1e9;
kR = R - (subR - 1);
kC = C - (subC - 1);
subGridToNumPoints = new int[kR][kC];

usedPointSet = new IntSet(R * C);
unusedPointSet = new IntSet(R * C);
for (int r = 0; r < R; r++) {
for (int c = 0; c < C; c++) {
unusedPointSet.add(r * C + c);
}
}
}

private void solve() {
greedy();
if (maxK - minK <= 2) {
double numRestart = 100;
double startTemperature = 2.5;
double endTemperature = 0.2;
double startTime = watch.getSecond();
double endTime = 9.5;
sa.expTemperature = 0.25;
for (double restart = 0; restart < numRestart; restart++) {
sa.startTemperature = startTemperature + (endTemperature - startTemperature) * restart / numRestart;
sa.endTemperature = endTemperature;
sa.startTime = startTime + (endTime - startTime) * restart / numRestart;
sa.endTime = startTime + (endTime - startTime) * (restart + 1) / numRestart;
SA2();
loadBest();
}
} else {
double numRestart = 100;
double startTemperature = 2.0;
double endTemperature = 0;
double startTime = watch.getSecond();
double endTime = 9.5;
sa.expTemperature = 1;
for (double restart = 0; restart < numRestart; restart++) {
sa.startTemperature = startTemperature + (endTemperature - startTemperature) * restart / numRestart;
sa.endTemperature = endTemperature;
sa.startTime = startTime + (endTime - startTime) * restart / numRestart;
sa.endTime = startTime + (endTime - startTime) * (restart + 1) / numRestart;
SA();
loadBest();
}
}
Utils.debug("SA", "score", score, "time", watch.getSecondString());
}

private void greedy() {
PriorityQueue<Pair<Integer, Integer>> sumAndPointPairs = new PriorityQueue<>();
for (int r = 0; r < subR; r++) {
for (int c = 0; c < subC; c++) {
sumAndPointPairs.add(new Pair<Integer, Integer>(-sum(r, c), (r << 16) | (c)));
}
}

score = 0;
for (int i = 0; i < maxK; i++) {
Pair<Integer, Integer> pair = sumAndPointPairs.poll();
int v = pair.second.intValue();
int r0 = v >>> 16;
int c0 = v & ((1 << 16) - 1);
for (int r = r0; r < R; r += subR) {
for (int c = c0; c < C; c += subC) {
score += numbers[r][c];
used[r][c] = true;
updateK(r, c, 1);
numUsedPoints++;
addUsed(r, c);
}
}
}
saveBest();
Utils.debug("greedy", "score", score, "time", watch.getSecondString());
}

private int sum(int r0, int c0) {
int sum = 0;
for (int r = r0; r < R; r += subR) {
for (int c = c0; c < C; c += subC) {
sum += numbers[r][c];
}
}
return sum;
}

private void SA() {
sa.init();
for (;; ++sa.numIterations) {
if ((sa.numIterations & ((1 << 10) - 1)) == 0) {
sa.update();
if (sa.isTLE()) {
break;
}
}
mutate();
}
}

private void mutate() {
double random = 3 * rng.nextDouble();
if (random < 1) {
flip(0);
} else if (random < 2) {
moveRandom(1);
} else if (random < 3) {
moveNearPoint(2);
}
}

private void SA2() {
sa.init();
for (;; ++sa.numIterations) {
if ((sa.numIterations & ((1 << 10) - 1)) == 0) {
sa.update();
if (sa.isTLE()) {
break;
}
}
mutate2();
}
}

private void mutate2() {
double random = 12 * rng.nextDouble();
if (random < 1) {
flip(0);
} else if (random < 2) {
moveRandom(1);
} else if (random < 12) {
moveNearPoint(2);
}
}

private void moveRandom(int countIndex) {
if (numUsedPoints == 0) {
return;
}

int v = usedPointSet.get((int) (usedPointSet.size() * rng.nextDouble()));
int fromR = v / C;
int fromC = v % C;

v = unusedPointSet.get((int) (unusedPointSet.size() * rng.nextDouble()));
int toR = v / C;
int toC = v % C;

double deltaScore = numbers[toR][toC] - numbers[fromR][fromC];
if (sa.accept(deltaScore)) {

if (canAdd(toR, toC, fromR, fromC) && canRemove(fromR, fromC, toR, toC)) {
used[fromR][fromC] = false;
used[toR][toC] = true;

updateK(fromR, fromC, -1, toR, toC);
updateK(toR, toC, 1, fromR, fromC);

addUsed(toR, toC);
removeUsed(fromR, fromC);

score += deltaScore;

saveBest();

countAC[countIndex]++;
sumDeltaScore[countIndex] += deltaScore;
} else {
sa.validIterations--;
sa.acceptIterations--;
}

}
}

private void moveNearPoint(int countIndex) {
if (numUsedPoints == 0) {
return;
}

int fromR;
int fromC;
int toR;
int toC;
if (usedPointSet.size() <= unusedPointSet.size()) {
int v = usedPointSet.get((int) (usedPointSet.size() * rng.nextDouble()));
fromR = v / C;
fromC = v % C;

toR = Math.max(0, Math.min(R - 1, fromR - 1 + (int) (3 * rng.nextDouble())));
toC = Math.max(0, Math.min(C - 1, fromC - 1 + (int) (3 * rng.nextDouble())));
while (used[toR][toC]) {
toR = Math.max(0, Math.min(R - 1, toR - 1 + (int) (3 * rng.nextDouble())));
toC = Math.max(0, Math.min(C - 1, toC - 1 + (int) (3 * rng.nextDouble())));
}
} else {
int v = unusedPointSet.get((int) (unusedPointSet.size() * rng.nextDouble()));
toR = v / C;
toC = v % C;

fromR = Math.max(0, Math.min(R - 1, toR - 1 + (int) (3 * rng.nextDouble())));
fromC = Math.max(0, Math.min(C - 1, toC - 1 + (int) (3 * rng.nextDouble())));
while (!used[fromR][fromC]) {
fromR = Math.max(0, Math.min(R - 1, fromR - 1 + (int) (3 * rng.nextDouble())));
fromC = Math.max(0, Math.min(C - 1, fromC - 1 + (int) (3 * rng.nextDouble())));
}
}

double deltaScore = numbers[toR][toC] - numbers[fromR][fromC];
if (sa.accept(deltaScore)) {

if (canAdd(toR, toC, fromR, fromC) && canRemove(fromR, fromC, toR, toC)) {
used[fromR][fromC] = false;
used[toR][toC] = true;

updateK(fromR, fromC, -1, toR, toC);
updateK(toR, toC, 1, fromR, fromC);

addUsed(toR, toC);
removeUsed(fromR, fromC);

score += deltaScore;

saveBest();

countAC[countIndex]++;
sumDeltaScore[countIndex] += deltaScore;
} else {
sa.validIterations--;
sa.acceptIterations--;
}

}
}

private void flip(int countIndex) {
n++;
if (n >= R * C) {
n = 0;
}

int r = n / C;
int c = n % C;

double deltaScore = used[r][c] ? -numbers[r][c] : numbers[r][c];

if (sa.accept(deltaScore)) {
if ((used[r][c] && canRemove(r, c)) || (!used[r][c] && canAdd(r, c))) {
used[r][c] = !used[r][c];
updateK(r, c, used[r][c] ? 1 : -1);

numUsedPoints += used[r][c] ? 1 : -1;
if (used[r][c]) {
addUsed(r, c);
} else {
removeUsed(r, c);
}

score += deltaScore;

saveBest();

countAC[countIndex]++;
sumDeltaScore[countIndex] += deltaScore;

} else {
sa.validIterations--;
sa.acceptIterations--;
}
}
}

private void updateK(int r0, int c0, int value) {
int startR = Math.max(0, r0 - (subR - 1));
int startC = Math.max(0, c0 - (subC - 1));
int endR = Math.min(kR - 1, r0);
int endC = Math.min(kC - 1, c0);
for (int r = startR; r <= endR; r++) {
for (int c = startC; c <= endC; c++) {
subGridToNumPoints[r][c] += value;
}
}
}

private void updateK(int r0, int c0, int value, int r2, int c2) {
int startR = Math.max(0, r0 - (subR - 1));
int startC = Math.max(0, c0 - (subC - 1));
int endR = Math.min(kR - 1, r0);
int endC = Math.min(kC - 1, c0);

int startR2 = Math.max(0, r2 - (subR - 1));
int startC2 = Math.max(0, c2 - (subC - 1));
int endR2 = Math.min(kR - 1, r2);
int endC2 = Math.min(kC - 1, c2);

for (int r = startR; r <= endR; r++) {
for (int c = startC; c <= endC; c++) {
if (r >= startR2 && r <= endR2) {
if (c >= startC2 && c <= endC2) {
c = endC2;
continue;
}
}
subGridToNumPoints[r][c] += value;
}
}
}

private boolean canAdd(int r0, int c0) {
int startR = Math.max(0, r0 - (subR - 1));
int startC = Math.max(0, c0 - (subC - 1));
int endR = Math.min(kR - 1, r0);
int endC = Math.min(kC - 1, c0);
for (int r = startR; r <= endR; r++) {
for (int c = startC; c <= endC; c++) {
if (subGridToNumPoints[r][c] + 1 > maxK) {
return false;
}
}
}
return true;
}

private boolean canAdd(int r0, int c0, int r2, int c2) {
int startR = Math.max(0, r0 - (subR - 1));
int startC = Math.max(0, c0 - (subC - 1));
int endR = Math.min(kR - 1, r0);
int endC = Math.min(kC - 1, c0);

int startR2 = Math.max(0, r2 - (subR - 1));
int startC2 = Math.max(0, c2 - (subC - 1));
int endR2 = Math.min(kR - 1, r2);
int endC2 = Math.min(kC - 1, c2);

for (int r = startR; r <= endR; r++) {
for (int c = startC; c <= endC; c++) {
if (r >= startR2 && r <= endR2) {
if (c >= startC2 && c <= endC2) {
c = endC2;
continue;
}
}
if (subGridToNumPoints[r][c] + 1 > maxK) {
return false;
}
}
}
return true;
}

private boolean canRemove(int r0, int c0) {
int startR = Math.max(0, r0 - (subR - 1));
int startC = Math.max(0, c0 - (subC - 1));
int endR = Math.min(kR - 1, r0);
int endC = Math.min(kC - 1, c0);
for (int r = startR; r <= endR; r++) {
for (int c = startC; c <= endC; c++) {
if (subGridToNumPoints[r][c] - 1 < minK) {
return false;
}
}
}
return true;
}

private boolean canRemove(int r0, int c0, int r2, int c2) {
int startR = Math.max(0, r0 - (subR - 1));
int startC = Math.max(0, c0 - (subC - 1));
int endR = Math.min(kR - 1, r0);
int endC = Math.min(kC - 1, c0);

int startR2 = Math.max(0, r2 - (subR - 1));
int startC2 = Math.max(0, c2 - (subC - 1));
int endR2 = Math.min(kR - 1, r2);
int endC2 = Math.min(kC - 1, c2);

for (int r = startR; r <= endR; r++) {
for (int c = startC; c <= endC; c++) {
if (r >= startR2 && r <= endR2) {
if (c >= startC2 && c <= endC2) {
c = endC2;
continue;
}
}
if (subGridToNumPoints[r][c] - 1 < minK) {
return false;
}
}
}
return true;
}

private void saveBest() {
if (score > bestScore) {
bestScore = score;
for (int r = 0; r < R; r++) {
for (int c = 0; c < C; c++) {
bestUsed[r][c] = used[r][c];
}
}
}

}

private void loadBest() {
score = bestScore;
for (int r = 0; r < R; r++) {
for (int c = 0; c < C; c++) {
if (used[r][c] != bestUsed[r][c]) {
used[r][c] = bestUsed[r][c];
updateK(r, c, used[r][c] ? 1 : -1);

numUsedPoints += used[r][c] ? 1 : -1;
if (used[r][c]) {
addUsed(r, c);
} else {
removeUsed(r, c);
}
}
}
}
}

private void addUsed(int r, int c) {
int value = r * C + c;
usedPointSet.add(value);
unusedPointSet.removeValue(value);
}

private void removeUsed(int r, int c) {
int value = r * C + c;
usedPointSet.removeValue(value);
unusedPointSet.add(value);
}

private String[] makeSolution() {
String[] res = new String[R];
for (int r = 0; r < R; r++) {
StringBuilder sb = new StringBuilder();
for (int c = 0; c < C; c++) {
sb.append(bestUsed[r][c] ? "x" : ".");
}
res[r] = sb.toString();
}
return res;
}

public static void main(String[] args) {
try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {

int H = Integer.parseInt(br.readLine());
int W = Integer.parseInt(br.readLine());
int h = Integer.parseInt(br.readLine());
int w = Integer.parseInt(br.readLine());
int Kmin = Integer.parseInt(br.readLine());
int Kmax = Integer.parseInt(br.readLine());

String[] grid = new String[H];
for (int i = 0; i < H; i++)
grid[i] = br.readLine();

PointsOnGrid pog = new PointsOnGrid();
String[] ret = pog.findSolution(H, W, h, w, Kmin, Kmax, grid);

System.out.println(ret.length);
for (int i = 0; i < ret.length; ++i) {
System.out.println(ret[i]);
}
System.out.flush();
} catch (Exception e) {
e.printStackTrace();
}
}
}

class SAState {

public static final boolean useTime = true;

public double startTime = 0;
public double endTime = 1 * 9.5;
public double time = startTime;

public double startTemperature = 2;
public double endTemperature = 0;
public double inverseTemperature = 1.0 / startTemperature;
public double lastAcceptTemperature = startTemperature;
public double expTemperature = 1;

public double startRange = 15;
public double endRange = 0;
public double range = startRange;

public int numIterations;
public int validIterations;
public int acceptIterations;

private static final double[] log = new double[32768];
static {
for (int i = 0; i < log.length; i++) {
log[i] = Math.log((i + 0.5) / log.length);
}
}

public void init() {
numIterations = 0;
validIterations = 0;
acceptIterations = 0;

startTime = useTime ? PointsOnGrid.watch.getSecond() : numIterations;

update();
lastAcceptTemperature = inverseTemperature;
}

public void update() {
updateTime();
updateTemperature();
updateRange();
}

public void updateTemperature() {
inverseTemperature = 1.0 / (endTemperature + (startTemperature - endTemperature) * Math.pow((endTime - time) / (endTime - startTime), expTemperature));
}

public void updateRange() {
range = endRange + (startRange - endRange) * Math.pow((endTime - time) / (endTime - startTime), 1.0);
}

public void updateTime() {
time = useTime ? PointsOnGrid.watch.getSecond() : numIterations;
}

public boolean isTLE() {
return time >= endTime;
}

public boolean accept(double deltaScore) {
return acceptB(deltaScore);
}

public boolean acceptB(double deltaScore) {
validIterations++;

if (deltaScore > -1e-9) {
acceptIterations++;
return true;
}

assert deltaScore < 0;
assert 1.0 / inverseTemperature >= 0;

if (deltaScore * inverseTemperature < -10) {
return false;
}

if (log[PointsOnGrid.rng.nextInt() & 32767] < deltaScore * inverseTemperature) {
acceptIterations++;
lastAcceptTemperature = inverseTemperature;
return true;
}
return false;
}

public boolean acceptS(double deltaScore) {
validIterations++;

if (deltaScore < 1e-9) {
acceptIterations++;
return true;
}

assert deltaScore > 0;
assert 1.0 / inverseTemperature >= 0;

if (-deltaScore * inverseTemperature < -10) {
return false;
}

if (PointsOnGrid.rng.nextDouble() < Math.exp(-deltaScore * inverseTemperature)) {
acceptIterations++;
lastAcceptTemperature = inverseTemperature;
return true;
}
return false;
}

}

final class Utils {
private Utils() {
}

public static final void debug(Object... o) {
System.err.println(toString(o));
}

public static final String toString(Object... o) {
return Arrays.deepToString(o);
}

}

class Watch {
private long start;

public Watch() {
init();
}

public double getSecond() {
return (System.nanoTime() - start) * 1e-9;
}

public void init() {
init(System.nanoTime());
}

private void init(long start) {
this.start = start;
}

public String getSecondString() {
return toString(getSecond());
}

public static final String toString(double second) {
if (second < 60) {
return String.format("%5.2fs", second);
} else if (second < 60 * 60) {
int minute = (int) (second / 60);
return String.format("%2dm%2ds", minute, (int) (second % 60));
} else {
int hour = (int) (second / (60 * 60));
int minute = (int) (second / 60);
return String.format("%2dh%2dm%2ds", hour, minute % (60), (int) (second % 60));
}
}

}

class XorShift {
private int w = 88675123;
private int x = 123456789;
private int y = 362436069;
private int z = 521288629;

public XorShift(long l) {
x = (int) l;
}

public int nextInt() {
final int t = x ^ (x << 11);
x = y;
y = z;
z = w;
w = w ^ (w >>> 19) ^ (t ^ (t >>> 8));
return w;
}

public double nextDouble() {
return (nextInt() >>> 1) * 4.6566128730773926E-10;
}

public int nextInt(int n) {
return (int) (n * nextDouble());
}

}

class IntSet {
private static final int EMPTY = -1;
private int size;
private int[] indexToValue;
private int[] valueToIndex;

public IntSet(int capacity) {
this.size = 0;
indexToValue = new int[capacity];
valueToIndex = new int[capacity];
Arrays.fill(valueToIndex, EMPTY);
}

public boolean add(int value) {
if (valueToIndex[value] != EMPTY) {
return false;
}
indexToValue[size] = value;
valueToIndex[indexToValue[size]] = size;
size++;
return true;
}

public boolean remove(int index) {
if (size == 0) {
return false;
}
assert index < size;
int swap = indexToValue[index];
indexToValue[index] = indexToValue[size - 1];
indexToValue[size - 1] = swap;

valueToIndex[indexToValue[index]] = index;
valueToIndex[indexToValue[size - 1]] = EMPTY;

size--;
return true;
}

public boolean removeValue(int value) {
int index = indexOf(value);
if (index == EMPTY) {
return false;
}
remove(index);
return true;
}

public void swap(int index, int index2) {
assert index < size;
assert index2 < size;

int swap = indexToValue[index];
indexToValue[index] = indexToValue[index2];
indexToValue[index2] = swap;

valueToIndex[indexToValue[index]] = index;
valueToIndex[indexToValue[index2]] = index2;

}

public int get(int index) {
assert index < size;
return indexToValue[index];
}

public int indexOf(int value) {
return valueToIndex[value];
}

public int size() {
return size;
}

public boolean isEmpty() {
return size() <= 0;
}

public void clear() {
for (; size() > 0;) {
remove(0);
}
}

public boolean contains(int value) {
return indexOf(value) != EMPTY;
}

}

class Pair<T extends Comparable<T>, S> implements Comparable<Pair<T, S>> {
public T first;
public S second;

public Pair(T t, S s) {
this.first = t;
this.second = s;
}

private int hash = 0;

@Override
public int hashCode() {
if (hash == 0) {
final int prime = 31;
int result = 1;
result = prime * result + ((first == null) ? 0 : first.hashCode());
result = prime * result + ((second == null) ? 0 : second.hashCode());
hash = result;
}
return hash;
}

@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
Pair<T, S> other = (Pair<T, S>) obj;
if (first == null) {
if (other.first != null)
return false;
} else if (!first.equals(other.first))
return false;
if (second == null) {
if (other.second != null)
return false;
} else if (!second.equals(other.second))
return false;
return true;
}

@Override
public int compareTo(Pair<T, S> o) {
return first.compareTo(o.first);
}
}