TCO 08 티셔츠가 걸린 대회였습니다.
문제는 Epidemic
바이러스가 퍼져나가는데.. 예방접종과 주위 사람들을 못만나게 하는(edge Reduce를 해석하면 뭐가 되는지?) 2가지 방법을 적절히 사용해서 제일 돈이 적게 드는 방법을 찾아라... 는 문제였습니다.
일요일에.. 64점 정도로 submit을 했었는데.. 이때 등수가 30등 정도 였었던것 같습니다.
100등까지 진출이니까 안전하겠지 하고 안심하고 있었는데.. 하루하루 등수 떨어지는게 장난이 아닙니다. -_-;
부랴부랴 소스 수정한다고 회사에서 눈치 봐가면서 30분마다 example 돌렸습니다.
visualizer가 제공이 되지 않아서 시뮬레이터를 만들까 하다가 귀찮기도 하고 37번이나 example test를 하게 되었습니다.
역시 시뮬레이터는 필수..
결국.. provisional score로 100등이 64.04점이었습니다.

• 먼저 init().
  1) 각각의 노드마다 edge list를 만듭니다. 이 때 반대쪽도 만듭니다.
  2) 감염확률은 risk로 1,2,3의 값이 주어지는데.. 평균적으로 테스트해보니까 phigh, plow 사이에서 .1633, .5, .8367 정도의 값을 가지게 되어서 각각 그 값으로 확률값을 넣어줍니다.
  3) 각 노드별로 연결되어 있는 사람들의 감염확률의 합을 계산합니다. 이 값은 이사람이 감염될 경우 주위에 감염시킬 확률을 계산하는데 쓰입니다.
  4) K==2인 경우에 초기에 감염될 확률이 많은 사람들은 미리 예방접종을 합니다. 계산식은 확률을 이용하였습니다. K==0일 때는 할 필요가 전혀 없고, K==1일때는 예방접종을 시켜보니 결과가 썩 좋지 않게 나와서 적용하지 않기로 했습니다.
  [spoiler="더 보기..."] ~~~ c

  int i, j;
  // 1) 부분..
  for (i = 0; i < g.size(); i += 2) {
  node[g[i]].fr.push_back(g[i+1]);
  node[g[i]].edg.push_back(false);
  node[g[i]].cnt_fr++;
  node[g[i+1]].fr.push_back(g[i]);
  node[g[i+1]].edg.push_back(false);
  node[g[i+1]].cnt_fr++;
  }
  // 2) 부분
  float pp[4];
  pp[1] = plow + (phigh - plow) * .1633;
  pp[2] = (plow + phigh) / 2;
  pp[3] = phigh - (phigh - plow) * .1633;
  for (i = 0; i < n; i++) {
  node[i].p = pp[risk[i]];
  }
  // 3) 부분
  for (i = 0; i < n; i++) {
  for (j = 0; j < node[i].fr.size(); j++) {
  node[i].p_fr += node[node[i].fr[j]].p;
  }
  }
  vector ans(0);
  float ratio;
  // 4) 부분
  if (k == 2) {
  for (i = 0; i < n; i++) {
  ratio = powf(pp[2] * (g.size() / n), k) * node[i].p * node[i].p_fr / n;
  if (ratio * cost_inf * (1 - x) > cost_ino) {
  ans.push_back(i);
  for (j = 0; j < node[i].fr.size(); j++) {
  node[node[i].fr[j]].p_fr -= node[i].p * (1 - x);
  }
  node[i].p *= x;
  node[i].ino = true;
  }
  }
  }

# 지정된 언어 [/spoiler]를 찾을 수 없습니다.
- 두번째 day()
소스가 많이 지저분한데요..
5) 일단 감염이 되면.. 주위 사람들의 3)에서 계산했던 값을 빼 줍니다.
6) K값에 따라서 예상 감염자를 계산합니다.
7) 예상 감염자의 주위 사람들에게 예방접종을 할지? 관계감소를 시킬지를 적당히 확률을 이용해서 계산합니다.
[spoiler="더 보기..."]~~~ c

// 5) 부분
bool Epidemic::make_inf(int n, int v)
{
    if (node[n].inf != 0) return false;
    node[n].inf = v;
    for (int i = 0; i < node[n].fr.size(); i++) {
        node[node[n].fr[i]].cnt_fr--;
        node[node[n].fr[i]].p_fr -= node[n].p;
    }
    return true;
}
vector<string> Epidemic::day(vector<int> infected)
{
    start_timer();
    vector<string> ans(0);
    int i, kk;
    map<int, float> infmap, infmap2;
    map<int, float>::iterator it;
    ++days;
    if (!check_timer() ) goto out;
    cnt_ino = 0;
    cnt_edg = 0;
    cnt_fr = 0;
    ch.reset();
    for (i = 0; i < infected.size(); i++) {
        make_inf(infected[i], 1);
        infmap[infected[i]] = 1;
    }
    // 6) 부분
    for (kk = 0; kk < k; kk++) {
        if (!check_timer() ) goto out;
        infmap2.clear();
        for(it = infmap.begin(); it != infmap.end(); it++) {
            int nn = it->first;
            if (!check_timer() ) goto out;
            for (i = 0; i < node[nn].fr.size(); i++) {
                if (node[node[nn].fr[i]].inf) continue;
                if (ch[node[nn].fr[i]]) continue;
                if (infmap2.find(node[nn].fr[i]) == infmap2.end() ) {
                    infmap2[node[nn].fr[i] ] = node[node[nn].fr[i]].p * it->second;
                } else {
                    infmap2[node[nn].fr[i] ] += node[node[nn].fr[i]].p * it->second;
                }
            }
        }
        infmap = infmap2;
        for(it = infmap.begin(); it != infmap.end(); it++) ch.set(it->first);
    }
    // 7) 부분.
    for(it = infmap.begin(); it != infmap.end(); it++) {
        if (!check_timer() ) goto out;
        inoculate(it->first, it->second, ans);
    }
out:    
    end_timer();
    fprintf(stderr, "Day %d(%.3f) - inf : %d, fr : %d, ino : %d, edg : %d\n", days, used_time, infected.size(), cnt_fr, cnt_ino, cnt_edg);
    fflush(stderr);
    return ans;
}
void Epidemic::inoculate(int n, float pp, vector<string> &ans)
{
    int i, j;
    int f;
    char tmp[100];
    float fpinf;
    float pinf, pedg, pino, pboth, pmin;
    for (i = 0; i < node[n].fr.size(); i++) {
        f = node[n].fr[i];
        if (node[f].inf) continue;
        if (k == 2 && ch[f]) continue;
        cnt_fr++;
        fpinf = node[f].p * pp;
        if (node[n].edg[i]) fpinf *= y;
        pinf = cost_inf * fpinf * (1 + node[f].p_fr);
        if (node[n].edg[i]) pedg = pinf + 1;
        else pedg = pinf * y + cost_edg;
        if (node[f].ino) pino = pinf + 1;
        else pino = pinf * x + cost_ino;
        if (node[n].edg[i] || node[f].ino) pboth = pinf + 1;
        else pboth = pinf * y * x + cost_edg + cost_ino;
        pmin = min(min(pinf, pedg), min(pino, pboth) );
        if (pmin == pinf) continue;
        if (pmin == pedg || pmin == pboth) {
            node[n].edg[i] = true;
            cnt_edg++;
            sprintf(tmp, "%d %d", n, f);
            ans.push_back(tmp);
            for (j = 0; j < node[f].fr.size(); j++) {
                if (node[f].fr[j] == n) {
                    node[f].edg[j] = true;
                    break;
                }
            }
        }
        if (pmin == pino || pmin == pboth) {
            node[f].ino = true;
            cnt_ino++;
            for (j = 0; j < node[f].fr.size(); j++) {
                node[node[f].fr[j]].p_fr -= node[f].p * (1 - x);
            }
            node[f].p *= x;
            sprintf(tmp, "%d", f);
            ans.push_back(tmp);
        }
    }
    return;
}

~~~[/spoiler]
- 실행 시간 계산하는 부분입니다.
clock()나 times() 를 이용해 보았었는데.. example 결과에 나오는 시간과는 차이가 많이 나서 gettimeofday()를 사용하고 있습니다.
end_timer()를 호출할때 1/100 초를 보정치로 계속 더해주니 거의 비슷해 지네요.
check_timer()를 자주 호출해서 시간이 초과하였을 경우, 단순하게 리턴을 시켜버리고 있습니다.
[spoiler="더 보기..."]~~~ c

#include <time.h>
#include <sys/time.h>
#ifdef LOCAL
#define TIME_LIMIT     58
#else
#define TIME_LIMIT     19
#endif
struct timeval start, now;
double used_time = 0;
void start_timer()
{
    gettimeofday(&start, NULL);
}
void end_timer()
{
    gettimeofday(&now, NULL);
    used_time += 0.01 + (now.tv_sec - start.tv_sec) + (double) (now.tv_usec - start.tv_usec) / 1000000;
}
bool check_timer()
{
    gettimeofday(&now, NULL);
    if (used_time + (now.tv_sec - start.tv_sec) + (double) (now.tv_usec - start.tv_usec) / 1000000 > TIME_LIMIT) return false;
    else return true;
}

~~~[/spoiler]
- 추가 아이디어
1차 감염확률만을 계산하였는데.. 2차, 3차 감염확률까지 계산하면 결과가 더 좋아질지도 모르겠습니다.
그럭저럭 61->65등으로 티셔츠는 받게 되었습니다.
우리나라는 3명이 출전했는데.. 간신히 저만 통과하게 되었습니다.
다음번에는 좋은 결과 있기를 바랍니다.
여러가지 아이디어를 짜내도.. 60등 위로는 도저히 못올라가겠더라구요.
한계를 절실하게 느끼는 중입니다.
Round 3는 2주일짜리인데 12등 이내로는 힘들것 같습니다. -_-;
올해는 티셔츠에서 만족을 해야 될듯...
<div>[이 글은 과거 홈페이지에서 이전된 글입니다. <a href="http://algospot.andromeda-express.com/zbxe/editorial/45202">원문보기</a>]</div>