Reply Code Challenge 2022 - Teen Edition 후기

선린 3인팟 조찬우, 김채완, 장태환 님과 함께 Plz No Geometry 라는 팀명으로 참가했다.

이번에도 연습은 모종의 이유로 하지 못했다. ㅋㅋ

 

대회는 ICPC 스타일의 5문제를 4시간 동안 푸는 식으로 진행되었고, 각 문제당 5개의 섭태가 있었다.

내가 A, 채완님이 B, 태환님이 C, 찬우님이 D를 먼저 잡고 각 문제가 해결되면 D, E에 붙어서 같이 고민하는 전략을 들고 시작했다.

 

A는 lcm 쓰는 무지성 문제였는데, 구코잼처럼 Case #1: 이거 출력하는 걸 빼먹어서 조금 헤맸다.

 

D, E를 쓱 읽어보니 D는 문제 이해도 힘들었고 E는 말도 안 되는 걸 요구하고 있었다.. 그래도 E의 범위가 작아 Naive를 시도해볼 수 있겠다는 생각이 들어 완탐을 짜기 시작했다. 풀이는 대충 백트래킹을 이중으로 돌면서 각 열 별로 가능한 상태를 모두 구해놓고, 이 상태들의 가능한 조합을 모두 시도해보면서 조건을 만족하는지를 확인하는 식이었다. 대충 계산한 시복은 $O(N^{N^N})$ 인데, 테케가 험악하게 주어지지만 않는다면 어느 정도 커팅이 될 거라 예상했다.

 

내가 머리를 쥐어뜯으며 E를 짜는 동안, B와 C를 셋이서 열심히 고민하더니 잘 해결해주었다. 사실 난 저기에 끼지 않아서 자세한 상황은 모른다. 뭔가 지문 상태가 별로였다는 듯.

 

반신반의하면서 짠 Naive가 예제를 아주 빠르게 풀어냈다. 그래도 혹시 몰라서 팀원들 몰래 제출해봤더니 섭태 2까지는 수월하게 풀렸고, 섭태 3부터는 겁나 오래 걸렸다. 그래서 채완님의 도움을 받았는데, 이게 테케를 하나씩 넣으니 잘만 나오더라. 그래서 섭태 3, 4를 해결할 수 있었다. 당시에는 반쯤 정신이 나가서 몰랐는데 지금 글 쓰면서 생각해보니 걍 테케 하나 끝나고 상태 벡터를 안 비워준 거였다;; 섭태 5는 왠지 모르겠는데 엄청 오래 걸려서 대회 끝날 때까지 긁지 못했다. 그리고 대회 중에 할 수 있는 커팅은 다 했다고 팀원들에게 말했던 것 같은데, 지금 보니 좀 큼지막하게 자를 수 있는 것들이 눈에 보인다... ㅈㅅ;; ㅋㅋ

 

대충 이런 걸 짰다.

#include<bits/stdc++.h>
using namespace std;
#define fastio cin.tie(0)->sync_with_stdio(0)
#define fi first
#define se second
#define nm (nl + nr >> 1)
#define pb(x) push_back(x)
#define all(v) (v).begin(), (v).end()
#define zip(v) (v).erase(unique(all(v)), (v).end())
#define dem_plc(x) cout << fixed, cout.precision(x)
#define ox(t) cout << (t ? "YES" : "NO") << '\n'
#define continue(x) { cout << x << '\n'; continue; }
#define myexit(x) return cout << x, 0
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<int, ll> pil;
typedef pair<ll, int> pli;
typedef pair<pii, int> ppi;
typedef pair<int, pii> pip;
typedef pair<pll, ll> ppl;
typedef pair<ll, pll> plp;
const ll mod = 1e9 + 7;
const ll INF = 2e9;
const ll LINF = 4e18;
const db PI = acos(-1);
const int N = 13;
// templete end

int n, lmn, lmx;
int x1[N], y1_[N], z1[N], x2[N], y2[N], z2[N];
int a[N][N], tmp[N], b[N], ans[N][N];
vector<vector<pii>> v[N];
bool flag;

void blank(int i, int now, int cnt, int sum) {
	if(now == cnt) {
		int mx = 0;
		for(int j = 0; j <= cnt; j++) mx = max(mx, b[j]);
		if(mx < z1[i]) return;
		vector<pii> vv;
		int idx = 1;
		for(int j = 1; j <= cnt; j++) {
			idx += b[j - 1];
			vv.push_back({idx, tmp[j]});
			idx += tmp[j];
		}
		v[i].push_back(vv);
		return;
	}
	if(now == -1) {
		for(int x = max(sum - (cnt - now - 1) * z1[i], 0); x <= min(sum - cnt + now + 2, z1[i]); x++) {
			b[now + 1] = x;
			blank(i, now + 1, cnt, sum - x);
		}
		return;
	}
	if(now + 1 == cnt) {
		assert(0 <= sum && sum <= z1[i]);
		b[now + 1] = sum;
		blank(i, now + 1, cnt, 0);
		return;
	}
	for(int x = max(sum - (cnt - now - 1) * z1[i], 1); x <= min(sum - cnt + now + 2, z1[i]); x++) {
		b[now + 1] = x;
		blank(i, now + 1, cnt, sum - x);
	}
}

void get(int i, int now, int cnt, int sum) {
	if(now == cnt) {
		blank(i, -1, cnt, n - x1[i]);
		return;
	}
	if(now + 1 == cnt) {
		assert(1 <= sum && sum <= lmx);
		tmp[now + 1] = sum;
		get(i, now + 1, cnt, 0);
		return;
	}
	for(int x = max(sum - (cnt - now - 1) * lmx, 1); x <= min(sum - cnt + now + 1, lmx); x++) {
		tmp[now + 1] = x;
		get(i, now + 1, cnt, sum - x);
	}
}

bool check() {
	for(int i = 1; i <= n; i++) {
		int xx = 0, yy = 0, zz = 0, bl = 0;
		for(int j = 1; j <= n; j++) {
			if(a[i][j]) {
				xx++;
				if(!a[i][j - 1]) yy++;
				bl = 0;
			}
			else {
				zz = max(zz, ++bl);
			}
		}
		if(xx != x2[i] || yy != y2[i] || zz != z2[i]) return 0;
	}
	return 1;
}

void sol(int now) {
	if(flag) return;
	if(now == n) {
		if(!check()) return;
		for(int i = 1; i <= n; i++) {
			for(int j = 1; j <= n; j++) {
				ans[i][j] = a[i][j];
			}
		}
		flag = 1;
		return;
	}
	for(const auto &vv : v[now + 1]) {
		for(int i = 1; i <= n; i++) a[i][now + 1] = 0;
		for(const auto &[idx, k] : vv) {
			for(int i = idx; i < idx + k; i++) a[i][now + 1] = 1;
		}
		sol(now + 1);
		if(flag) return;
	}
}

void solve() {
	cin >> n >> lmn >> lmx;
	for(int i = 1; i <= n; i++) cin >> x1[i];
	for(int i = 1; i <= n; i++) cin >> y1_[i];
	for(int i = 1; i <= n; i++) cin >> z1[i];
	for(int i = 1; i <= n; i++) cin >> x2[i];
	for(int i = 1; i <= n; i++) cin >> y2[i];
	for(int i = 1; i <= n; i++) cin >> z2[i];
	for(int i = 1; i <= n; i++) get(i, 0, y1_[i], x1[i]);
	sol(0);
	if(!flag) cout << "I'm so sad\n";
	else {
		for(int i = 1; i <= n; i++) {
			for(int j = 1; j <= n; j++) {
				cout << ans[i][j] << ' ';
			}
			cout << '\n';
		}
	}
}

int main()
{
	fastio;
	int tc; cin >> tc;
	for(int TC = 1; TC <= tc; TC++) {
		flag = 0;
		cout << "Case #" << TC << ":\n";
		solve();
	}
}

 

이후 태환님은 졸려서 탈주하셨고, 채완님과 찬우님은 D를 열심히 트라이하고 나는 옆에서 치어리딩하다가 끝났다.

 

 

 

참가자 풀이 어떻게 되는지는 모르겠지만 1150팀 중 15등이라는 좋은 성적으로 마무리했다.

재밌고 멋진 경험이었고, 늦은 시간에 고생한 팀원들 모두 수고하셨습니다 :D