---
id: "imported/blog/history/ex/ahc-35"
title: "AHC 35"
description: "오랜만에 참가한 AHC. 제목은 Breed Improvement."
kind: "record"
published: "2024-07-21T00:00:00.000Z"
tags: ["PS","atcoder"]
url: "https://www.readiz.com/blog/history/ex/ahc-35/"
markdownUrl: "https://www.readiz.com/blog/history/ex/ahc-35/index.md"
---

# AHC 35

오랜만에 참가한 AHC. 제목은 `Breed Improvement`.

- 문제 링크: <https://atcoder.jp/contests/ahc035/tasks/ahc035_a>
- 해설(YouTube, 일본어): <https://www.youtube.com/watch?v=gRbq9aUCrKs&ab_channel=AtCoderLive>

# 문제 분석

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을 달성했다.

```cpp
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를 로컬에서 돌려볼 수 있었다.

```bash
# #!/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"
```

## 전체 코드

```cpp
#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;
}
```