백준 15325번 Doktor

백준 15325번 Doktor

#include <iostream>

#include <string>

#include <vector>

#include <algorithm>

#define FOR(i, a, b) for (int (i) = (a); (i) < (b); i++)

#define REP(i, n) FOR(i, 0, n)

using namespace std;

 

const int MaxN = 1000100;

 

//everything is 1-indexed

 

int N;

int perm[MaxN];

vector <int> radii[2 * MaxN]; // center and radius are doubled

int prefFixedPoints[MaxN];

 

 

void findSegmentBounds(const int center, const int radius, int& left, int& right) {

    left = (center - radius) / 2;

    right = (center + radius) / 2;

}

 

int fixedPointsInSegment(int a, int b) { // [a, b]

    return prefFixedPoints[b] - prefFixedPoints[a - 1];

}

 

void precomputePrefFixedPoints() {

    //preFixedPonits[i]는 현재 고정점의 개수를 부분합으로 나타낸 배열입니다. 

    //3 2 4 1 의 경우에는 0 1 1 1 으로 

    //3 6 5 7 4 1 2 의 경우에는 0 0 0 0 0 0 0 으로 저장됩니다.

    for (int i = 1; i <= N; i++)

        prefFixedPoints[i] = prefFixedPoints[i - 1] + (perm[i] == i);

}

 

void findCenters() {

    for (int i = 1; i <= N; i++)

        radii[perm[i] + i].push_back(abs(perm[i] - i));

    

    for (int center = 2; center <= N + N; center++) { // 가능한 center들

        //sort로 정렬을 해주는 이유는 같은 센터의 경우 반지름이 크면 클수록 회전했을 때 얻을 수 있는 경우가 1씩 늘어나기 때문입니다.

        //회전했을때 잃는 고정점의 개수는 아직 고려하지 않았습니다.

        sort(radii[center].begin(), radii[center].end()); // the log in the complexity may be evaded by smart insertion

    }

}

 

void findBestFlip() {

    int targetMax = -MaxN, targetLeft = -1, targetRight = -1;

    for (int center = 2; center <= N + N; center++) {

        int numOfCreatedFixedPoints = 0;

        for (auto radius : radii[center]) {

            numOfCreatedFixedPoints++;

            int left, right;

            findSegmentBounds(center, radius, left, right);

            int numOfLostFixedPoints = fixedPointsInSegment(left, right);    //left,right 범위에서 뒤집으면 잃을 수 있는 고정점 개수

            int res = numOfCreatedFixedPoints - numOfLostFixedPoints; // 생성되는 고정점개수-없어지는 고정점개수 ->변경하여 얻어지는 고정점+/- 개수

            //고정점개수 이때까지 변경한 것중에서 최대로 만드는 범위 찾기

            if (targetMax < res) {

                targetMax = res;

                targetLeft = left;

                targetRight = right;

            }

        }

    }

 

    printf("%d %d\n", perm[targetLeft], perm[targetRight]);

}

 

void load() {

    scanf("%d", &N);

    for (int i = 1; i <= N; i++)

        scanf("%d", perm + i);

}

 

int main() {

    ios_base::sync_with_stdio(0);

    cin.tie(0);

    load();

    precomputePrefFixedPoints();

    findCenters();

    findBestFlip();

    return 0;

}

 

Colored by Color Scripter

cs

출처: Contest > Croatian Open Competition in Informatics > COCI 2017/2018 > Contest #2 3번

       https://www.acmicpc.net/problem/15324

이 코드는 Contest #2 대회 솔루션 코드입니다. 그대로 복사 해왔어요.

문제를 풀 때 회전축 의 경우가 

1. i 와 i+1 사이인 경우

2. i 인 경우

두가지를 모두 동시에 해결해서 풀 수 있는 간결한 코드입니다. 

이 코드를 참조해서 나중에 제가 코드 짜보고 첨부하겠습니다.