티스토리 뷰
역시 지난번의 굿바이 한별 팀으로 참가해 종합 9등을 했다. 나는 정말 최악의 대회를 치른 것 같다는 느낌이었다. 다른 팀원들이 그나마 많이 풀어 줘서 이 정도라도 올라온 것 같았다.
CD. Colored-Dealt (0:13:25)
나는 처음에 AB, CD, EF, GH, IJ를 맡기로 했는데, 일단 CD를 읽자마자 쉽다는 확신이 들어서 바로 잡았다. 우선 전부 다 빨간색으로 배정하고, 왼쪽부터 한 개씩 푸른 색으로 바꿔나가는 식으로 최대 가중치 구간을 한 칸씩 이동시킬 수 있다. 이때 인접한 두 쿼리의 차이를 이용해 $N-1$개의 꽃 색을 알 수 있고, 마지막의 경우 첫 번재 쿼리 결과를 이용해 알아낼 수 있다.
#include <string>
#include "colored_dealt.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int ans[1002];
string ansStr;
char dict[] = "0RGB";
string guess(int N){
string str (N, 'R');
ansStr.resize(N);
int val = design(str);
int firstVal = val;
for(int i=0; i<N-1; i++){
str[i] = 'B';
int newVal = design(str);
int diff = (3 - (newVal - val));
ans[i] = diff, ansStr[i] = dict[diff], firstVal -= diff;
// printf("%d: %d %c\n", i, diff, ansStr[i]);
val = newVal;
}
ansStr[N-1] = dict[firstVal];
// printf("ansStr: %s\n", ansStr.c_str());
return ansStr;
}
GH. Gardened-Halved (55:42)
그다음으로 EF를 봤는데 정말 어려워 보여서 패스했다. 이후 GH로 넘어갔더니 투스텝 문제가 나왔다. 보통 투스텝이 어렵지만, 이 문제의 경우 그냥 나무 심는 상황과 경로 간의 일대일대응을 찾는 문제라서 쉽다고 생각했다. 이분 매칭을 짜면 확실히 풀 수 있겠지만 그렇게 하기는 귀찮았고 그냥 가능한 모든 상태에 대해 하나씩 보며 그리디하게 매칭해 주는 코드를 짰다. 운 좋게도 코드가 작동했고 AC를 받았다.
#include <bits/stdc++.h>
#include "gardened_halved.h"
using namespace std;
typedef long long ll;
vector<string> string_list;
vector<vector<int> > way_list;
int color(vector<int> v, string s){
int n = (int)s.size() / 2;
vector<vector<int> > board (n);
for(int i=0; i<n; i++) board[i].resize(n);
int x = 0, y = 0;
for(char c: s){
if(c == 'U'){
if(x<n) board[y][x] = 1;
y++;
}
else x++;
}
for(int i=0; i<n; i++) for(int j=1; j<n; j++) board[i][j] |= board[i][j-1];
int ret = 0;
int k = (int)v.size()/2;
for(int i=0; i<k; i++){
ret += (1<<i) * (board[v[i*2+1]][v[i*2]]);
}
return ret;
}
void init(int n, int k){
vector<string> vs;
vector<vector<int> > vw;
vector<bool> sused;
/// n부터
string str;
for(int i=0; i<n; i++) str.push_back('U'), str.push_back('R');
sort(str.begin(), str.end());
do {
vs.push_back(str);
} while(next_permutation(str.begin(), str.end()));
/// 그다음
if(k==1){
for(int i=0; i<n; i++) for(int j=0; j<n; j++)
vw.push_back(vector<int> {i, j});
}
else{
for(int i=0; i<n; i++) for(int j=0; j<n; j++){
for(int ii=0; ii<n; ii++) for(int jj=0; jj<n; jj++){
if(make_pair(i, j) >= make_pair(ii, jj)) continue;
vw.push_back(vector<int> {i, j, ii, jj});
}
}
}
/// 이제 대응해야 함
sused.resize((int)vs.size());
for(vector<int> v: vw){
vector<int> indices (k*2, -1);
for(int i=0; i<(int)vs.size(); i++){
if(sused[i]) continue;
int col = color(v, vs[i]);
if(indices[col] != -1) continue;
indices[col] = i;
}
for(int i=0; i<k*2; i++){
if(indices[i] == -1) continue;
sused[indices[i]] = 1;
vector<int> stopush;
for(int j=0; j<k; j++){
stopush.push_back(v[j*2]);
stopush.push_back(v[j*2+1]);
stopush.push_back((i>>j)&1);
}
string_list.push_back(vs[indices[i]]);
way_list.push_back(stopush);
}
}
assert(count(sused.begin(), sused.end(), true) == (int)sused.size());
// for(int i=0; i<(int)string_list.size(); i++){
// printf("%s: ", string_list[i].c_str());
// for(auto x: way_list[i]) printf("%d ", x);
// puts("");
// }
}
vector<vector<int> > grow_tree(int K, string M){
int N = (int)M.size() / 2;
init(N, K);
vector<vector<int> > ret (K);
int idx = find(string_list.begin(), string_list.end(), M) - string_list.begin();
for(int i=0; i<K; i++){
ret[i] = vector<int> (2);
ret[i][0] = way_list[idx][i*3], ret[i][1] = way_list[idx][i*3+1];
}
return ret;
}
string restore_route(int N, vector<vector<int> > T){
int K = (int)T.size();
init(N, K);
vector<int> key;
for(auto x: T) for(int y: x) key.push_back(y);
int idx = find(way_list.begin(), way_list.end(), key) - way_list.begin();
return string_list[idx];
}
그리고 여기까지가 대회 중 내 마지막 AC였다.
AB. Adobe-Booked (대회 중 자력 1점)
일단 문제를 많이 변형해야 한다. 문제의 배열 $C$에서 $C_i = j$일 경우 $i$가 $j$번 연달아 나오는 정렬된 배열 $A$를 고민하자. 이런 식으로 새 배열을 만드는 이유는, 어떤 버스의 학생들이 도착하는 숙소 번호가 $A$에서 항상 연속된 구간을 이루기 때문이다. 이것은 그리디적인 관점으로 쉽게 증명할 수 있고, 굳이 그렇게 하지 않아도 자명하다.
그러면 이제 배열 $A$에서 길이 $P$의 구간 $B$개를 겹치지 않게 잡아서, 각 구간의 cost를 최소화시키는 문제가 된다. 이때 cost는 버스 학생들의 이동 거리 합이 되는데, 중간값과의 차이의 절댓값의 합이라는 것이 매우 유명하다. 이런 방식으로 풀면 $O(K^2)$ 언저리에 DP를 통해 풀 수 있다. $K=|A|$라고 생각하면 된다. 대략적인 DP 점화식은 $DP[i][j]$: $i$번 점까지 $j$개의 구간을 잡았을 때 이동 거리 합의 최솟값이라고 하면 되고, 대충 생각하면 세제곱 같지만 $i$가 늘어나는 전이를 일일이 그때그때 보지 말고 앞에서 봐준 걸 뒤에서 활용하는 식으로 잘 관리해서 제곱으로 줄일 수 있다. 이렇게 하면 Subtask 2가 풀릴 것이나, 내가 이 부분을 구현하지는 않았고, kizen이 내 코드를 디버깅해 주면서 짰다.
하여튼 이 문제는 $K \le 250 \ 000$이므로 저렇게는 못 풀고 최적화를 해야 한다. 먼저 $B$개의 길이 $P$인 구간을 고른다는 건 조금 복잡하다. 그냥 전체 수열을 $B$개의 구간으로 분할하고, 각 구간에서 $P$의 부분구간을 고르는 식으로 생각하는 게 더 좋다. 이러면 $Cost[i][j]$를 정의할 수 있는데, $Cost[i][j]$는 $[i, j]$ 구간에서 길이 $P$의 부분구간을 하나 골랐을 때 최소 이동 거리라고 정의할 수 있다. (만약 $[i, j]$ 길이가 $P$ 미만이라면 $\infty$로 정의한다.) 이제 여기에서 $Cost$가 monge array임을 관찰할 수 있다. 증명은 굳이 하지 않겠고, 그냥 그림을 그려 보면 바로 납득할 수 있다.
monge array, 정확히 $B$개 구간 -> 바로 Alien's trick이라는 감이 와야 한다. 물론 나는 아직 대회에서 Alien's trick을 써먹어 본 적이 없어서 바로 감이 오진 않았다. 이후 구사과님의 블로그에 있는 Alien's Trick 파트를 정독하고 구현에 들어갔다. 그리고 그대로 망했다. 문제 풀이는 이게 끝이지만, Alien's trick에 그걸 역추적하는 부분까지 결국 대회 시간 안에 디버깅하지 못했다. 팀원에게 디버깅을 맡겨 보기도 했지만 소용없었고, 결국 대회 다음 날 낮에 코드를 다시 디버깅해서 풀었다.
이 문제를 풀 때는 조금 더 구현을 편하게 하는 방법이 있다. 일단 $DP$를 돌리면서 pair로 최소 이동 거리 합과 선택한 구간 개수를 가지고 다니면 이동 거리가 같을 때 구간 개수를 최소/최대로 유도할 수 있다. 이렇게 하면 반정수 트릭 같은 걸 쓸 필요 없이 단순하게 이분 탐색을 해서 적당한 $\lambda$를 찾아줄 수 있고, 이 뒤는 그냥 Alien's trick 역추적을 그대로 구현하면 충분하다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
int b, p;
ll arr[250002];
ll sum[250002];
void input();
ll binarySearch();
void getSolution(ll);
void output(ll);
int calc(ll);
int main(){
input();
ll key = binarySearch();
getSolution(key);
output(key);
}
void input(){
vector<int> v;
// n = rand() % 150000 + 100000, b = rand() % 2500 + 3, p = rand() % (n/b-1) + 1;
// printf("%d %d %d", n, b, p);
scanf("%d %d %d", &n, &b, &p);
for(int i=0; i<n; i++){
int x;
scanf("%d", &x);
while(x--) v.push_back(i);
}
// for(int i=0; i<n; i++) v.push_back((ll(rand())*rand()+rand())%250000);
// sort(v.begin(),v.end());
n = (int)v.size();
for(int i=1; i<=n; i++) arr[i] = v[i-1];
for(int i=1; i<=n; i++) sum[i] = sum[i-1] + arr[i];
}
pair<ll, ll> DP[250002];
int dpMinIdx[250002];
int track[250002];
ll grade(int r){
int l = r-p+1;
int m = (l+r)/2;
return (sum[r] - sum[m] - arr[m] * (r-m)) + (arr[m] * (m-l) - (sum[m-1] - sum[l-1]));
}
void doDP(ll lambda, bool mode){
// printf("DP lambda %lld mode %d\n", lambda, mode);
fill(DP, DP+n+1, make_pair(1e18, 1e18));
DP[0] = make_pair(0, 0), dpMinIdx[0] = 0;
/// 변수 선언
pair<ll, ll> minCost = make_pair(1e18, 1e18);
int minIdx = 0;
for(int i=1; i<p; i++){
DP[i] = make_pair(1e18, 1e18), dpMinIdx[i] = 0, track[i] = 0;
}
for(int i=p; i<=n; i++){
/// i-p+1 ~ i 구간을 검사해 본다
if(minCost >= make_pair(DP[dpMinIdx[i-p]].first + grade(i) - lambda, DP[dpMinIdx[i-p]].second-(mode?1:-1))){
minCost = make_pair(DP[dpMinIdx[i-p]].first + grade(i) - lambda, DP[dpMinIdx[i-p]].second-(mode?1:-1));
minIdx = dpMinIdx[i-p];
}
DP[i] = minCost;
track[i] = minIdx;
dpMinIdx[i] = (DP[dpMinIdx[i-1]] >= DP[i]) ? i : dpMinIdx[i-1];
// printf("DP[%d]: (%lld, %lld)\n", i, DP[i].first, DP[i].second);
}
}
int calc(ll lambda, int x){
doDP(lambda, x);
return abs(DP[n].second);
}
ll binarySearch(){
const ll P = 1e17;
ll L = -1e12, R = 1e12, ANS = R; /// 처음으로 초과하는 반정수점 찾기
while(L<=R){
ll M = (L+R+P+P)/2-P;
int v = calc(M, 1);
// printf("lambda %lld: v %d\n", M*2+1, v);
if(v >= b) ANS = M, R = M-1;
else L = M+1;
}
assert(calc(ANS, 0) <= b && b <= calc(ANS, 1));
return ANS;
}
vector<int> vec1, vec2;
vector<int> intervals;
void getSolution(ll lambda){
doDP(lambda, 1);
/// track으로 몇 번 썼는지 본다
int x = n;
while(x){
vec1.push_back(x);
x = track[x];
}
for(auto &x: vec1) x++;
vec1.push_back(1);
reverse(vec1.begin(), vec1.end());
int k1 = abs(DP[n].second);
doDP(lambda, 0);
/// track으로 몇 번 썼는지 본다
x = n;
while(x){
vec2.push_back(x);
x = track[x];
}
for(auto &x: vec2) x++;
vec2.push_back(1);
reverse(vec2.begin(), vec2.end());
int k2 = abs(DP[n].second);
int k = b;
// assert(k2 <= b && b <= k1);
if(k1 == k) intervals = vec1;
else if(k2 == k) intervals = vec2;
else if(k2 < k && k < k1){
/// 두 해를 잘 합친다
for(int i=0, j=0; ; ){
if(vec1[i+1] > vec2[j+1]) j++;
else if(vec1[i] < vec2[j] || i-j < k-k2) i++;
else{
for(int a=0; a<=i; a++) intervals.push_back(vec1[a]);
for(int a=j+1; a<(int)vec2.size(); a++) intervals.push_back(vec2[a]);
assert((int)intervals.size() == b + 1);
return;
}
}
}
else exit(0);
}
ll ans;
vector<vector<int> > ansV;
void output(ll lambda){
// printf("intervals: ");
// for(auto x: intervals) printf("%d ", x);
// puts("");
for(int i=0; i<b; i++){
int s = intervals[i], e = intervals[i+1] - 1;
ll minV = 1e18; int minX = -1;
for(int j=s+p-1; j<=e; j++){
ll v = grade(j);
if(minV > v) minV = v, minX = j;
}
ans += minV;
int x = minX;
ansV.push_back(vector<int> ());
ansV.back().push_back(arr[x - p/2]);
for(int j=x-p+1; j<=x; j++) ansV.back().push_back(arr[j]);
}
assert(ans - lambda * b == DP[n].first);
printf("%lld\n", ans);
for(auto v: ansV){
for(auto x: v) printf("%d ", x);
puts("");
}
}
만약 이후에 문제를 더 업솔빙하게 된다면 추가할 예정이다.