提出 #42966479

---

ソースコード 拡げる

# 27 位解法を整形

# ----- 方針 -----
# 入れ替えは上下のみ
# 小さい番号のボールから昇順に決める
# 各ボールについて、確定位置（右上と左上が確定している）まで動かす方法がいくつかあるが、
# その中で最も評価が高いものを選ぶ
# イメージ的には、なるべく大きい番号のボールの上を通るものを高評価にしている
# 逐次更新はなしで、パラメータを変えて試して一番良い結果を選んでいる

# ----- 評価関数 -----
# 評価関数は、通る道にある玉の番号を a_i とすると Σ a_i ^ e / l
# l は道の長さ（交換回数）
# e は 0.4 ≦ e ≦ 1.1 ぐらいを適当に動かす
# なお更新は 2 次元 DP でできる

# ----- e の範囲の根拠 -----
# 番号 i のボールの「適正位置」は √2i ぐらいなので、この意味では e ≒ 0.5 にするのが良さそう
# 単純合計（e ≒ 1.0）との間付近を雑に選んでいる


from time import time
from math import sqrt
sTime = time()
N = 30
M = N * (N + 1) // 2
origX = [[int(a) for a in input().split()] for _ in range(N)]
origIX = [(0, 0)] * M
for i in range(N):
    for j in range(i + 1):
        origIX[origX[i][j]] = (i, j)

BEST_ANS = []
for exp_start_100 in range(40, 111, 2):
    for exp_end_100 in range(40, 111, 3):
        if time() - sTime > 1.8:
            break
        
        X = [x[:] for x in origX]
        IX = origIX[:]
        fixed = [[0] * (i + 1) for i in range(N)]
        for i in range(N):
            fixed[i][0] += 1
            fixed[i][i] += 1
        row_remaining_count = [i + 1 for i in range(N + 1)]
        done_row_count = 0
        DP = [[0] * (i + 1) for i in range(N)] # Reusable Table
        ANS = []
        for a in range(M):
            exp = exp_start_100 / 100 + (exp_end_100 - exp_start_100) / 100 * sqrt(a) / sqrt(M)
            ii, jj = IX[a]
            DP[ii][jj] = 100000 * (a + 1) # DP テーブルを毎回初期化しなくて良いように適当に足している
            ma = 0
            mai = ii
            maj = jj
            for i in range(ii - 1, done_row_count - 1, -1):
                DPi = DP[i]
                DPi1 = DP[i+1]
                Xi = X[i]
                fixedi = fixed[i]
                for j in range(max(0, jj - (ii - i)), min(i + 1, jj + 1)):
                    evaluation = Xi[j] ** exp # ← 評価関数
                    DPi[j] = max(DPi1[j], DPi1[j+1]) + evaluation
                    if fixedi[j] == 2:
                        perf = (DPi[j] - 100000 * (a + 1)) / (ii - i) # 評価合計 ÷ 移動回数が高いものを優先
                        if perf > ma:
                            ma = perf
                            mai = i
                            maj = j
            
            i, j = mai, maj
            L = [(i, j)]
            if i + 1 < N:
                fixed[i][j] += 1
                fixed[i+1][j] += 1
                fixed[i+1][j+1] += 1
            row_remaining_count[i] -= 1
            while row_remaining_count[done_row_count] == 0:
                done_row_count += 1
            while i < ii:
                i += 1
                if DP[i][j] < DP[i][j+1]:
                    j += 1
                L.append((i, j))

            for k in range(len(L) - 1)[::-1]:
                i1, j1 = L[k]
                i2, j2 = L[k+1]
                ANS.append((i1, j1, i2, j2))
                X[i1][j1], X[i2][j2] = X[i2][j2], X[i1][j1]
                IX[X[i1][j1]] = (i1, j1)
                IX[X[i2][j2]] = (i2, j2)

        if not BEST_ANS or len(ANS) < len(BEST_ANS):
            BEST_ANS = ANS
    
ANS = BEST_ANS
print(len(ANS))
for ans in ANS:
    print(*ans)

提出情報

ジャッジ結果