어제 애들이 PS 에서 돌길래 따라 돌아 보았다. --; 7문제 푼 시점에서 마지막 문제를 놓고 할까 말까 고민하다가 '에잇 다풀어야지 난 멋있으니까 'ㅡ')r' 하고 달라붙어서 결국 풀었다. ㅠ.ㅠ 8/1242. 한 시간 있다 시작했으니 실제로는 8/762. 당시 원석이형 성준이형 태형이형 팀네는 7/646. 하지만 8년전의 대회잖아 기쁘지 않아 ㅠㅠㅋㅋㅋㅋㅋㅋㅋ
A: Calendar Game
Simple impartial game. 윤년 및 자잘한 룰이 들어가서 구현이 좀 귀찮다. 대부분 한 번쯤은 걸려 넘어졌던 문제.
lang:cpp
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef long long ll;
const int days[12] = { 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 };
map<VI, int> cache;
VI end;
int monthLength(int year, int month)
{
if(month != 2) return days[month-1];
bool isLeap = (year % 400 == 0 || (year % 100 > 0 && year % 4 == 0));
return isLeap ? 29 : 28;
}
VI nextDay(VI key)
{
++key[2];
if(key[2] > monthLength(key[0], key[1]))
{
++key[1];
key[2] = 1;
}
if(key[1] == 13)
{
++key[0];
key[1] = 1;
}
return key;
}
VI nextMonth(VI key)
{
++key[1];
if(key[1] == 13)
{
++key[0];
key[1] = 1;
}
if(key[2] > monthLength(key[0], key[1]))
key.clear();
return key;
}
int isWinning(const VI& key)
{
if(key.empty()) return 1;
if(key > end) return 1;
if(key == end) return 0;
if(cache.count(key)) return cache[key];
int& ret = cache[key];
ret = 0;
if(!isWinning(nextDay(key)))
ret = 1;
else if(!isWinning(nextMonth(key)))
ret = 1;
return ret;
}
int main()
{
end.resize(3);
end[0] = 2001;
end[1] = 11;
end[2] = 4;
int cases;
cin >> cases;
for(int cc = 0; cc < cases; ++cc)
{
int y, m, d;
cin >> y >> m >> d;
VI key(3);
key[0] = y; key[1] = m; key[2] = d;
cout << (isWinning(key) ? "YES" : "NO") << endl;
}
}
B: Wooden Sticks
아직까지도 어떻게 증명해야 할 지 모르겠는 그리디 ㅡ_ㅡ:
lang:cpp
int main()
{
int cases;
cin >> cases;
for(int cc = 0; cc < cases; ++cc)
{
int n;
cin >> n;
vector<pair<int,int> > st(n);
for(int i = 0; i < n; ++i)
cin >> st[i].first >> st[i].second;
sort(all(st));
int ret = 0;
VI taken(n);
while(true)
{
int a = 0, b = 0;
for(int i = 0; i < n; ++i)
if(!taken[i] && a <= st[i].first && b <= st[i].second)
{
taken[i] = 1;
a = st[i].first;
b = st[i].second;
}
if(a || b)
++ret;
else
break;
}
cout << ret << endl;
}
}
C: Modular Multiplication of Polynomials
문제가 좀 모호하긴 하지만 결국은 주어진 대로 구현만 하면 오케이.
lang:cpp
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef long long ll;
VI norm(VI x)
{
for(int i = 0; i < x.size(); ++i)
x[i] %= 2;
while(!x.empty() && x.back() == 0) x.pop_back();
return x;
}
VI read()
{
int n;
cin >> n;
VI ret(n);
for(int i = 0; i < n; ++i)
cin >> ret[n-1-i];
return norm(ret);
}
VI operator * (const VI& a, const VI& b)
{
VI ret(a.size() + b.size() + 2);
for(int i = 0; i < a.size(); ++i)
for(int j = 0; j < b.size(); ++j)
ret[i+j] += a[i] * b[j];
return norm(ret);
}
VI operator + (const VI& a, const VI& b)
{
VI ret(a.size());
assert(a.size() == b.size());
for(int i = 0; i < a.size(); ++i)
ret[i] = (a[i] ^ b[i]);
return ret;
}
VI operator % (VI a, VI b)
{
while(a.size() >= b.size())
{
VI c(a.size());
for(int i = 0; i < b.size(); ++i)
c[c.size()-i-1] = b[b.size()-i-1];
a = norm(a + c);
}
return norm(a);
}
ostream& operator << (ostream& os, const VI& x)
{
os << x.size();
for(int i = 0; i < x.size(); ++i)
os << " " << x[x.size()-i-1];
return os;
}
int main()
{
int cases;
cin >> cases;
for(int cc = 0; cc < cases; ++cc)
{
VI f = read();
VI g = read();
VI h = read();
/*
cout << "f = " << f << endl;
cout << "g = " << g << endl;
cout << "h = " << h << endl;
cout << "f*g = " << f*g << endl;*/
VI x = (f * g) % h;
cout << x << endl;
}
}
D: Human Gene Functions
Plain vanilla DP.
lang:cpp
string a, b;
int cache[101][101];
bool solved[101][101];
const string elem = "ACGT-";
const int table[5][5] = { { 5, -1, -2, -1, -3 }, { -1, 5, -3, -2, -4 }, {-2, -3, 5, -2, -2}, {-1, -2, -2, 5, -1 }, {-3, -4, -2, -1, 0}};
int cost(char a, char b)
{
return table[elem.find(a)][elem.find(b)];
}
int go(int i, int j)
{
if(i == a.size() && j == b.size()) return 0;
int& ret = cache[i][j];
if(solved[i][j]) return ret;
solved[i][j] = true;
ret = -987654321;
if(i < a.size() && j < b.size())
ret = max(ret, go(i+1, j+1) + cost(a[i], b[j]));
if(i < a.size())
ret = max(ret, go(i+1, j) + cost(a[i], '-'));
if(j < b.size())
ret = max(ret, go(i, j+1) + cost('-', b[j]));
return ret;
}
int main()
{
int cases;
cin >> cases;
for(int cc = 0; cc < cases; ++cc)
{
int al, bl;
cin >> al >> a >> bl>> b;
CLEAR(solved,0);
cout << go(0, 0) << endl;
}
}
E: Flip And Shift
각 시프트는 결국 2만큼 떨어진 애들끼리의 스왑이라는 것을 알아내고, 짝수칸 홀수칸에 있는 애들끼리만 교환이 가능하다는 것을 알면 간단하다. 홀수 특수 케이스 처리 안해주고 이래저래 바꿔 짜다 보니 소스가 구림
lang:cpp
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef long long ll;
int main()
{
int cases;
cin >> cases;
for(int cc = 0; cc < cases; ++cc)
{
int n;
VVI cnt(2,VI(2,0));
cin >> n;
for(int i = 0; i < n; ++i)
{
int c;
cin >> c;
cnt[c][i%2]++;
}
if(n % 2)
cout << "YES" << endl;
else
{
bool ok = false;
for(int sh = 0; sh < 2; ++sh)
{
int wh = cnt[0][0] + cnt[0][1];
VVI c = cnt;
VI desired(n);
for(int i = 0; i < n; ++i)
desired[(i+sh)%n] = ((wh-- > 0) ? 0 : 1);
for(int i = 0; i < n; ++i)
c[desired[i]][i%2]--;
if(c[0][0] == 0 && c[0][1] == 0 && c[1][0] == 0 && c[1][1] == 0)
ok = true;
}
if(ok)
cout << "YES" << endl;
else
cout << "NO" << endl;
}
}
}
F: Moving Tables
Can't be much easier.
lang:cpp
int main()
{
int cases;
cin >> cases;
for(int cc = 0; cc < cases; ++cc)
{
int n;
cin >> n;
VI u(200, 0);
for(int i = 0; i < n; ++i)
{
int a, b;
cin >> a >> b;
if(a > b) swap(a, b);
a /= 2;
b /= 2;
for(int j = a; j <= b; ++j)
++u[j];
}
cout << *max_element(all(u)) * 10 << endl;
}
}
G: Farmland
솔직히 정말 더러운 문제 -_-;;; 하지만 풀었다 ㅜㅜ 전에 한번 구현하려고 했다가 실패했던 polygon tracing 으로, 주어진 평면에서의 모든 폴리곤을 따라가 보는 것이 포인트. 가장 오른쪽에 있는 선분을 따라갈 때, 해당 선분을 CCW 만으로 찾기 어렵다. 결국은 polar coordinate 를 동원해서 확인해야 했음. 뭐 다른 방법이 있을 것 같기도 하고.. ^^
lang:cpp
const double PI = 2.0 * acos(0.0);
struct point
{
double y, x;
point(double y = 0, double x = 0) : y(y), x(x) {}
double dot(const point& rhs) const { return y * rhs.y + x * rhs.x; }
double cross(const point& rhs) const { return y * rhs.x - x * rhs.y; }
bool operator < (const point& rhs) const { if(y != rhs.y) return y < rhs.y; return x < rhs.x; }
point operator + (const point& rhs) const { return point(y + rhs.y, x + rhs.x); }
point operator - (const point& rhs) const { return point(y - rhs.y, x - rhs.x); }
point operator * (double f) const { return point(y * f, x * f); }
point normalized() const { double d = norm(); return point(y / d, x / d); }
double polar() const { double t = atan2(y, x); if(t < 0) t += 2 * PI; return t; }
double norm() const { return hypot(y, x); }
};
int n;
vector<point> p;
VVI adj;
set<pair<int,int> > seen;
set<VI> counted;
int length;
int walk(int here, int there)
{
int start = here, nstart = there;
if(seen.count(make_pair(here, there))) return 0;
VI path(2);
path[0] = here; path[1] = there;
bool valid = true;
// printf("walk (%d,%d)\n", here+1, there+1);
int iter = 0;
while(iter == 0 || here != start || there != nstart)
{
// printf("\t%d,%d\n", here, there);
++iter;
// a
int next = -1;
if(adj[there].size() == 1)
{
valid = false;
next = here;
}
else
{
double pi = (p[here] - p[there]).polar();
double nextAngleDiff;
for(int i = 0; i < adj[there].size(); ++i)
{
int cand = adj[there][i];
if(cand == here) continue;
// if((p[there] - p[here]).cross(p[cand] - p[here]) > 0) continue;
double candAngle = (p[cand] - p[there]).polar();
double candAngleDiff = pi - candAngle;
if(candAngleDiff < 0) candAngleDiff += 2 * PI;
// printf("\texamine %d-%d-%d, candAngle %.4lf, candAngleDiff %.4lf\n", here+1,there+1,cand+1, candAngle, candAngleDiff);
if(next != -1 && nextAngleDiff < candAngleDiff) continue;
#define EQUAL(a,b) (fabs((a)-(b)) < 1e-7)
#define D(a,b) ((a)-(b)).norm()
if(next != -1 && EQUAL(nextAngleDiff, candAngleDiff) && D(p[next], p[there]) < D(p[cand], p[there])) continue;
next = cand;
nextAngleDiff = candAngleDiff;
}
}
assert(next != -1);
path.push_back(next);
here = there;
there = next;
}
path.pop_back();
path.pop_back();
/*
for(int i = 0; i < path.size(); ++i)
printf("%d ", path[i]+1);
printf("\n");
*/
// add to seen
for(int i = 0; i < path.size(); ++i)
seen.insert(make_pair(path[i], path[(i+1)%path.size()]));
if(!valid) return 0;
if(path.size() != length) return 0;
// make sure no repeated vertex
sort(all(path));
if(unique(all(path)) != path.end()) return 0;
/* if(counted.count(path)) return 0;
counted.insert(path);*/
// printf("TAKEN\n");
// return..
return 1;
}
int main()
{
point a(1, 1);
point b(2, 1);
point c(1, 2);
int cases;
cin >> cases;
for(int cc = 0; cc < cases; ++cc)
{
cin >> n;
adj.assign(n+1, VI());
p.resize(n+1);
for(int i = 0; i < n; ++i)
{
int here;
cin >> here;
--here;
int y, x;
cin >> x >> y;
p[here] = point(y, x);
int d;
cin >> d;
for(int j = 0; j < d; ++j)
{
int there;
cin >> there;
--there;
adj[here].push_back(there);
}
}
// add an isolated vertex outside: screw outermost polygon....
int minP = 0;
for(int i = 1; i < n; ++i)
if(p[i] < p[minP])
minP = i;
p[n] = p[minP] - point(100, 100);
adj[minP].push_back(n);
adj[n].push_back(minP);
++n;
cin >> length;
counted.clear();
seen.clear();
int ret = 0;
for(int here = 0; here < n; ++here)
{
for(int i = 0; i < adj[here].size(); ++i)
{
int there = adj[here][i];
ret += walk(here, there);
}
}
cout << ret << endl;
}
}
H: Square Destroyer
/backtracking
Set Cover 로 변형해서 풀었다. (집합들은 사각형, 집합의 원소들은 성냥) 이렇게 하면 훨씬 직관적인 구현이 가능한 것 같은 착각... 이 드는데.. -_- 한 번에 나와서 뿌듯함. 하이라이트는 마지막에 Manual IDS 한 것 ㅋㅋㅋㅋㅋ
lang:cpp
int n;
int sol;
bool solved;
void backtrack(int sq, VI& gone, const VVI& contingent, const VVI& affects, int removed)
{
if(sol <= removed) return;
while(sq < gone.size() && gone[sq]) ++sq;
if(gone.size() == sq)
{
sol = removed;
solved = true;
return;
}
for(int i = 0; i < contingent[sq].size(); ++i)
{
int match = contingent[sq][i];
for(int j = 0; j < affects[match].size(); ++j)
{
int nsq = affects[match][j];
++gone[nsq];
}
assert(gone[sq]);
backtrack(sq+1, gone, contingent, affects, removed+1);
for(int j = 0; j < affects[match].size(); ++j)
{
int nsq = affects[match][j];
--gone[nsq];
}
}
}
int main()
{
int cases;
cin >> cases;
for(int cc = 0; cc < cases; ++cc)
{
cin >> n;
int matches = (n + 1) * n * 2;
VI missing(matches);
int k;
cin >> k;
for(int i = 0; i < k; ++i)
{
int m;
cin >> m;
missing[m-1] = 1;
}
int squares = 0;
for(int s = 1; s <= n; ++s)
squares += (n-s+1) * (n-s+1);
VVI contingent(squares);
VVI affects(matches);
#define ACROSS(Y,X) ((Y) * (n+n+1) + (X))
#define DOWN(Y,X) (n + (Y) * (n+n+1) + (X))
int sq = 0;
for(int s = 1; s <= n; ++s)
{
for(int y = 0; y <= n-s; ++y)
for(int x = 0; x <= n-s; ++x)
{
for(int i = 0; i < s; ++i)
{
contingent[sq].push_back(ACROSS(y, x + i));
contingent[sq].push_back(ACROSS(y + s, x + i));
contingent[sq].push_back(DOWN(y + i, x));
contingent[sq].push_back(DOWN(y + i, x + s));
}
for(int i = 0; i < contingent[sq].size(); ++i)
affects[contingent[sq][i]].push_back(sq);
++sq;
}
}
assert(sq == squares);
VI gone(squares);
for(int i = 0; i < matches; ++i)
if(missing[i])
for(int j = 0; j < affects[i].size(); ++j)
gone[affects[i][j]] = 1;
if(count(all(gone), 0) == 0)
{
cout << 0 << endl;
continue;
}
solved = false;
// manual IDS -_ -
sol = 4;
backtrack(0, gone, contingent, affects, 0);
if(solved) { cout << sol << endl; continue; }
sol = 8;
backtrack(0, gone, contingent, affects, 0);
if(solved) { cout << sol << endl; continue; }
sol = 16;
backtrack(0, gone, contingent, affects, 0);
if(solved) { cout << sol << endl; continue; }
sol = 32;
backtrack(0, gone, contingent, affects, 0);
assert(solved);
cout << sol << endl;
}
}
