結果

問題 No.2029 Swap Min Max Min
ユーザー maspymaspy
提出日時 2022-08-07 00:50:18
言語 Python3
(3.12.2 + numpy 1.26.4 + scipy 1.12.0)
結果
RE  
実行時間 -
コード長 1,263 bytes
コンパイル時間 302 ms
コンパイル使用メモリ 11,036 KB
実行使用メモリ 8,596 KB
最終ジャッジ日時 2023-10-15 01:15:08
合計ジャッジ時間 3,521 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 RE -
testcase_01 RE -
testcase_02 RE -
testcase_03 RE -
testcase_04 RE -
testcase_05 RE -
testcase_06 RE -
testcase_07 RE -
testcase_08 RE -
testcase_09 RE -
testcase_10 RE -
testcase_11 RE -
testcase_12 RE -
testcase_13 RE -
testcase_14 RE -
testcase_15 RE -
testcase_16 RE -
testcase_17 RE -
testcase_18 RE -
testcase_19 RE -
testcase_20 RE -
testcase_21 RE -
testcase_22 RE -
testcase_23 RE -
testcase_24 RE -
testcase_25 RE -
testcase_26 RE -
testcase_27 RE -
testcase_28 RE -
testcase_29 RE -
testcase_30 RE -
testcase_31 RE -
testcase_32 RE -
testcase_33 RE -
testcase_34 RE -
testcase_35 RE -
testcase_36 RE -
testcase_37 RE -
testcase_38 RE -
testcase_39 RE -
testcase_40 RE -
testcase_41 RE -
testcase_42 RE -
testcase_43 RE -
testcase_44 RE -
権限があれば一括ダウンロードができます

ソースコード

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