Medium 과 Hard 가 골고루 어려웠던 SRM393 은 하드를 세 명밖에 못 풀면서 안드로 매치로 달려갔습니다. 뭐 그래봐야 페사마가 1등을 먹은 건 여전합니다만. (개인 레이팅 최고기록을 깸으로써, 이제 다시 저와 1000점이 넘게 차이가 납니다. 이거 뭥미)
한국에서는 저와 kimyolo, ilyoan 님이 두 문제 풀면서 선전하셨고요.. 저는 얼떨결에 풀고 챌린지도 안했는데 Top 10 에 들어서 부끄럽습니다. 이런 매치에서는 챌린지를 좀 더 적극적으로 했어야 하는데..
자 그럼 문제 해설 갑니다.
250 - InstantRunoffVoting : 매우 간단한 '이걸 구현해라' 문제이죠. 문제 잘 읽고 따라 치면 되는 문제. (훗, 레코드입니다..) 따라서 틀릴 구석이 많진 않습니다만 은근히 쏠쏠히 틀렸네요. 많이 틀린 부분은 후보 수 != 투표자 수일때, 배열 크기를 바꿔 쓰는 것이었습니다. (한국 A모 레드님도 이걸로 Systest fail) 요런건 공통된 챌린지 포인트이니 잡아주는 센스..
제 소스입니다. 매크로는 좀 봐주세영.
~~~ cpp

#include
#include
#include
#include
#include
using namespace std;
#define FOR(i,a,b) for(int i = (a); i < (b); ++i)
#define REP(i,n) FOR(i,0,n)
#define FORE(it,x) for(typeof(x.begin()) it=x.begin();it!=x.end();++it)
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define CLEAR(x,with) memset(x,with,sizeof(x))
#define sz size()
typedef long long ll;
struct InstantRunoffVoting
{
int winner(vector voters)
{
bool alive[10]; REP(i,10) alive[i] = true;
int n = voters.sz, m = voters[0].sz;
while(true)
{
if(count(alive, alive+m, true) == 0) break;
int got[10]; CLEAR(got,0);
REP(i,n) REP(j,m) if(alive[ voters[i][j]-'0' ]) { ++got[voters[i][j]-'0']; break; }
REP(i,m) if(got[i]*2 > n) return i;
int mini = 987654321;
REP(i,m) if(alive[i]) mini <?= got[i];
REP(i,m) if(got[i] == mini) alive[i] = false;
}
return -1;
}
};
~~~
500 - NSegmentDisplay; 굉장히 복잡해 보입니다만 알고 보면 그렇게 복잡하진 않습니다. 일단, 한 번이라도 켜진 segment 가 있으면 걔는 고장났을 수 없다는 걸 알 수 있죠. 따라서, 이걸 갖고 맨 처음에 inconsistent 체크를 할 수 있습니다: 매 pattern 에 대해서, 이 symbol 이 보이는 거라고 설명할 수 있는 게 최소한 하나라도 있어야 하는데, 없으면 inconsistent 인 거죠. 예를 들어, pattern[i] = 0 이고 symbol[i] = 1 이라고 합시다. 이 때, i 번째 segment 가 딴 데서도 한 번도 안 켜졌다면 이건 고장난 거라고 치고 넘어갈 수 있습니다. 하지만 딴 데서 한 번이라도 켜져 있다면 이건 말이 안 되죠.
inconsistent 체크를 통과했다면, 한 번이라도 켜졌던 segment 는 모두 work 한다고 주장할 수 있습니다. 그 후, 모두 꺼져 있었던 segment 에 대해 not work 인지, don't know 인지 판단해야 합니다. (한번도 안 켜졌다면 work 일 수는 없습니다. 왜일까요?) 이 점을 각각의 segment 에 따라서 독립적으로 판정을 할 수 있습니다. 이 점이 약간 비직관적이라 어려운데요.. a 비트가 망가진 게 아니려면 X 라는 시나리오로 가야 하고, b 비트가 망가진 게 Y 라는 시나리오로 가야 한다고 합시다. 이 때 알 수 없는 본능이, 'X 와 Y 가 서로 상호 배제적이라면, a와 b에 대해 서로 결과가 연관 있어야 하는 게 아닌가' 라고 속삭입니다만, 사실은 생까고 둘다 '알수 없음' 으로 해야 합니다. 당연히, X 일지 Y 일지 우리는 모르니까요.
하나의 segment 에 대한 판단은.. 모든 패턴을 돌아보면서, 해당 비트가 꺼져 있는 symbol 들을 다 이 패턴에 매칭해 보면 됩니다. 그래서 하나라도 말이 되는 것 (work 인 segment 들이 일치하는 것) 이 있으면 시나리오가 말이 되는 거죠.
소스 나갑니다. 매크로는 위 소스 코드에서 참조하세염;;
~~~ cpp
struct NSegmentDisplay
{
bool works[50][50];
bool worksAgainst(const string& observed, const string& symbol, const vector& seen)
{
int n = seen.sz;
REP(i,n)
{
if(observed[i] == '1' && symbol[i] == '0') return false;
if(observed[i] == '0' && symbol[i] == '1' && seen[i]) return false;
}
return true;
}
string brokenSegments(vector symbols, vector patterns)
{
int s = symbols.sz, p = patterns.sz, n = symbols[0].sz;
string ret(n, '?');
vector seen(n, false);
REP(i,p) REP(j,n) if(patterns[i][j] == '1') { seen[j] = true; ret[j] = 'Y'; }
CLEAR(works,0);
REP(i,p) REP(j,s) works[i][j] = worksAgainst(patterns[i], symbols[j], seen);
REP(i,p) if(count(works[i], works[i]+s, true) == 0) return "INCONSISTENT";
REP(i,n) if(!seen[i])
{
REP(a,p)
{
bool canHappen = false;
REP(b,s) if(symbols[b][i] == '0') if(works[a][b])
{
canHappen = true; break;
}
if(!canHappen)
{
ret[i] = 'N';
break;
}
}
}
return ret;
}
};
~~~
1000 - AirlineInternet ; 읽어보면 까마득합니다만 의외로 쉬운 문제입니다. (못 푼 놈이 말은 쉽게 한다) 일단, 비행기의 움직임은 R과 상관없이 동일하므로, R 로 할 수 (모든 비행기에 인터넷을 연결할 수) 있다면 R+1 로도 할 수 있다는 게 자명하죠. 따라서 바이너리 서치를 생각할 수 있습니다.
바이너리 서치는 임의의 R 을 정하고, 이 R 로 모든 비행기가 인터넷을 이용할 수 있는가 판단하는 것을 반복합니다. 이 판단을 어떻게 할까요? 비행기들은 continuous 하게 움직이기 때문에, 매번 시뮬레이션할 수도 없구요.
이런 때 유용하게 써먹을 수 있는 테크닉이, boundary 마다 잘라서 시간을 discrete 하게 바꾸는 방법입니다. 두 대의 비행기의 움직임을 살펴보면, 두 비행기의 거리는 2차함수의 일부를 그리게 됩니다. (왜냐면, 에, 비행기의 각 좌표를 시간에 대한 일차함수로 표현하면, 같은 t 에서 두 비행기 간의 거리는 t 에 대한 2차함수이기 때문에..) 따라서, 비행기간의 거리가 R 이 되는 시점을 찾아내면 그 전후로 그 비행기간에 연결이 가능하다/불가능하다 를 알 수 있게 되죠. 공항에 대해서도 이와 마찬가지로 해 줍니다. 이렇게 하고 이 시점들을 다 소트하면, 각각의 time interval (t[i], t[i+1]) 내에서는 연결 관계가 변하지 않는다는 걸 알 수 있죠.
그럼 t' = (t[i]+t[i+1])/2 시점을 구한 뒤 이 시점에서 비행기들의 위치를 계산하고, 모든 비행기가 인터넷을 쓸 수 있나를 확인하면 됩니다. 모든 time interval 내에서, 떠 있는 비행기가 모두 인터넷을 쓸 수 있어야겠죠?
소스 코드 나갑니다. (공항과 비행기 사이 거리 계산 안해서 섭밋 못하고, 바이너리 서치 100번 할 것 50번 해서 틀린 비운의 코드..)
~~~ cpp
vector solve(double coef[3])
{
vector ret;
if(fabs(coef[2]) < 1e-9)
{
// order 1
if(fabs(coef[1]) > 1e-9)
ret.push_back(- coef[0] / coef[1]);
else if(fabs(coef[0]) < 1e-8)
ret.push_back(0);
}
else
{
// order 2
double D = coef[1] * coef[1] - 4.0 * coef[0] * coef[2];
if(D >= 0)
{
double sqrtD = sqrt(D);
ret.push_back((-coef[1] + sqrtD) / (2 * coef[2]));
if(sqrtD > 1e-9)
ret.push_back((-coef[1] - sqrtD) / (2 * coef[2]));
}
}
return ret;
}
struct AirlineInternet
{
double a[20], b[20], c[20], d[20];
int fromTime[20], toTime[20];
int airX[20], airY[20];
int n, m;
vector integerTimes;
void convert(const string& flight, int index)
{
int fromAir, fromTime, toAir, toTime;
sscanf(flight.c_str(), "%d %d %d %d", &fromAir, &toAir, &fromTime, &toTime);

integerTimes.pb(fromTime);
integerTimes.pb(toTime);
int fromX = airX[fromAir], fromY = airY[fromAir];
int toX = airX[toAir], toY = airY[toAir];
double xSpeed = (toX - fromX) / double(toTime - fromTime);
double ySpeed = (toY - fromY) / double(toTime - fromTime);
a[index] = fromX - fromTime * xSpeed;
b[index] = xSpeed;
c[index] = fromY - fromTime * ySpeed;
d[index] = ySpeed;
this->fromTime[index] = fromTime;
this->toTime[index] = toTime;
}
inline double sqr(double d) { return d*d; }
bool feasible(double R)
{
vector times;
times.insert(times.end(), all(integerTimes));
REP(i,m) REP(j,n)
{
double ad = a[i] - airX[j], bd = b[i], cd = c[i] - airY[j], dd = d[i];
double coef[3];
coef[2] = sqr(bd) + sqr(dd);
coef[1] = 2 * (ad * bd + cd * dd);
coef[0] = sqr(ad) + sqr(cd) - sqr(R);
vector sol = solve(coef);
REP(k,sol.sz)
{
double t = sol[k];
if(t <= fromTime[i] || toTime[i] <= t) continue;
times.pb(sol[k]);
}
}
REP(i,m) REP(j,i)
{
if(toTime[i] <= fromTime[j] || toTime[j] <= fromTime[i]) continue;
double ad = a[i] - a[j], bd = b[i] - b[j], cd = c[i] - c[j], dd = d[i] - d[j];
double coef[3];
coef[2] = sqr(bd) + sqr(dd);
coef[1] = 2 * (ad * bd + cd * dd);
coef[0] = sqr(ad) + sqr(cd) - sqr(R);
vector sol = solve(coef);
REP(k,sol.sz)
{
double t = sol[k];
if(t <= fromTime[i] || t <= fromTime[j] || toTime[i] <= t || toTime[j] <= t) continue;
times.pb(sol[k]);
}
}
sort(all(times));
times.erase(unique(all(times)), times.end());
double x[20], y[20];
bool included[20], visited[20];
REP(i,times.sz-1) if(times[i+1] - times[i] > 1e-9)
{
double t = (times[i] + times[i+1]) * 0.5;

REP(j,m)
{
included[j] = (fromTime[j] < t && t < toTime[j]);
if(included[j])
{
x[j] = a[j] + b[j] * t;
y[j] = c[j] + d[j] * t;
}
}
CLEAR(visited,0);
queue q;
REP(j,n) REP(k,m) if(!visited[k] && included[k] && hypot(airX[j] - x[k], airY[j] - y[k]) <= R)
{
visited[k] = true;
q.push(k);
}
while(!q.empty())
{
int here = q.front(); q.pop();
REP(there,m) if(included[there] && !visited[there] && hypot(x[here]-x[there], y[here]-y[there]) <= R)
{
visited[there] = true;
q.push(there);
}
}
REP(j,m) if(included[j] && !visited[j]) return false;
}
return true;
}
double minimumRange(vector airportLocations, vector flights)
{
n = airportLocations.sz; m = flights.sz;
REP(i,n) { sscanf(airportLocations[i].c_str(), "%d %d", &airX[i], &airY[i]); }
REP(i,m) convert(flights[i], i);
sort(all(integerTimes));
integerTimes.erase( unique(all(integerTimes)), integerTimes.end() );
double lo = 0, hi = 0;
REP(i,n) REP(j,i) hi >?= hypot(airX[i] - airX[j], airY[i] - airY[j]);
hi *= 0.5;
printf("hi %.9lf\n", hi);
REP(iter,50)
{
double mid = (lo+hi) * 0.5;
if(feasible(mid))
hi = mid;
else
lo = mid;
}
printf("gap %.8lf\n", hi-lo);
return hi;
}
};
~~~