Approach 貪欲法を使いました。

  • 各ターン 4.5/K 秒間で見つかった最も良い増減を適用する。
  • length = 1,2,... と増やしていって、最もスコアを改善するペアを見つける。
  • 動かす量 v は、 min ( min( A[i+a] - (i+a+1) ) , min( (k+a+1) - A[k+a] ) )  for (a = 0,1,...,length) と、これに 2000 加えたもの。

source code

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

public class Main {
private int N;
private int K;
private int[] A;

private int[] is;
private int[] js;
private int[] ks;
private int[] ls;
private int[] vs;

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

public static void main(String[] args) {
new Main().run();
}

private void run() {
readProblem();
solve();
writeSolution();
}

private void readProblem() {
try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {
String line = br.readLine();
String[] split = line.split(" ");
N = Integer.parseInt(split[0]);
K = Integer.parseInt(split[1]);
A = new int[N];
for (int i = 0; i < N; i++) {
A[i] = Integer.parseInt(br.readLine());
}

is = new int[K];
js = new int[K];
ks = new int[K];
ls = new int[K];
vs = new int[K];

} catch (Exception e) {
e.printStackTrace();
}
}

private void solve() {
greedy();
Utils.debug("score", calculateScore(), "time", watch.getSecondString());
Utils.debug("score", 1e9 - calculateScore(), "time", watch.getSecondString());
Utils.debug("score", 41e9 - 41 * calculateScore(), "time", watch.getSecondString());
}

private void greedy() {
double startTime = watch.getSecond();
for (int k = 0; k < K; k++) {

long best = (long) 1e9;
int besti = 0;
int bestj = 0;
int bestk = 1;
int bestl = 1;
int bestv = 0;
{
long score = calculateScore();
if (score < best) {
best = score;
}
}
for (int numIterations = 0;; numIterations++) {

int length = numIterations;
int bestIValue = (int) -1e9;
int bestI = -1;
int bestKValue = (int) -1e9;
int bestK = -1;
for (int i = 0; i + length < N; i++) {
int minI = (int) 1e9;
int minK = (int) 1e9;
for (int j = 0; j <= length; j++) {
minI = Math.min(minI, A[i + j] - (i + j + 1));
minK = Math.min(minK, (i + j + 1) - A[i + j]);
}
if (minI * (length + 1) > bestIValue) {
bestIValue = minI * (length + 1);
bestI = i;
}
if (minK * (length + 1) > bestKValue) {
bestKValue = minK * (length + 1);
bestK = i;
}
}
int i2 = bestI;
int j2 = i2 + length;
int k2 = bestK;
int l2 = k2 + length;
is[k] = i2;
js[k] = j2;
ks[k] = k2;
ls[k] = l2;
for (int plusAlpha = 0; plusAlpha < 2; plusAlpha++) {
vs[k] = Math.min(bestIValue / (length + 1), bestKValue / (length + 1));
if (plusAlpha > 0) {
if (watch.getSecond() - startTime >= 4.5 * (k + 1) / K) {
Utils.debug(k, numIterations, "best", best, "time", watch.getSecondString());
break;
}
vs[k] += 2000;
}
if (isValid(k)) {
next(k);
long score = calculateScore();
if (score < best) {
best = score;
besti = is[k];
bestj = js[k];
bestk = ks[k];
bestl = ls[k];
bestv = vs[k];
}
previous(k);
}
}

if (watch.getSecond() - startTime >= 4.5 * (k + 1) / K) {
Utils.debug(k, numIterations, "best", best, "time", watch.getSecondString());
break;
}
}
is[k] = besti;
js[k] = bestj;
ks[k] = bestk;
ls[k] = bestl;
vs[k] = bestv;
if (isValid(k)) {
next(k);
}

}
}

private void next(int k) {
int v = vs[k];
for (int i = is[k]; i <= js[k]; i++) {
A[i] -= v;
}
for (int i = ks[k]; i <= ls[k]; i++) {
A[i] += v;
}
}

private void previous(int k) {
int v = vs[k];
for (int i = is[k]; i <= js[k]; i++) {
A[i] += v;
}
for (int i = ks[k]; i <= ls[k]; i++) {
A[i] -= v;
}
}

private boolean isValid(int k) {
if (vs[k] < 0 || vs[k] >= N) {
return false;
}

if (is[k] > js[k]) {
return false;
}
if (ks[k] > ls[k]) {
return false;
}

if (js[k] - is[k] != ls[k] - ks[k]) {
return false;
}

for (int i = is[k]; i <= js[k]; i++) {
if (A[i] - vs[k] <= 0) {
return false;
}
}
for (int i = ks[k]; i <= ls[k]; i++) {
if (A[i] + vs[k] > N) {
return false;
}
}
return true;
}

private void writeSolution() {
for (int k = 0; k < K; k++) {
is[k]++;
js[k]++;
ks[k]++;
ls[k]++;
}

for (int k = 0; k < K; k++) {
System.out.println(is[k] + " " + js[k] + " " + ks[k] + " " + ls[k] + " " + vs[k]);
}
System.out.flush();
}

private long calculateScore() {
long score = 0;
for (int i = 0; i < N; i++) {
score += Math.abs(A[i] - (i + 1));
}
return score;
}
}

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 long nextLong() {
return ((long) nextInt() << 32) ^ (long) nextInt();
}

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

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

}