codeforce 1600

COFO::1476C Longest Simple Cycle

cofo problem

COFO::1476C Longest Simple Cycle

Problem

Point

Design

Thought process

open/close 
DP ? GREEDY ?
. a[i] == b[i] 인 곳을 기준으로 simple cycle 의 계속 나눠지나?
. a[i] == b[i] 인 곳이 없으면 전체가 하나인듯 ( TC2 )

. 각 cycle 내에서도 어떤 선분을 선택할지에 따라서 값이 달라질 수 있음 ( TC 3 )


1. 일단, a[i] == b[i] 인 곳을 기준으로 cycle 을 구분하고
	. 이건 쉬울 것 같고
2. 각 cycle 내에서 최대 길이를 찾는다.
	. 이걸 좀 생각해봐야함
	. chain le 부터 ri 까지 하나의 cycle 이라고 하자.
		. 이때 이 cycle 내에서 최대 길이를 갖는 cycle 을 구하는 방법은?
			. le <= i < j <= ri 를 만족하는 i, j 를 고른다.
			. len = c[i] + c[j] 
				+ ( prefUpper[j] - prefUpper[i-1] )
				+ ( prefLower[j] - prefLower[i-1] )
			
			. 하지만, 이처럼 하면 i 와 j 를 선택해야하므로 O(N^2) 으로 TLE 예상
			. 다 try 안해봐도 답을 알 수 있어야함
			. 어떻게 다 안해볼 수 있지? 
				. two-pointer 같은걸로 지나가면서 슥- 구할 수 있나 O(N) 에 ?
				. 각 i 마다 최대 len 을 갖게하는 j 를 logN 만에 구할 수 있나 ?
					. 구간 [i, ri] 까지의 pref + c[x] 의 값이 구해져서 정렬되어있어야가능
						. 즉, 안될듯 
		. DP 로는 안되나? 
			. dp[i] : c[i] 를 오른쪽 끝 chain으로 하는 cycle 구간의 최대합
			
			for (int i = 0; i < n; i++) {
				if (dp[i-1] - c[i-1] + c[i] + (a[i]) + (c[i-1] - b[i] + 1) > dp[i] )
					dp[i] = dp[i-1] - c[i-1] + c[i] + (a[i]) + (c[i-1] - b[i] + 1);
				else dp[i] = dp[i-1];
			}
			
		. 그냥 단순하게 가장 큰 cycle 을 찾고.
			. 이 안에서, 좌 -> 우 방향으로 가면서
			. 그냥 two-pointer ?
			. Nope
			. 현재 구간이 [le, ri] 라고 해보자.
				. ri + 1 하는 것이 이득인 경우
				. le + 1 하는 것이 이득인 경우
				. else
					. 이 경우에 어떻게 해야하는지? 에 대한 solution이 없음
					. 현 위치에서 우로 1칸 가는 경우가 현위치보다 이득이지 않다고해서,
					  현위치에서 우로 2칸 가는 경우가 현위치보다 이득이지 않을까?! 
					  -> 해보기 전까진 모르는 것
					 -> 즉, DP 로 모든 경우를 해보는 수밖에 없는 문제임
					
					=> maxium subarray sum 관점에서 보면, 이 경우엔 그냥 sum = arr[i] 로 두고 새로 시작해야함

Complexity

Code

#include<bits/stdc++.h>
#define fi first
#define se second
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define rep(i, a, b) for(int i = (a); i <(b); i++)
#define r_rep(i, a, b) for(int i = (a); i >(b); i--)
typedef long long ll;
using namespace std;

int t;
void solve() {
    int n; cin >> n;
    vector<int> c(n + 1); rep(i, 1, n + 1) cin >> c[i];
    vector<int> a(n + 1); rep(i, 1, n + 1) cin >> a[i];
    vector<int> b(n + 1); rep(i, 1, n + 1) cin >> b[i];
    ll ans = 0;
    ll prevLen = 0;
    // i 지점을 우측변으로 하는 사각형으로 새로 시작하던지
    // i 지점을 우측변으로 하는 i-1 이전부터 이어져온 사각형을 유지하던지
    // 이게 어떻게 모든 경우를 cover 하지?
    //          (le, ri)
    // 새로시작된게 아니라면, 무조건 끌고가는건데,,
    
    // 알겠다.
    // 모든 지점에서 사각형을 만들어서 우측으로 출발시킴.
    // 그리고 현재 지점에서 판단하는 것.
    // 이전에 현재 지점 이전에 모든 사각형이 시작되었었음 (le fix)
    // 그리고 그 중 하나가 현재 지점까지 끌고와졌다면, 하나더 linking 하는 것을 고려하는 것
    // 즉, 모든 지점에서 출발시킨 결과물이 curLen = max(,) 에 반영됨.
    // 우리는 이게 어떤 지점에서 출발했는지엔 관심이 없고, 길이만 구하면 되니까 이렇게 풀 수 있는 것
    rep(i, 2, n + 1) {
        ll curLen = c[i] + abs(a[i] - b[i]) + 1LL;
        if (a[i] != b[i])
            curLen = max(curLen, c[i] + prevLen - abs(a[i] - b[i]) + 1LL);
        ans = max(ans, curLen);
        prevLen = curLen;
    }
    
    cout << ans << '\n';
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    
    int tc; cin >> tc; while(tc--)
        solve();
    return 0;
}