結果

問題 No.2719 Equal Inner Products in Permutation
ユーザー ecottea
提出日時 2025-02-03 03:29:02
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,761 bytes
コンパイル時間 658 ms
コンパイル使用メモリ 82,912 KB
実行使用メモリ 262,752 KB
最終ジャッジ日時 2025-02-03 03:29:45
合計ジャッジ時間 40,054 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 9 WA * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
import random
import math
import time

def calc_diff(P, N):
    """
    与えられた順列 P（長さ 3N）について，
      S1 = sum_{i=1}^{N} P[i] * P[N+i]
      S2 = sum_{i=1}^{N} P[N+i] * P[2N+i]
    の差の絶対値を返す．
    ※ Python の添字は 0 始まりなので，
       P[0..N-1] が最初のブロック，
       P[N..2*N-1] が 2 番目，
       P[2*N..3*N-1] が 3 番目のブロックとなる．
    """
    s1 = 0
    s2 = 0
    for i in range(N):
        s1 += P[i] * P[N + i]
        s2 += P[N + i] * P[2 * N + i]
    return abs(s1 - s2)

def simulated_annealing(N, time_limit=1.5):
    # 3N の順列 [1, 2, ..., 3N] から初期解（ランダムシャッフル）を作成
    size = 3 * N
    P = list(range(1, size + 1))
    random.shuffle(P)
    best = P[:]
    best_score = calc_diff(P, N)
    current = P[:]
    current_score = best_score

    # SA のパラメータ
    T = 1000.0          # 初期温度（適宜調整）
    cooling_rate = 0.9999
    start_time = time.time()

    while time.time() - start_time < time_limit:
        # ランダムに2箇所の位置を選び，交換
        i = random.randrange(size)
        j = random.randrange(size)
        # 交換候補
        current[i], current[j] = current[j], current[i]
        new_score = calc_diff(current, N)
        delta = new_score - current_score
        # 温度 T による確率的受容
        if delta <= 0 or random.random() < math.exp(-delta / T):
            current_score = new_score
            if new_score < best_score:
                best_score = new_score
                best = current[:]
                # 条件を満たすなら終了
                if best_score == 0:
                    return best
        else:
            # 交換を戻す
            current[i], current[j] = current[j], current[i]
        T *= cooling_rate
    return best

def main():
    # 標準入力から N を読み込む
    input_line = sys.stdin.readline().strip()
    if not input_line:
        return
    N = int(input_line)
    # N = 1 のときは解が存在しない
    if N == 1:
        print(-1)
        return

    # シミュレーテッド・アニーリングで探索
    # （時間制限は 1.5 秒程度に設定．必要に応じて調整してください．）
    sol = simulated_annealing(N, time_limit=1.5)
    if calc_diff(sol, N) != 0:
        # もし見つからなかった場合は，失敗したことを示す（実際の問題設定では解が存在するので通常はここに来ない）
        print(-1)
    else:
        # 解が見つかったら，リスト中の数字を空白区切りで出力
        print(" ".join(map(str, sol)))

if __name__ == '__main__':
    main()
0