어제 밤 12시에 탑코더에서 좀 특이한 매치가 열렸다..
형식은 일반 srm 과 비슷한데 정규 srm 이 아니라서
not rated event 일뿐더러.. competition history에도 안나온다..
물론 match editorial 도 없다.. 흠..

이런 비정규 매치를 하는 취지는 여기에 설명되어있다..
뭐 앞으로 다양한 시도를 하는것같긴 한데..
그냥 이런거 하느니.. 일반 srm 이나 늘리는게 더 좋은데.. 쩝..

not rated event 라서 부담없이 했는데.. 성적은 괜찮게 나왔다..
방 9위 디비젼 199위..





Level1 - ErdosNumber
Erdos 라는 사람은 자신과 0 촌이다.. 이사람과 같이 책을 쓴 사람은 Erdos 와 1촌이다.. Erdos 와 1촌인 사람과 같이 책을 쓴 사람은 Erdos 와 2촌이다.. 즉, 어떤 책을 같이 쓴 공동저자는 그 저자들 가운데 가장 낮은 Erdos number + 1 의 Erdos number 를 갖게 된다.. 모든 사람의 Erdos number 출력하기..

이 문제는 UVa 에 있는 10044 - Erdos Numbers 문제와 거의 같다.. 물론 UVa 문제가 훨씬 어렵다..
솔루션이 어려운게 아니라.. input 받아서 parsing 하는게 열라 더럽다..
물론 이 문제도 input parsing 이 까다롭지만 UVa 비하면 새발의 피라고나할까..

일단 각각의 저자를 vertex 라고 생각하고 공동 저자끼리 길이가 1인 edge로 연결하여 graph 를 구성한다..
Erdos 자신을 vertex 1 이라고 놓고.. 1번 vertex 부터 나머지 vertex 까지의 shortest path를 구하면 끝..~
shortest path 는 간단히 Floyd-Warshall 을 이용했다..~

처음에 문제를 잘못이해해서 코드 중간에 좀 쓸데없는 짓을 했다.. ㅋㅋ 굳이 상관없을꺼같아서 그냥 남겨뒀음
이문제는 C++ STL 을 잘 다루는사람한테 특히 유리할듯.. 나도 map, set 을 적극 활용했다..
생각해보니 multiset 은 쓸필요가 없는디..? -_-;;

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <algorithm>
  4 #include <vector>
  5 #include <string>
  6 #include <map>
  7 #include <set>
  8 using namespace std;
  9 #define min(x, y) ((x) > (y) ? (y) : (x))
 10 //#define max(x, y) ((x) > (y) ? (x) : (y))
 11 #define INF 999999999
 12 typedef struct _d {
 13     char name[200];
 14     int val;
 15 } DATA;
 16
 17 int graph[200][200];
 18 char list[200][200];
 19 int n;
 20 DATA data[200];
 21
 22 int comp(const void* x, const void* y)
 23 {
 24     DATA* a = (DATA*)x;
 25     DATA* b = (DATA*)y;
 26     return strcmp(a->name, b->name);
 27 }
 28
 29 class ErdosNumber {
 30 public:
 31
 32 vector <string> calculateNumbers(vector <string> pub)
 33 {
 34     int i, j, k;
 35     int idx1, idx2;
 36     char buf[2000];
 37     char* ptr;
 38     map<string, int> idx;
 39     vector<string> res;
 40
 41     for (i = 0; i < 200; i++) {
 42         for (j = 0; j < 200; j++) {
 43             graph[i][j] = INF;
 44         }
 45         graph[i][i] = 0;
 46     }
 47     idx.clear();
 48     idx["ERDOS"] = 1;
 49     strcpy(list[1], "ERDOS");
 50     n = 2;
 51     for (i = 0; i < pub.size(); i++) {
 52         multiset<int> tempset;
 53         multiset<int>::iterator it, it2;
 54         strcpy(buf, pub[i].c_str());
 55         ptr = strtok(buf, " ");
 56         if (idx.find(ptr) == idx.end()) {
 57             strcpy(list[n], ptr);
 58             idx[ptr] = n++;
 59         }
 60         idx1 = idx[ptr];
 61         tempset.insert(idx1);
 62         ptr = strtok(NULL, " ");
 63         while (ptr != NULL) {
 64             if (idx.find(ptr) == idx.end()) {
 65                 strcpy(list[n], ptr);
 66                 idx[ptr] = n++;
 67             }
 68             idx2 = idx[ptr];
 69             tempset.insert(idx2);
 70             ptr = strtok(NULL, " ");
 71         }
 72         for (it = tempset.begin(); it != tempset.end(); it++) {
 73         for (it2 = tempset.begin(); it2 != tempset.end(); it2++) {
 74             graph[*it][*it2] = min(graph[*it][*it2], 1);
 75         }
 76         }
 77     }
 78     n--;
 79     for (k = 1; k <= n; k++) {
 80     for (i = 1; i <= n; i++) {
 81     for (j = 1; j <= n; j++) {
 82         graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j]);
 83     }
 84     }
 85     }
 86     for (i = 1; i <= n; i++) {
 87         strcpy(data[i].name, list[i]);
 88         data[i].val = graph[1][i];
 89     }
 90     qsort(&data[1], n, sizeof(DATA), comp);
 91     for (i = 1; i <= n; i++) {
 92         if (data[i].val == INF)
 93             sprintf(buf, "%s", data[i].name);
 94         else
 95             sprintf(buf, "%s %d", data[i].name, data[i].val);
 96         res.push_back(buf);
 97     }
 98     return res;
 99 }
100
101 };



Level2 - CantorDust



to be updated..



Level3 - WallClimbing



to be updated..

Leave a Comment


to Top