BOJ 14448 - Subsequence Reversal 링크
(2023.08.21 기준 P2)

문제

N마리의 소들과 소들의 키가 주어지고, 사진을 찍기 위해 각 소들은 한 줄로 서있다.
가장 긴, 키가 감소하지 않는 부분 수열의 길이가 길수록 사진은 더 보기 좋아진다고 한다.
그리고 임의의 소들을 골라 한번만 순서를 뒤집을 수 있다.

가능한 가장 긴, 키가 감소하지 않는 부분 수열의 길이 출력

알고리즘

가장 긴 감소하지 않는 부분 수열은 LIS o(n log n). 그리고 담금질 기법

풀이

적합도를 가장 긴 감소하지 않는 부분 수열의 길이로 하여금 담금질 기법을 사용하면 된다.

임의의 인덱스 하나를 골라 뒤집는 상태를 반대로 바꾼다. 바꾼 후의 뒤집는 상태를 현재 유전자라고 하자.

현재 유전자의 적합도를 구해 이전 유전자의 적합도와 비교하면 된다.
비교하여 LIS의 길이가 증가했다면, 무조건 현재 유전자를 사용.
증가하지 않았다면, 현재 유전자의 부적합도(exp(이전 유전자와의 차이 / 온도))와 0~1 사이의 난수를 이용하여 확률적으로 현재 유전자를 사용할 지 정하면 된다.

이 행위를 온도 감률과 담금질 횟수를 적당히 조정 후, 시간 제한에 맞게 최대한 많이 반복하면 된다.

코드

• C++

#include <bits/stdc++.h>
using namespace std;

// 난수 설정
random_device rd;
mt19937 generator(rd());

int randint(int l, int r){
    return uniform_int_distribution<int> (l, r)(generator);
}

double random(int l, int r){
    return uniform_real_distribution<> (l, r)(generator);
}

int N;
vector<int> A;

int LIS(vector<int> A){
    vector<int> L = {A[0]};
    int I[N], idx = 1;
    fill(I, I + N, 0);
    for (int i = 1; i < N; i++){
        if (L.back() <= A[i]){
            I[i] = idx++;
            L.push_back(A[i]);
        }
        else{
            I[i] = lower_bound(L.begin(), L.end(), A[i]) - L.begin();
            L[I[i]] = A[i];
        }
    }
    return idx;
}

vector<int> flip(vector<int> A, vector<int> a){
    int l = 0, r = N - 1;
    while (l < r){
        if (a[l]){
            if (a[r]){
                swap(A[l], A[r]);
                l++; r--;
            }
            else r--;
        }
        else if (a[r]) l++;
        else{
            l++; r--;
        }
    }
    return A;
}

int solve(){
    int result, prev;
    result = prev = LIS(A); // 적합도
    vector<int> a(N); fill(a.begin(), a.end(), 0); // 뒤집을 원소 인덱스 및 이전 유전자
    double tk = 2.5; // 온도와 볼츠만 상수의 곱 (t = 1.0, k = 2.5)

    for (int _ = 0; _ < 2500; _++){
        vector<int> b; b.assign(a.begin(), a.end());
        b[randint(0, N - 1)] ^= 1; // 랜덤으로 뒤집을 인덱스 정하기 및 현재 유전자
        int now = LIS(flip(A, b)); // 현재 적합도

        // 현재 유전자를 쓸 확률을 구해야 한다.
        double p = exp((now - prev) / tk);
        // 이전 적합도보다 더 좋아졌으면 (현재 적합도가 더 높아졌으면)
        // 무조건 쓰게 되고
        // 아니면 확률적으로 쓸지 말지 결정하게 된다.

        if (p > random(0, 1)){ // 랜덤으로 0~1을 뽑아 현재 유전자를 쓸지 결정
            a.assign(b.begin(), b.end());
            prev = now;
        }

        result = max(result, now);
        tk *= 0.999; // 온도 감률
    }

    return result;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> N;
    A.resize(N);
    for (int i = 0; i < N; i++) cin >> A[i];

    int answer = 0;
    time_t st = time(0);
    while (time(0) - st < 1.8) // 시간 제한에 맞게 계속 돌린다.
        answer = max(answer, solve());
    cout << answer;
}

• Python

import sys; input = sys.stdin.readline
from math import exp
from time import time
from random import random, randint
from bisect import bisect_left

def LIS(A):
    L = [A[0]]
    I = [0] * N; idx = 1
    for i in range(1, N):
        if L[-1] <= A[i]:
            I[i] = idx
            idx += 1
            L.append(A[i])
        else:
            I[i] = bisect_left(L, A[i])
            L[I[i]] = A[i]
    return idx

def flip(A, a):
    l = 0; r = N - 1
    while l < r:
        if a[l]:
            if a[r]:
                A[l], A[r] = A[r], A[l]
                l += 1; r -= 1
            else:
                r -= 1
        elif a[r]:
            l += 1
        else:
            l += 1; r -= 1
    return A

def solve():
    result = prev = LIS(A) # 적합도
    a = [0] * N # 뒤집을 원소 인덱스 및 이전 유전자
    tk = 2.5 # 온도와 볼츠만 상수의 곱 (t = 1.0, k = 2.5)
    
    for _ in range(2500):
        b = a.copy()
        b[randint(0, N - 1)] ^= 1 # 랜덤으로 뒤집을 인덱스 정하기 및 현재 유전자
        now = LIS(flip(A.copy(), b)) # 현재 적합도
    
        # 현재 유전자를 쓸 확률을 구해야 한다.
        p = exp((now - prev) / tk)
        # 이전 적합도보다 더 좋아졌으면 (현재 적합도가 더 높아졌으면)
        # 무조건 쓰게 되고
        # 아니면 확률적으로 쓸지 말지 결정하게 된다.
    
        if p > random(): # 랜덤으로 0~1을 뽑아 현재 유전자를 쓸지 결정
            a = b.copy()
            prev = now
    
        result = max(result, now)
        tk *= 0.999 # 온도 감률
    
    return result

N = int(input())
A = [int(input()) for _ in range(N)]

answer = 0
st = time()
while time() - st < 6: # 시간 제한에 맞게 계속 돌린다.
    answer = max(answer, solve())
print(answer)