문제 분석

4시간 짜리인만큼, 입력은 단순했다. N = 6 / M = 15 / T = 10 고정. N은 밭은 크기, M은 Feature의 크기, T는 Turn의 수이다.

이렇게 밭에 심은 농작물(?) 들은 좌우상하 인접한 녀석들과 교배되어, 수확된다. 다음 턴이 $N^2$ 개만을 선별하여 다시 심는 것을 반복하여 최대한 Feature를 개선하는 것이 목표.

문제 풀이

우선 외곽과 주변을 다르게 처리해야한다. 주변에는 영향을 미치는 cell이 2, 3개인 반면, 중앙부분은 4개이기 때문. Breeding이 많이 되길 원한다면, 중앙에 둬야한다.

나는 스코어를 부여하는 방식을 통해서 개선을 많이 이루어냈는데, 우선 전체 Feature의 합을 스코어로 썼을 때 210M 정도의 스코어가 나왔다. 이를 이렇게만 했을 때에는 효율적이지 않은 것을 직관적으로 알 수 있다.

전체 스코어의 합을 사용하는 것은 후반부에는 유효하겠지만, 초반부에는 오히려 Feature를 다양화할 필요가 있다. 이를 위해서는 제곱, 세제곱을 취하면 다양화를 수식적으로 할 수 있게 된다.

최종적으로는 아래와 같이, Turn 0에서 3제곱, Turn 9에서 1제곱 하도록 수식을 조정하여, 250M을 달성했다.

double coeff = -0.25 * CurTurn + 3;
FOR(i,0,C) {
    double s = 0;
    FOR(j,0,M) {
        Get(i,j);
        s += pow(Seed[i].M[j], coeff);
    }
    Seed[i].score = s;
}

이후에는 너무 1개의 Feature에 대해서만 반영하는 case를 제외하기 위해, 특정 Feature를 max로 갖는 녀석이 2개를 초과하게 되면, 다른 녀석으로 대체하도록 수식을 대체하여 약간 개선하는 선에서 마무리 했다.

주석처리한 Random Swap, SA 전략은 이 문제에서는 크게 효과를 보지 못했다.

팁

아래와 같은 Bash 스크립트로, 편하게 전체 TC를 로컬에서 돌려볼 수 있었다.

# #!/bin/bash

g++ -O2 sol.cpp -o max

ans=0
for num in $(seq -w 0000 0299); do
    ./max < ./in/$num.txt > ./out/$num.txt
    line=$(tail -n 1 ./out/$num.txt) > /dev/null
    line="${line:1}"
    ans=$(($ans+$line))
    echo "$num: $line"
done
echo "Overall Score: $ans"

전체 코드

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

#ifndef ONLINE_JUDGE
#define _D(...) printf(__VA_ARGS__)
bool isDebug = true;
#else
#define _D(...)
bool isDebug = false;
#endif

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

int N, M, T;
int CurTurn;
int C;

struct Seed_t {
    int M[15];
    double score;
    bool used;
} Seed[1000];

int Order[1000];

void sort(int s, int e) {
    if (s >= e) return;

    int l = s, r = e, m = (s+e)>>1;
    double pivot = Seed[Order[m]].score;
    
    while(l < r) {
        while(Seed[Order[l]].score > pivot) ++l;
        while(pivot > Seed[Order[r]].score) --r;
        if (l > r) break;
        swap(Order[l], Order[r]);
        ++l; --r;
    }

    sort(s, r); sort(l, e);
}

int Plant[6][6];
Seed_t Nxt_Seed[1000];

bool isFirst = true;
void Get(int i, int j) {
    if (isDebug && !isFirst) {
        Seed[i].M[j] = Nxt_Seed[i].M[j];
        return;
    }
    scanf("%d", &Seed[i].M[j]);
}
int gidx;
void Generate() {
    gidx = 0;
    // 좌우
    char buf[20];
    FOR(i,0,N) FOR(j,0,N-1) {
        scanf("%s", buf);
        _D("#");
        FOR(k,0,M) {
            if (buf[k] == '0') {
                Nxt_Seed[gidx].M[k] = Seed[Plant[i][j]].M[k];
            } else {
                Nxt_Seed[gidx].M[k] = Seed[Plant[i][j+1]].M[k];
            }
            _D("%d ", Nxt_Seed[gidx].M[k]);
        }
        ++gidx;
        _D("\n");
    }
    // 상하
    FOR(i,0,N-1) FOR(j,0,N) {
        scanf("%s", buf);
        _D("#");
        FOR(k,0,M) {
            if (buf[k] == '0') {
                Nxt_Seed[gidx].M[k] = Seed[Plant[i][j]].M[k];
            } else {
                Nxt_Seed[gidx].M[k] = Seed[Plant[i+1][j]].M[k];
            }
            _D("%d ", Nxt_Seed[gidx].M[k]);
        }
        ++gidx;
        _D("\n");
    }
}

int BaseScore;
void GetBaseScore() {
    BaseScore = 0;
    FOR(k,0,M) {
        int maxval = 0;
        FOR(i,0,C) {
            if (Seed[i].M[k] > maxval) maxval = Seed[i].M[k];
        }
        BaseScore += maxval;
    }
}

void In() {
    if (!isFirst && isDebug) Generate();

    double coeff = -0.25 * CurTurn + 3;
    FOR(i,0,C) {
        double s = 0;
        FOR(j,0,M) {
            Get(i,j);
            s += pow(Seed[i].M[j], coeff);
        }
        Seed[i].score = s;
    }

    if (isFirst) {
        GetBaseScore();
        isFirst = false;
    }
};

int dr[4] = {-1, 0, 1, 0};
int dc[4] = {0, -1, 0, 1};
double GetSingleScore(int r, int c) {
    double ret = 0;
    // double coeff = -0.25 * CurTurn + 3;
    FOR(p,0,4) {
        int tr = r + dr[p];
        int tc = c + dc[p];
        double cur = 0;
        FOR(k,0,M) {
            // ret += pow(double(Seed[Plant[tr][tc]].M[k] + Seed[Plant[r][c]].M[k]) / 2, coeff);
            cur += pow(abs(Seed[Plant[tr][tc]].M[k] - Seed[Plant[r][c]].M[k]), 2);
        }
        ret += cur;
    }

    return ret;
}

struct Coord_t {
    int r, c;
} Coord[1000];
Coord_t Center;
int COrder[1000];
int CKey[1000];

void csort(int s, int e) {
    if (s >= e) return;

    int l = s, r = e, m = (s+e)>>1;
    int pivot = CKey[COrder[m]];
    
    while(l < r) {
        while(CKey[COrder[l]] < pivot) ++l;
        while(pivot < CKey[COrder[r]]) --r;
        if (l > r) break;
        swap(COrder[l], COrder[r]);
        ++l; --r;
    }

    csort(s, r); csort(l, e);
}

int seed = 5;
unsigned int prand() {
    seed = 214013 * seed + 2531011;
    return (seed >> 16) & 0x7FF;
}
void Out() {
    FOR(i,0,C) Order[i] = i, Seed[i].used = false;
    sort(0,C - 1);

    if (CurTurn == 0) {
        // Max는 2개까지만 선택
        int didx = N*N;
        int cnt[15] = {0, };
        FOR(i,0,C) {
            if (didx >= C) break;
            int maxVal = 0, maxIdx = -1;
            FOR(k,0,M) {
                if (maxVal < Seed[Order[i]].M[k]) {
                    maxVal = Seed[Order[i]].M[k];
                    maxIdx = k;
                }
            }
            if (cnt[maxIdx] >= 2) {
                swap(Order[i], Order[didx++]);
            } else {
                cnt[maxIdx]++;
            }
        }
    }

    int idx = 0;
    FOR(z,0,N*N) {
        int i = COrder[z];
        Seed[Order[idx]].used = true;
        Plant[Coord[i].r][Coord[i].c] = Order[idx++];
    }


    // 랜덤스왑 시작
    // if (CurTurn == 1) {
    //     int swapcnt = 0;
    //     FOR(r,0,10'000) {
    //         int ar = (prand() % (N - 1)) + 1;
    //         int ac = (prand() % (N - 1)) + 1;
    //         int br = (prand() % (N - 1)) + 1;
    //         int bc = (prand() % (N - 1)) + 1;
    //         if (ar == br && ac == bc) continue;

    //         double before = GetSingleScore(ar, ac) + GetSingleScore(br, bc);
    //         swap(Plant[ar][ac], Plant[br][bc]);
    //         double after = GetSingleScore(ar, ac) + GetSingleScore(br, bc);
            
    //         if (before < after) {
    //             // swap!
    //             // _D("#before: %lf / after: %lf\n", before, after);
    //             ++swapcnt;
    //         } else {
    //             // no!
    //             swap(Plant[ar][ac], Plant[br][bc]);
    //         }
    //     }

    //     // 랜덤스왑 끝
    //     _D("#swap: %d\n", swapcnt);
    // }

    FOR(i,0,N) {
        FOR(j,0,N) {
            printf("%d ", Plant[i][j]);
        }
        printf("\n");
    }
    fflush(stdout);
}

void GetScore() {
    int maxval = 0;
    FOR(i,0,C) {
        int curScore = 0;
        FOR(k,0,M) {
            curScore += Seed[i].M[k];
        }
        if (curScore > maxval) maxval = curScore;
    }
    _D("#Base: %d\n", BaseScore);
    _D("#Max: %d\n", maxval);
    _D("#%.0lf\n", round((double)maxval * 1'000'000 / BaseScore));
}

int main() {
    isFirst = true;
    scanf("%d %d %d", &N, &M, &T);
    C = 2 * N * (N - 1); // 60

    Center = {N / 2, N / 2};
    FOR(i,0,N) FOR(j,0,N) {
        COrder[i*N+j] = i*N+j;
        CKey[i*N+j] = abs(i - Center.r) + abs(j - Center.c);
        Coord[i*N+j] = {i, j};
    }
    csort(0,N*N-1);
    
    FOR(i,0,N*N) {
        _D("#[%d] %d, %d\n", i, Coord[COrder[i]].r, Coord[COrder[i]].c);
    }

    FOR(i,0,T) {
        _D("#Turn %d\n", i);
        CurTurn = i;
        In();
        Out();
        GetScore();
    }
    In(); // We can use it to evalute score
    GetScore();

    return 0;
}