제 2회 나나컵 후기

  • 장홍준
    장홍준

    대회 개요 : https://oj.uz/contest/view/NANA2
    대회 결과 : https://oj.uz/contest/scoreboard/NANA2

    안녕하세요.
    팀명 .으로 나나컵에 참가했던 hongjun7입니다.

    일반 알고리즘 문제 A, B, C, D와 마라톤 매치 느낌의 문제 E, F로 구성된 세트였습니다. ipsc 대회처럼 input 파일을 업로드 받아서 output 파일을 제출하는 식으로 진행되었습니다.

    저는 초반에 건드렸던 A와 중반부에 고민했던 D를 못풀고, B와 E를 풀고 대회를 마쳤습니다. 아래는 제가 풀었던 B번과 E번에 대한 제 방법입니다.

    B번. 영화 선택 - Easy 풀이

    문자열 S에서 연속하게 위치하는 0들에 대해 경우를 나누어 생각하면 됩니다. 단, 연속하게 위치하는 0들이 문자열 S가 시작하는 곳이나 끝나는 곳을 포함한다면 이동거리가 다른 것에 유의합니다.

    #include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
#define min(a, b) ((a)>(b)?(b):(a))
#define max(a, b) ((a)>(b)?(a):(b))
int T;
long long P, D, _a, _b;
char S[1000005];
int main() {
//  freopen("input.txt", "r", stdin);
//  freopen("output.txt", "w", stdout);
    for (scanf("%d", &T); T--;) {
        scanf("%s%lld", &S[1], &P);
        long long res = 1e18;
        D = strlen(S + 1);
        int cnt = 0, max = 0, r = 0, l = 0, r2 = 0, l2 = 0;
        long long cost = 0;
        for (int i = 1; i <= D; i++) cost += min((S[i] - '0'), 10 - (S[i] - '0'));
        int zero = 0;
        for (int i = 1; i <= D; i++) zero += S[i] == '0';
        if (zero == D) res = 0;
        else if (zero == 0) res = cost*P + D*P - 1;
        else {
            res = cost*P + D*P - 1;
            for (int i = 1; i <= D + 1; i++) {
                if (S[i] == '0') ++cnt;
                else if (cnt) {
                    r = i - 1, l = i - 1 - cnt + 1;
                    long long A1 = l - 1;
                    long long A3 = r - l + 1;
                    long long A2 = D - A1 - A3;
                    cnt = 0;
                    if (A1 >= 1) {
                        long long d1 = (A1 - 1) * 2LL + cost*P + (D*(P - 1)) + A2;
                        res = min(res, d1);
                    }
                    long long d2 = A2 * 2LL + cost*P + (D*(P - 1)) + (A1 - 1);
                    res = min(res, d2);
                    long long d3 = 1e18;
                    if (l == 1) d3 = D*(P - 1) + D - A3 + cost*P;
                    if (r == D) d3 = D*(P - 1) + D - A3 - 1 + cost*P;
                    res = min(d3, res);
                    cnt = 0;
                }
            }
        }
        printf("%lld\n", res + 1);
    }
//  fcloseall();
    return 0;
}

    E번. 부족전쟁 풀이

    처음에 다익스트라 비슷한 방식으로 접근했다가 번번이 0점이 나와서 randomized한 방식을 택해보기로 하였습니다. 1번 마을부터 시작하므로 방문하게 될 첫번째 마을부터 (n-1)번째 마을까지의 순서를 랜덤하게 섞습니다.
    i번째 마을을 어디서 방문할 것인지는, 그 전에 방문했던 마을들 중에서 가장 시간 순으로 가까운 마을(거리 순으로 가장 가까운 게 아니라)을 택해줍니다. n개의 마을을 다 방문하고 걸린 시간이 기존의 최적해보다 좋다면 갱신해주고 아니면 버립니다.
    이걸 n의 크기에 맞게 적당히 많이 반복해주니 상당히 좋은 해가 나왔습니다. 각 데이터에 대해 100번 정도 반복하고 제출했더니 216.51점이 나왔습니다.
    점수를 더 높이고자 첫번째 마을에서는 무조건 가장 먼 마을을 처음 방문하고 위의 방법을 반복해보니 오히려 더 나쁜 답을 구해서 대회가 끝나기 전까지 계속 위의 방법을 반복해주다보니 225.01점이 나왔습니다.

    #include <cstdio>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
#define MN 12000
const int Run = 200;
int n, past[MN];
double x[MN], y[MN], d[MN];
int seq[MN], R[MN];
vector <int> V[MN];
int main() {
//  freopen("input.txt", "r", stdin);
//  freopen("output.txt", "w", stdout);
    scanf("%d", &n);
    int v, g;
    for (int i = 1; i <= n; i++) scanf("%lf%lf", &x[i], &y[i]);
    double res = 1e16;
    for (int K = 1; K <= Run; K++) {
        for (int i = 1; i <= n; i++) seq[i] = i, d[i] = 0;
        for (int k = 1; k <= 5; k++) random_shuffle(seq + 2, seq + n + 1);
        int pn = 1;
        past[pn] = 1;
        double max = 0;
        for (int i = 2; i <= n; i++) {
            g = seq[i];
            int par;
            double min = 1e16;
            for (int j = 1; j <= pn; j++) {
                v = past[j];
                double cost = d[v] + 300.0 + sqrt((x[g] - x[v])*(x[g] - x[v]) + (y[g] - y[v])*(y[g] - y[v])) * 35;
                if (cost < min) min = cost, par = v;
            }
            d[g] = min;
            d[par] += 300.0;
            past[++pn] = g;
            if (d[g] > max) max = d[g];
        }
        if (res > max) {
            res = max;
            for (int i = 1; i <= n; i++) R[i] = seq[i];
        }
    }
    //과정 구하기 위해서 한 번 더
    for (int i = 1; i <= n; i++) seq[i] = R[i], d[i] = 0;
    int pn = 1;
    past[pn] = 1;
    for (int i = 2; i <= n; i++) {
        g = seq[i];
        int par;
        double min = 1e16;
        for (int j = 1; j <= pn; j++) {
            v = past[j];
            double cost = d[v] + 300 + sqrt((x[g] - x[v])*(x[g] - x[v]) + (y[g] - y[v])*(y[g] - y[v])) * 35;
            if (cost < min) min = cost, par = v;
        }
        d[g] = min;
        d[par] += 300.0;
        V[par].push_back(g);
        past[++pn] = g;
    }
//  printf("%lf\n", res);
    for (int i = 1; i <= n; i++) {
        printf("%d", V[i].size());
        if (V[i].size() > 0) {
            for (int j = 0; j < V[i].size(); j++) printf(" %d", V[i][j]);
        }
        puts("");
    }
//  fcloseall();
    return 0;
}

    F번은 코드를 다 작성하지 못하고 제출을 못했지만 뚜렷한 방법이 잘 떠오르지 않네요. 기타 다른 문제들에 대해서도 참가자분들은 어떻게 푸셨는지, 의도한 해법은 무엇인지 궁금합니다.
    좋은 문제들로 대회를 열어주신 일루님과 GENIUSainta 사이트 관계자분들께 감사드리며 이만 글을 마치겠습니다.


    9년 전
3개의 댓글이 있습니다.
  • kriii
    kriii

    감동적이네요..


    9년 전 link
  • 일루
    일루

    저는 마라톤 은퇴해야겠어요.. 전 못풀어서 점수를 그렇게 매긴건데 ㅠㅠ


    9년 전 link
  • VOCList
    VOCList

    저도 소소하게 후기탑승

    대회장에 와서 문제를 쭉 읽으니 A번은 뭔가 전날 문제랑 비슷한데 전날 문젤 안풀었으니 스킵. B번은 읽고 모르겠어서 스킵. C번은 B번 하드라길래 스킵. E번은 MM이길래 스킵. F번은 MM이길래 스킵.

    그래서...

    D짰습니당.

    ...

    작성한 코드가 이지는 통과하는데 하드데이터를 통과하질 못해서 나나님 솔루션이 틀렸다구 한참을 우기다 제 코드에 흔한 접선버그가.. 2바이트쯤 수정하구 패스했군여.

    이러고 나니 벌써 세시간쯤 지나서 그 다음엔 치킨치킨하고 콜라콜라하다 다른분들은 다들 B번을 푸셨더라구요. 저도 슥슥 그리디로 접근해보고 대회 끄읏.


    9년 전 link

  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.