結果

問題 No.2029 Swap Min Max Min
ユーザー maspy
提出日時 2022-08-07 00:50:18
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
RE  
実行時間 -
コード長 1,263 bytes
コンパイル時間 246 ms
コンパイル使用メモリ 12,544 KB
実行使用メモリ 10,880 KB
最終ジャッジ日時 2024-09-16 18:46:28
合計ジャッジ時間 3,174 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample RE * 3
other RE * 42
権限があれば一括ダウンロードができます

ソースコード

diff # 

import itertools
from collections import deque

def solve(n, a):
    x = n // 2
    y = 0
    ind = []
    for i in range(n):
        if a[i] <= x:
            ind.append(i)
    if n % 2 == 1:
        for i, v in enumerate(ind):
            y += abs(v - (2 * i + 1))
    else:
        y1 = 0
        y2 = 0
        for i, v in enumerate(ind):
            y1 += abs(v - (2 * i + 1))
            y2 += abs(v - 2 * i)
        y = min(y1, y2)
    return x, y
    
def naive(N, A):
	# N! 状態の最短路
    dist = dict()
    que = deque()

    def add(x, d):
        if x not in dist:
            dist[x] = d
            que.append(x)

    add(A, 0)
    while que:
        A = que.popleft()
        for i in range(N - 1):
            B = list(A)
            B[i], B[i + 1] = B[i + 1], B[i]
            add(tuple(B), dist[A] + 1)
    X, Y = 10000, 0
    for A, y in dist.items():
        x = max(min(a, b) for a, b in zip(A, A[1:]))
        if X > x:
            X = x
            Y = y
        if X == x:
            Y = min(Y, y)
    return X, Y

# 2 <= N <= 6 という入力を全部チェック
for N in range(2, 6):
    for A in itertools.permutations(range(1, N + 1)):
        me = solve(N, A)
        ac = naive(N, A)
        assert me == ac, (N, A, me, ac)
0