고급반 4주차 풀이 - 파이팅

1. [18857] 집 떠나와 열차 타고 (Diamond V)

BCC를 기준으로 생각해봅시다.

그래프가 선인장이기 때문에, BCC는 '간선 1개'이거나 '사이클 1바퀴'밖에 없습니다.

그러므로, \( 1 \Rightarrow N \)의 경로와 닿는 모든 BCC를 들고 온 뒤, 두 경우에 맞게 처리해주면 됩니다.

• 간선 1개: 그 간선을 자르면 됩니다.
• 사이클 1바퀴: 경로에 속한 가장 짧은 간선과 경로에 속하지 않은 가장 짧은 간선을 자르면 됩니다.

각 BCC별로 저 값을 구해둔 뒤, 최솟값을 찾아주면 됩니다.

int n, m;
vector<pi4> adj[402020];

int ord=0, ind[402020]; stack<pi3> stk;
int cnt = 0, num[429020];
int dfs(int now, int pre){
	ord += 1; ind[now] = ord;
	int res = ind[now];
	for (pi4 edg : adj[now]){
		int nxt = edg.fr.fr, wvi = edg.fr.sc; if (nxt == pre){ continue; }
		if (ind[now] > ind[nxt]){ stk.push({ {now, nxt}, wvi }); }
		if (ind[nxt] > 0){ res = min(res, ind[nxt]); }
		else{
			int val = dfs(nxt, now);
			res = min(res, val);
			if (val >= ind[now]){
				cnt += 1;
				while (!stk.empty()){
					pi3 p = stk.top(); stk.pop();
					int v = p.fr.fr, w = p.fr.sc;
					int wvi = p.sc; int vwi = adj[w][wvi].fr.sc;
					adj[v][vwi].sc.sc = adj[w][wvi].sc.sc = cnt;
					num[cnt] += 1;
					if (p.fr == mkp(now, nxt)){ break; }
				}
			}
		}
	}
	return res;
}

bool chk[402020]; pi2 pth[402020]; int pc;
bool dfsp(int now, int idx){
	chk[now] = 1; pth[idx] = {now, -1};
	if (now == n){ pc = idx; return 1; }
	for (pi4 edg : adj[now]){
		int nxt = edg.fr.fr; if (chk[nxt]){ continue; }
		int clr = edg.sc.sc; pth[idx].sc = clr;
		if ( dfsp(nxt, idx+1) ){ return 1; };
	}
	return 0;
}

int res = 0;
void f(int now, int pre, const int& ed, const int& col, int mn){
	if (now == ed){ res += mn; return; }
	for (pi4 edg : adj[now]){
		int nxt = edg.fr.fr; if (nxt == pre){ continue; }
		int clr = edg.sc.sc; if (col != clr){ continue; }
		int wei = edg.sc.fr;
		f(nxt, now, ed, col, min(mn, wei));
	}
}

void Main(){
	cin >> n >> m;
	while (m--){
		int v, w, x; cin >> v >> w >> x;
		int vl = adj[v].size(), wl = adj[w].size();
		adj[v].push_back({ {w, wl}, {x, 0} });
		adj[w].push_back({ {v, vl}, {x, 0} });
	}
	for (int i = 1; i <= n; i++){ if (ind[i] == 0){ int _ = dfs(i, -1); } }
	/*for (int bcc = 1; bcc <= cnt; bcc++){
		cout << "BCC " << bcc << ": " << endl;
		for (int v = 1; v <= n; v++){
			for (pi4 e : adj[v]){
				int w = e.fr.fr, c = e.sc.sc;
				if (c != bcc){ continue; }
				cout << v << ' ' << w << "   ";
			}
		}
		cout << endl << flush;
	}*/
	bool _ = dfsp(1, 0);
	int ans = 1e9;
	//cout << "PATH "; for (int i = 0; i <= pc; i++){ cout << " (" << pth[i].fr << "," << pth[i].sc << ") "; } cout << endl << flush;
	int st = 0; while (st < pc){
		int ed = st;
		while (ed < pc){
			if (pth[st].sc == pth[ed].sc){ ed += 1; }
			else{ break; }
		}
		int stv = pth[st].fr, edv = pth[ed].fr;
		int col = pth[st].sc;
		if (num[col] == 1){
			for (pi4 edg : adj[stv]){
				int nxt = edg.fr.fr; if (nxt != edv){ continue; }
				ans = min(ans, edg.sc.fr);
				//cout << "FIND " << st << ' ' << ed << " = " << edg.sc.fr << endl << flush;
			}
		}
		else{
			res = 0; f(stv, -1, edv, col, 1e9);
			ans = min(ans, res);
			//cout << "FIND " << st << ' ' << ed << " = " << res << endl << flush;
		}
		st = ed;
	}
	cout << ans;
}

2. [18858] 훈련소로 가는 날 (Gold III)

\( DP_{i, j, k} := \) 길이가 \( i \)이며 \( A_{i} = j \)이고, \( k = (A_{i-1} < A_{i}) \)인 수열의 개수

를 정의하면, 점화식은 아래 3가지 경우로 나눌 수 있습니다.

 

이번에 고르는 수를 \( x \)라고 하면,

• \( j < x \; DP_{i, x, 1} \): \( DP_{i-1, j, 0} + DP_{i-1, j, 1} \)
• \( j = x \; DP_{i, x, 0} \): \( DP_{i-1, j, 0} + DP_{i-1, j, 1} \)
• \( j > x \; DP_{i, x, 0} \): \( DP_{i-1, j, 0} \)

문제의 답은 \( \sum_{x=1}^{x=M} (DP_{N, x, 0} + DP_{N, x, 1}) \)가 됩니다.

const ll mod = 998244353;

ll dp[1020][120][2];

void Main(){
	int n, m; cin >> n >> m;
	for (int i = 1; i <= m; i++){ dp[1][i][0] = 1; }
	for (int i = 2; i <= n; i++){
		for (int v2 = 1; v2 <= m; v2++){
			for (int v1 = 1; v1 <= m; v1++){
				if (v1 < v2){
					dp[i][v2][1] += dp[i-1][v1][0]+dp[i-1][v1][1];
					dp[i][v2][1] %= mod;
				}
				else if (v1 == v2){
					dp[i][v2][0] += dp[i-1][v1][0]+dp[i-1][v1][1];
					dp[i][v2][0] %= mod;
				}
				else{
					dp[i][v2][0] += dp[i-1][v1][0];
					dp[i][v2][0] %= mod;
				}
			}
			//cout << "DP " << i << ' ' << v2 << " = " << dp[i][v2][0] << ' ' << dp[i][v2][1] << endl;
		}
	}
	ll ans = 0;
	for (int i = 1; i <= m; i++){
		ans += dp[n][i][0] + dp[n][i][1]; ans %= mod;
	}
	cout << ans;
}

3. [18859] 부모님께 큰절 하고 (Platinum IV)

우선 배열을 정렬시키고 시작합시다. 즉, 지금부터 \( A_{i} \le A_{i+1} \)를 만족합니다.

이렇게 하면 감소와 증가가 바뀌는 부분이 최솟값, \( A_{1} \)이 됩니다.

 

이제부터 설명하다가 중간중간에 Case가 나오게 됩니다. (제 체감상) 이 문제는 Case Work 문제이기 때문입니다.

Case1. \( A_{1} = A_{2} \): 공차 0의 등차수열이 되는데, 이는 예술적이지 않습니다. "No"

 

이제 \( A_{1} \)의 오른쪽에 \( A_{2} \)를 놓아봅시다.

오른쪽 방향으로는 정의상 공차가 1 이상인 등차수열이기 때문에, 그 뒤에 오게 되는 원소들은 정해지게 됩니다. 그러니 되는대로 연결시켜봅시다.

 

이제 선택되지 않은 원소들의 최대공약수 \( g \)를 구해봅시다.

Case2. 선택되지 않은 원소가 없다: 수열 자체가 등차수열인데, 마지막 원소 하나 뽑아서 맨 앞으로 보내면 예술적인 절이 됩니다. "Yes"

 

최대공약수를 구하는 이유는 왼쪽으로 가는 등차수열의 공차가 최대공약수가 되어야 하기 때문입니다.

만약 이 과정에서 등차수열이 중간 항을 건너뛴다면, 그 중간 항을 오른쪽 등차수열에서 들고 오면 됩니다.

Case3. 그 항이 오른쪽 등차수열에 없다: 왼쪽을 등차로 만들 수 없으니 예술적인 절을 할 수 없습니다. "No"

Case4. 왼쪽 수열에 수가 중복된다: 왼쪽을 등차로 만들 수 없으니 예술적인 절을 할 수 없습니다. "No"

 

이렇게 왼쪽 등차수열이 완성되었다면, 이제 오른쪽 등차수열이 아직 등차수열인지 판별해주면 됩니다.

Case5. 오른쪽 수열이 등차수열이다: 예술적인 절을 찾았습니다! "Yes"

Case6. 오른쪽 수열이 등차수열이 아니다: 아쉽게도 예술적이지 못했습니다. "No"

ll gcd(ll a, ll b){ return b==0 ? a : gcd(b, a%b); }

ll arr[402020];
bool chk[402020];

void Main(){
	int n; cin >> n;
	for (int i = 1; i <= n; i++){ cin >> arr[i]; }
	sort(arr+1, arr+n+1);
	ll mn = arr[1], dif = arr[2]-arr[1];
	if (dif == 0){ cout << "No"; return; }
	ll val = mn;
	multiset<ll> s;
	for (int i = 1; i <= n; i++){
		if (val == arr[i]){ chk[i] = 1; val += dif; s.insert(arr[i]); }
	}
	int lst = 1; ll g = -1;
	for (int i = 1; i <= n; i++){
		if (!chk[i]){
			if (g == -1){ g = arr[i]-arr[lst]; }
			else{ g = gcd(g, arr[i]-arr[lst]); }
			lst = i;
		}
	}
	if (lst == 1){ cout << "Yes"; return; }
	val = mn;
	for (int i = 1; i <= n; i++){
		if (chk[i]){ continue; }
		if (val == arr[i]){ cout << "No"; return; }
		while (val+g < arr[i]){ val += g;
			if (s.count(val) == 0){ cout << "No"; return; }
			s.erase(s.find(val));
		}
		val = arr[i];
	}
	dif = *(++s.begin()) - *(s.begin());
	val = mn;
	for (ll x : s){
		//cout << "X " << x << ' ' << dif << endl;
		if (x != val){ cout << "No"; return; }
		val += dif;
	}
	cout << "Yes";
}

4. [18860] 대문 밖을 나설 때 (Platinum II)

트리 DP입니다.

\( DP_{v} := \) \( v \)번 정점이 꽉 찰 때까지의 시간

\( ADD_{v} := \) \( DP_{v} \)시간 후 \( v \)까지 다 채우고 남는 석유의 양

\( SUM_{v} := \) \( v \)번 정점을 루트로 하는 서브트리의 석유 탱크의 크기의 합

\( CNT_{v} := \) \( v \)번 정점을 루트로 하는 서브트리의 펌프의 개수

 

점화식은 \( v \)의 두 자식 \( w_{1}, w_{2} \) 중 먼저 채울 값을 골라주면 됩니다.

두 경우가 대칭적이니, \( w_{1} \)을 먼저 켜는 경우만 설명하겠습니다.

 

우선 \( DP_{w_{1}} \)의 시간동안 \( w_{1} \)과 이의 서브트리를 석유로 채운 뒤, \( ADD_{w_{1}} \)만큼의 석유가 \( w_{2} \)의 서브트리 속 자식에 들어가게 됩니다.

그러니 첫 1시간동안은 \( ADD_{w_{1}} \)개의 펌프가 켜지고, 나머지는 그 다음 시간 동안 \( w_{1} \)의 펌프에서 나오는 석유에 의해 모두 켜지게 됩니다.

그러니 석유의 추가량은 1초동안 \( CNT_{w_{1}} + ADD_{w_{1}} \)가 되었다가, \( CNT_{v} \)가 됩니다.

이를 토대로 \( w_{2} \)까지 다 채우는데 걸리는 시간을 계산할 수 있고,

\( w_{1} \)과 \( w_{2} \)가 다 채워졌으니 이제 \( CNT_{v} \)만큼 올라오는 석유로 \( v \)번 정점을 채우는데의 시간과 그 때 넘치는 석유의 양을 계산해주면 됩니다.

 

문제의 답은 \( DP_{1} \)입니다.

ll arr[262150], siz[262150]; int cnt[262150];
pl2 dp[262150];

pl2 f(int i1){ int i2 = i1^1, i = i1>>1;
	ll tim = dp[i1].fr, ovf = dp[i1].sc, num = cnt[i1];
	ll val = siz[i2] + arr[i];
	//cout << "(VAL " << siz[i2] << ' ' << num << ") ";
	val -= ovf; num += ovf;
	val -= num; num = cnt[i]; tim += 1;
	if (val <= 0){ return {tim, -val}; }
	ll t = (val+num-1) / num;
	return {tim+t, t*num - val};
}

void Main(){
	int n; cin >> n;
	for (int i = 1; i <= n; i++){ cin >> arr[i]; }
	for (int i = n; i >= 1; i--){
		siz[i] = arr[i];
		int i1 = i<<1, i2 = i<<1|1;
		//cout << "DP " << i << " = ";
		if (i2 > n){
			dp[i] = {arr[i], 0}; cnt[i] = 1;
			//cout << dp[i].fr << ' ' << dp[i].sc << endl;
		}
		else{
			siz[i] += siz[i1] + siz[i2]; cnt[i] = cnt[i1] + cnt[i2];
			pl2 p1 = f(i1), p2 = f(i2);
			if (p1.fr != p2.fr){ dp[i] = min(p1, p2); } else{ dp[i] = max(p1, p2); }
			//cout << dp[i].fr << ' ' << dp[i].sc << " | " << p1.fr << ' ' << p1.sc << " / " << p2.fr << ' ' << p2.sc << endl;
		}
	}
	cout << dp[1].fr;
}

5. [18861] 가슴 속에 무엇인가 (Ruby V)

Link-Cut Tree로 Maximum Spanning Tree를 관리하면 됩니다.

 

1번 쿼리는 Link 연산으로 처리할 수 있습니다.

물론 Link로 인해 사이클이 생긴다면 사이클에서 가장 작은 간선을 Cut해줘야 합니다.

루트에서 연결하는 게 아니니 MakeRoot(v) 연산이 추가적으로 필요합니다.

 

3번 쿼리는 Path Minimum Query로 처리할 수 있습니다.

물론 그 전에 \( v \)와 \( w \)가 같은 트리에 속해있는지 판별해줘야 합니다.

 

문제는 2번 쿼리인데, Maximum Spanning Tree를 관리하는데 Cut 연산을 해줘야 합니다.

이는 곧 2번 쿼리를 처리하다가, 1번 쿼리에서 Cut했던 간선을 다시 연결해야 할 수도 있다는 의미가 됩니다.

하지만 그럴 걱정은 안 해도 됩니다.

1번 쿼리에서 자른 간선은 정의상 사이클을 이루는 남은 간선들보다 한계 심박수가 낮으므로, 사이클을 이루는 간선들이 터진다면 없어진 간선들도 같이 터지기 때문에 걱정하지 않아도 됩니다.

 

2번 쿼리를 처리하기 위해서는 현재 링크컷 트리에 저장되어있는 간선들을 모아서 '간선 리스트'를 추가적으로 관리하고 있어야 합니다.

struct Node{
	Node *p = nullptr, *l = nullptr, *r = nullptr;
	pi2 val = {INF, INF}, mn = {INF, INF}; bool flp = 0;
	int idx = 0;
};
inline bool isr(Node *nod){
	if (!nod->p){ return 1; }
	return nod->p->l != nod && nod->p->r != nod;
}

void pro(Node *nod){ if (!nod){ return; }
	if (!nod->flp){ return; }
	swap(nod->l, nod->r);
	if (nod->l){ nod->l->flp ^= 1; }
	if (nod->r){ nod->r->flp ^= 1; }
	nod->flp = 0;
}
void upd(Node *nod){ pro(nod);
	nod->mn = nod->val;
	if (nod->l){ nod->mn = min(nod->mn, nod->l->mn); }
	if (nod->r){ nod->mn = min(nod->mn, nod->r->mn); }
}

void rot(Node *now){
	if (isr(now)){ return; }
	Node *par = now->p; Node *pre = par->p;
	if (isr(par)){ now->p = pre; }
	else{
		if (pre->l == par){ pre->l = now; } else{ pre->r = now; }
		now->p = pre;
	}
	Node *nxt = nullptr;
	if (par->l == now){
		par->l = nxt = now->r;
		now->r = par;
	}
	else{
		par->r = nxt = now->l;
		now->l = par;
	}
	par->p = now;
	if (nxt){ nxt->p = par; }
	upd(par); upd(now);
}
void spl(Node *now){
	while (!isr(now)){
		Node *par = now->p; Node *pre = par->p;
		pro(pre); pro(par); pro(now);
		if (!isr(par)){
			if ((par->l == now) == (pre->l == par)){ rot(par); }
			else{ rot(now); }
		}
		rot(now);
	}
	pro(now);
}

void acs(Node *now){
	spl(now); now->r = nullptr;
	while (now->p){
		spl(now->p); now->p->r = now;
		spl(now);
	}
}
void chr(Node *now){
	acs(now); spl(now); now->flp ^= 1;
}
Node* fnp(Node *now){
	acs(now); pro(now);
	if (!now->l){ return nullptr; }
	now = now->l; pro(now);
	while (now->r){ now = now->r; pro(now); }
	spl(now); return now;
}
Node* fnr(Node *now){
	acs(now); pro(now); while (now->l){ now = now->l; pro(now); }
	spl(now); return now;
}

void lnk(Node *now, Node *par){ chr(now);
	acs(now); acs(par);
	now->l = par; par->p = now;
	upd(now);
}
void cut(Node *now){
	acs(now);
	now->l->p = nullptr; now->l = nullptr;
	upd(now);
}
Node* lca(Node *v, Node *w){
	acs(v); acs(w); spl(v);
	if (v->p){ return v->p; } else{ return v; }
}

void cut(Node *v, Node *w){
	if (fnp(v) == w){ return cut(v); } else{ return cut(w); }
}
pi2 qry(Node *v, Node *w){ Node *l = lca(v, w);
	pi2 res = l->val;
	acs(v); spl(l); if (l->r){ res = min(res, l->r->mn); }
	acs(w); spl(l); if (l->r){ res = min(res, l->r->mn); }
	return res;
}

Node* vtx[718020]; pi2 edg[718020];
set<pi2> cur;

void dfs(Node* now){
	if (now->l){ dfs(now->l); }
	cout << "NODE " << now->idx << ' ' << now << endl;
	cout << "PARENT " << now->p << endl;
	cout << "CHILDS " << now->l << ' ' << now->r << endl;
	cout << endl;
	if (now->r){ dfs(now->r); }
}

void Main(){
	int n, q; cin >> n >> q;
	for (int i = 1; i <= n; i++){ vtx[i] = new Node; vtx[i]->idx = i; }
	int ptr = n; while (q--){ ptr += 1;
		int typ; cin >> typ;
		if (typ == 1){
			int v, w, x; cin >> v >> w >> x;
			vtx[ptr] = new Node; vtx[ptr]->idx = ptr;
			vtx[ptr]->val = vtx[ptr]->mn = {x, ptr};
			edg[ptr] = {v, w};
			if (fnr(vtx[v]) == fnr(vtx[w])){
				pi2 p = qry(vtx[v], vtx[w]);
				int val = p.fr, idx = p.sc;
				//cout << val << " vs " << x << endl << flush;
				if (val >= x){ goto done; }
				int a = edg[idx].fr, b = edg[idx].sc;
				cut(vtx[a], vtx[idx]); cut(vtx[idx], vtx[b]);
				cur.erase( cur.find(p) );
			}
			lnk(vtx[v], vtx[ptr]); lnk(vtx[ptr], vtx[w]);
			cur.insert({x, ptr});
			done: ;
		}
		if (typ == 2){
			int x; cin >> x;
			while (!cur.empty()){
				pi2 p = *( cur.begin() );
				int val = p.fr, idx = p.sc;
				if (val >= x){ break; }
				int a = edg[idx].fr, b = edg[idx].sc;
				cut(vtx[a], vtx[idx]); cut(vtx[idx], vtx[b]);
				cur.erase( cur.begin() );
			}
		}
		if (typ == 3){
			int v, w; cin >> v >> w;
			//cout << "ROOT " << fnr(vtx[v]) << ' ' << fnr(vtx[w]) << endl;
			if (fnr(vtx[v]) != fnr(vtx[w])){ cout << 0 << endl; }
			else{ cout << qry(vtx[v], vtx[w]).fr << endl; }
		}
		/*cout << "Current Tree" << endl;
		for (int j = 1; j <= ptr; j++){
			if (!vtx[j]){ continue; }
			if (!isr(vtx[j])){ continue; }
			dfs(vtx[j]); cout << "-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-" << endl;
		}
		cout << flush;*/
	}
}

6. [18862] 아쉬움이 남지만 (Diamond IV)

트리 DP 문제입니다.

\( DP_{v} := \) \( v \)번 정점에서 출발했을 때 회수할 수 있는 탄피의 개수

\( MP_{v, x} := \) \( v \)번 정점에서 출발했는데 회수하지 못한 탄피들 중, \( v \)의 부모가 \( x \) 이상의 높이를 가지고 있다면 회수 가능한 탄피의 개수

 

이제 전파를 해봅시다. \( v \rightarrow w \)인 모든 \( w \)에 대해 계산이 끝났다고 가정하겠습니다.

이제 조건을 2개로 나눠봅시다.

• \( H_{v} \ge H_{w} \): 우선 \( DP_{w} \)개의 탄피를 회수할 수 있으며, 회수하지 못한 탄피들 중 \( \sum_{x \le H_{v}} MP_{w, x} \)개의 탄피를 추가적으로 회수할 수 있습니다.
• \( H_{v} \lt H_{w} \): 아쉽게도 \( w \)번 정점으로 갈 수 없으니, 아무것도 회수할 수 없습니다.
  \( MP_{v, 2H_{w} - H_{v}} \)에 \( DP_{w} + 1 \)개의 탄피가 추가되며, 나머지 탄피도 회수 실패 처리하면 됩니다.

두 경우 모두 \( MP_{w, x} \)에서 회수에 실패한 탄피는 \( MP_{v, 2x-H_{v}} \)로 옮겨주면 됩니다.

하지만 이렇게만 하면 TLE가 뜹니다. 그런데 식을 보면 알겠지만, 회수에 실패할 때마다 목표 높이에 2가 곱해지는 걸 볼 수 있습니다. 그러니 \( \log H \)번 정도를 돌리면 최대 높이보다 더 높은 목표 높이를 가지게 됨을 생각해볼 수 있고, 최대 높이보다 더 높은 목표 높이는 당연히 달성 불가능하니 그냥 \( MP \)에서 없애버리면 됩니다.

 

이렇게 DP 계산을 끝낸 뒤 각 정점에서의 DP 값을 출력해주면 됩니다.

ll arr[316420];
vector<int> adj[316420];

int dp[316420]; map<ll, int> mp[316420];
void dfs(int now, int pre){
	dp[now] = 1;
	for (int nxt : adj[now]){
		if (nxt == pre){ continue; }
		dfs(nxt, now);
		if (arr[nxt] <= arr[now]){
			dp[now] += dp[nxt];
			for (pair<ll, int> p : mp[nxt]){
				if (p.fr <= arr[now]){ dp[now] += p.sc; }
				else{
					ll res = p.fr + p.fr-arr[now];
					if (res <= INF){ mp[now][res] += p.sc; }
				}
			}
		}
		else{
			ll res = arr[nxt] + arr[nxt]-arr[now];
			if (res <= INF){ mp[now][res] += dp[nxt]; }
			for (pair<ll, int> p : mp[nxt]){
				ll res = p.fr + p.fr-arr[now];
				if (res <= INF){ mp[now][res] += p.sc; }
			}
		}
	}
	/*cout << "DP " << now << " = " << dp[now] << ": ";
	for (pair<ll, int> p : mp[now]){ cout << "(" << p.fr << ' ' << p.sc << ") "; }
	cout << endl << flush;*/
}

void Main(){
	int n; cin >> n;
	for (int i = 1; i <= n; i++){ cin >> arr[i]; }
	for (int i = 1; i < n; i++){
		int v, w; cin >> v >> w;
		adj[v].push_back(w); adj[w].push_back(v);
	}
	dfs(1, -1);
	for (int i = 1; i <= n; i++){ cout << dp[i] << ' '; }
}

7. [18863] 풀 한 포기 친구 얼굴 (Platinum I)

각 명령은 6가지 변수로 나타낼 수 있습니다.

욱제의 시작 위치를 (0, 0)이라고 할 때,

\( (\Delta y, \Delta x) := \) 명령이 끝난 뒤 욱제의 위치

\( (y_1, y_2) := \) 명령 도중에 이동하는 최대/최소의 y 위치

\( (x_1, x_2) := \) 명령 도중에 이동하는 최대/최소의 x 위치

 

어떤 명령을 \( (y, x) \)에서 실행하려면, 명령 도중에 구역 밖으로 나가면 안 됩니다. 즉, \( 1 \le y - y_1 \le y - y_2 \le N \text{ and } 1 \le x - x_1 \le x - x_2 \le M \)을 만족해야 합니다.

 

이를 토대로 \( (N, M) \)에서 출발해서 '역방향으로' DFS를 돌리면 \( (N, M) \)으로 갈 수 있는 모든 좌표를 찾을 수 있게 됩니다.

\( CHK_{y, x} := \) \( (y, x) \)에서 \( (N, M) \)으로 갈 수 있는가?

 

이제 이를 토대로 DP 계산을 시작해봅시다.

\( DP_{y, x} := \) \( (y, x) \)에서 시작할 때, 가능한 오리걸음의 방법의 수

 

DP 계산은 Top-Down 방식으로 다음과 같이 하면 됩니다.

• \( CHK_{y, x} = \text{False} \): 여기서 \( (N, M) \)으로 갈 수 없으니, 조교는 욱제를 여기로 보낼 수 없습니다. 즉, 0가지 경우가 가능합니다.
• \( (y, x) = (N, M) \): 이제 욱제는 자유입니다! (추가 명령 없음)의 1가지 경우가 가능합니다.
• 현재 지점에서 내릴 수 있는 명령 \( (\Delta y, \Delta x, y_1, y_2, x_1, x_2) \)에 대해...
  도착점을 \( (y', x') \)이라고 한다면:
  • 만약 지금까지 왔던 경로에 \( (y', x') \)이 있고, \( CHK_{y', x'} \)라면: 조교는 이 사이클을 원하는 만큼 돌려버릴 수 있습니다. \( \infty \)가지 경우가 가능합니다.
  • \( DP_{y', x'} = \infty \): 조교는 \( (y', x') \)에서부터 욱제를 신나게 굴릴 수 있습니다. \( \infty \)가지 경우가 가능합니다.
• 만약 위 경우에 해당하는 명령이 없다면, \( DP_{y, x} = \sum DP_{y', x'} \)가 됩니다.

struct Move{ int yd, xd, y1, y2, x1, x2; };
Move mov[12];

int n, m;
bool chk[1020][1020];
void dfs(int y, int x){
	chk[y][x] = 1;
	for (int k = 1; k <= 10; k++){
		int yy = y - mov[k].yd, xx = x - mov[k].xd;
		int yy1 = yy + mov[k].y1, xx1 = xx + mov[k].x1;
		int yy2 = yy + mov[k].y2, xx2 = xx + mov[k].x2;
		if (1 > yy || yy > n){ continue; }
		if (1 > xx || xx > m){ continue; }
		if (1 > yy1 || yy2 > n){ continue; }
		if (1 > xx1 || xx2 > m){ continue; }
		if (chk[yy][xx]){ continue; }
		dfs(yy, xx);
	}
}

bool pth[1020][1020];
const ll mod = 993244853; ll dp[1020][1020];
ll dpf(int y, int x){
	pth[y][x] = 1;
	if (dp[y][x] != -1){ pth[y][x] = 0; return dp[y][x]; }
	if (!chk[y][x]){
		//cout << "DP " << y << ' ' << x << " = " << 0 << endl;
		pth[y][x] = 0; return dp[y][x] = 0;
	}
	if (y==n && x==m){
		//cout << "DP " << y << ' ' << x << " = " << 1 << endl;
		pth[y][x] = 0; return dp[y][x] = 1;
	}
	ll &res = dp[y][x]; res = 0;
	for (int k = 1; k <= 10; k++){
		int yy = y + mov[k].yd, xx = x + mov[k].xd;
		int yy1 = y + mov[k].y1, xx1 = x + mov[k].x1;
		int yy2 = y + mov[k].y2, xx2 = x + mov[k].x2;
		if (1 > yy1 || yy2 > n){ continue; }
		if (1 > xx1 || xx2 > m){ continue; }
		if (pth[yy][xx] && chk[yy][xx]){ pth[y][x] = 0; return res = -2; }
		ll val = dpf(yy, xx);
		if (val == -2){
			//cout << "DP " << y << ' ' << x << " = " << -2 << endl;
			pth[y][x] = 0; return res = -2;
		}
		res += val; res %= mod;
	}
	//cout << "DP " << y << ' ' << x << " = " << res << endl;
	pth[y][x] = 0; return res;
}

void Main(){
	memset(dp, -1, sizeof(dp));
	for (int i = 1; i <= 10; i++){
		string s; cin >> s;
		int y=0, x=0, y1=0, y2=0, x1=0, x2=0;
		for (char ch : s){
			if (ch == 'N'){ y -= 1; } if (ch == 'S'){ y += 1; }
			if (ch == 'W'){ x -= 1; } if (ch == 'E'){ x += 1; }
			y1 = min(y1, y); y2 = max(y2, y);
			x1 = min(x1, x); x2 = max(x2, x);
		}
		mov[i] = { y, x, y1, y2, x1, x2 };
	}
	cin >> n >> m;
	dfs(n, m);
	ll ans = dpf(1, 1);
	if (ans == -2){ cout << -1; } else{ cout << ans; }
}

8. [18864] 모든 것이 새롭다 (Diamond II)

슬라이딩 퍼즐에 있는 구멍을 0 대신 \( abcdef \)로 두고, \( a \rightarrow b \rightarrow c \rightarrow d \rightarrow e \rightarrow f \) 차원의 순서로 왼쪽에서 오른쪽으로 읽을 때의 수열을 \( P \)라고 하면,

(\( P \)의 Inversion Count + 구멍의 위치와 우측 하단의 맨해튼 거리)의 홀짝성은 바뀌지 않습니다.

또한, 맞춰진 상태에서의 홀짝성과 현재 상태의 홀짝성이 같으면 항상 맞힐 수 있는 해법이 존재합니다.

 

이는 15-slide puzzle에서는 Well-known이며, 차원 개수 및 축 개수를 일반화해도 되는지는 Proof by AC를 해주면 됩니다. [TODO, 언젠가는: 증명해보기]

 

예외적으로, 5개 이상의 차원의 길이가 1일 때에는 (사실상 1차원) 구멍을 제외하고 정렬이 되어있는 상태여야 합니다.

int arr[1000020];

const int N = 1048576; int fen[1048580];
void upd(int pos, int val){
	for (int i = pos; i < N; i += i&-i){ fen[i] += val; }
}
int qry(int pos){
	int res = 0;
	for (int i = pos; i > 0; i -= i&-i){ res += fen[i]; }
	return res;
}

void Main(){
	int a, b, c, d, e, f; cin >> a >> b >> c >> d >> e >> f;
	int n = a*b*c*d*e*f; int m = (a!=1) + (b!=1) + (c!=1) + (d!=1) + (e!=1) + (f!=1);
	int pos = 0;
	for (int i = 0; i < n; i++){
		cin >> arr[i];
		if (arr[i] == 0){ arr[i] = n; pos = i; }
	}
	if (m == 1){
		int ptr = 1;
		for (int i = 0; i < n; i++){ if (arr[i] == ptr){ ptr += 1; } }
		cout << (ptr >= n ? "2ez" : "eokkkkkk");
		return;
	}
	int z = pos%f, y = pos/f%e, x = pos/f/e%d, w = pos/f/e/d%c, v = pos/f/e/d/c%b, u = pos/f/e/d/c/b%a;
	bool inv = ( (a+b+c+d+e+f) - (u+v+w+x+y+z) ) & 1;
	for (int i = n-1; i >= 0; i--){
		inv ^= qry(arr[i]) & 1;
		upd(arr[i], 1);
	}
	cout << (inv ? "eokkkkkk" : "2ez");
}

9. [18865] 이제 다시 시작이다 (Platinum I)

우선, 훈련소의 우측 상단 점을 \( (0, 0) \)으로 고정시켜봅시다.

그리고, 각각의 스피커를 (원점과의 거리가 달라지지 않는) \( x \) 축 위의 한 점으로 옮겨봅시다.

* 우측 상단에 있기 때문에 저렇게 옮겨줘도 답이 달라지지 않습니다.

 

저렇게 정의하면, 이제 스피커의 위치를 1차원만으로 표현할 수 있습니다.

\( CNT_{x} := \) \( x \) 위치에 있는 스피커의 개수

 

이제, 현재까지 설치된 스피커에 대해 아래 쿼리를 처리할 수 있으면 됩니다.

\( Q(k) = \sum_{x} \left( \max(k-x, 0) \right)^2 \times C_{x} \)

이 쿼리를 처리할 수 있다면, 훈련소의 높이, 너비가 각각 \( h, w \)일 때

포함-배제 하듯이 \( Q(V) - Q(V-h) - Q(V-w) + Q(V-h-w) \)를 계산해주면 됩니다.

 

결국 남은 건 저 쿼리를 처리하는 건데, 이를 위해 Segment Tree로 총 3가지 값을 처리해줘야 합니다.

"수식으로 설명하기"를 시도했으나 실패했으므로, \( [st, ed] = [1, 8] \) 구간으로 예시를 보여주는 방식으로 대체하겠습니다. [TODO: 설명]

계수	C1	C2	C3	C4	C5	C6	C7	C8
SUM	1	1	1	1	1	1	1	1
TRI	8	7	6	5	4	3	2	1
SQP	36	28	21	15	10	6	3	1

+ \( LEN := \) 구간의 길이

\( st = ed \)라면, \( SUM = TRI = SQP = C_{st} \)가 됩니다.

그렇지 않다면, 두 자식의 SUM, TRI, SQP를 합해야 합니다.

합하는 과정 역시 \( [1, 5] \)와 \( [6, 8] \)을 합치는 예시로 대체하겠습니다. [TODO: 설명]

계수	C1	C2	C3	C4	C5	C6	C7	C8
sum1	1	1	1	1	1
sum2						1	1	1
sum	1	1	1	1	1	1	1	1

계수	C1	C2	C3	C4	C5	C6	C7	C8
tri1	5	4	3	2	1
tri2						3	2	1
3×sum1	3	3	3	3	3
tri	8	7	6	5	4	3	2	1

계수	C1	C2	C3	C4	C5	C6	C7	C8
sqp1	15	10	6	3	1
sqp2						6	3	1
3×tri1	15	12	9	6	3
6×sum1	6	6	6	6	6
sqp	36	28	21	15	10	6	3	1

\( SUM = SUM_1 + SUM_2 \)
\( TRI = TRI_1 + TRI_2 + LEN_2 \cdot SUM_1 \)
\( SQP = SQP_1 + SQP_2 + LEN_2 \cdot TRI_1 + \frac{LEN_2 \cdot (LEN_2+1)}{2} \cdot SUM_1 \)

최종 결과는 아래와 같이 구할 수 있습니다.

계수	C1	C2	C3	C4	C5	C6	C7	C8
2×sqp	72	56	42	30	20	12	6	2
-1×tri	-8	-7	-6	-5	-4	-3	-2	-1
res	64	49	36	25	16	9	4	1

\( RES = 2 \cdot SQP - TRI \)

struct Node{ ll sum, tri, sqp; int st, ed; };
const int N = 524288; Node seg[1048580];

inline Node add(const Node& a, const Node& b){
	//cout << "ADD " << a.st << ' ' << a.ed << ' ' << b.st << ' ' << b.ed << endl << flush;
	if (a.st > b.st){ return add(b, a); }
	assert(a.ed+1 == b.st);
	int al = a.ed-a.st+1, bl = b.ed-b.st+1;
	Node res = {0, 0, 0, a.st, b.ed};
	res.sum = a.sum + b.sum;
	res.tri = a.tri + b.tri + bl*a.sum;
	res.sqp = a.sqp + b.sqp + bl*a.tri + bl*(bl+1LL)/2*a.sum;
	return res;
}

void upd(int pos, int val){ pos += N;
	seg[pos].sum += 1; seg[pos].tri += 1; seg[pos].sqp += 1;
	pos >>= 1;
	while (pos){
		int p1 = pos<<1, p2 = pos<<1|1;
		seg[pos] = add(seg[p1], seg[p2]); pos >>= 1;
	}
}
Node qry(int st, int ed){ st += N; ed += N;
	Node res = {0, 0, 0, -1, -1};
	while (st <= ed){
		if (st & 1){
			if (res.st == -1){ res = seg[st]; }
			else{ res = add(res, seg[st]); }
			st += 1;
		}
		if (~ed & 1){
			if (res.st == -1){ res = seg[ed]; }
			else{ res = add(res, seg[ed]); }
			ed -= 1;
		}
		if (st > ed){ break; }
		st >>= 1; ed >>= 1;
	}
	return res;
}
inline ll f(int x){
	if (x < 0){ return 0; }
	Node res = qry(0, x-1);
	return 2*res.sqp - res.tri;
}

void Main(){
	for (int i = N+N-1; i >= 1; i--){
		if (i >= N){ seg[i].st = seg[i].ed = i-N; }
		else{ seg[i].st = seg[i<<1].st; seg[i].ed = seg[i<<1|1].ed; }
	}
	int sy, sx, ey, ex; cin >> sy >> sx >> ey >> ex;
	int h = ey-sy, w = ex-sx;
	int q; cin >> q;
	while (q--){
		int m; cin >> m;
		if (m == 1){
			int y, x; cin >> y >> x; y -= ey; x -= ex;
			x += y; upd(x, 1);
		}
		if (m == 2){
			int x; cin >> x;
			cout << f(x) - f(x-h) - f(x-w) + f(x-h-w) << endl;
		}
	}
}

10. [18866] 젊은 날의 생이여 (Gold V)

욱제의 젊은 날 \( K \)를 골라봅시다.

\( K \)의 정의 상, 아래 두 조건을 만족해야 합니다.

• \( \min_{i \le K} U_{i} \ge \max_{i \gt K} U_{i} \)
• \( \max_{i \le K} V_{i} \le \min_{i \gt K} V_{i} \)

Prefix min/max, Suffix min/max로 잘 구해줄 수 있는 식이 나왔으니 "누락된 값은 무시하면서" 그대로 Prefix/Suffix min/max를 박아주고, 위 조건을 만족하는 \( K \) 중 가장 큰 값을 찾아주면 됩니다.

pl2 arr[1000020];
const ll INF = 1e15; pl2 prf[1000020], suf[1000020];

void Main(){
	int n; cin >> n;
	for (int i = 1; i <= n; i++){ cin >> arr[i].fr >> arr[i].sc; }
	prf[0] = {INF, -INF};
	for (int i = 1; i <= n; i++){
		prf[i] = prf[i-1];
		if (arr[i].fr != 0){ prf[i].fr = min(prf[i-1].fr, arr[i].fr); }
		if (arr[i].sc != 0){ prf[i].sc = max(prf[i-1].sc, arr[i].sc); }
		//cout << "PRF " << i << " = " << prf[i].fr << ' ' << prf[i].sc << endl;
	}
	suf[n+1] = {-INF, INF};
	for (int i = n; i >= 1; i--){
		suf[i] = suf[i+1];
		if (arr[i].fr != 0){ suf[i].fr = max(suf[i+1].fr, arr[i].fr); }
		if (arr[i].sc != 0){ suf[i].sc = min(suf[i+1].sc, arr[i].sc); }
		//cout << "SUF " << i << " = " << suf[i].fr << ' ' << suf[i].sc << endl;
	}
	for (int k = n-1; k >= 1; k--){
		if (prf[k].fr > suf[k+1].fr && prf[k].sc < suf[k+1].sc){ cout << k; return; }
	}
	cout << -1;
}

11. [18867] 편지 꼭 해다오 (Silver II)

랜덤 Generator를 만들어봅시다.

Generator가 하는 일은 "답안에 1글자를 추가한 뒤, 그 글자의 814제곱을 더해주고, 결과값이 20200402가 되면 답안 출력 후 종료"면 됩니다.

답안에 글자를 추가하는 방식은 본인이 원하는 방식으로 해주면 되며, 보통 '랜덤하게 넣는다'와 'BFS를 쓴다'가 있습니다.

 

요약하면, 컴퓨터에게 계산을 맡기면 되며, 제가 제출한 편지?는 다음과 같습니다.

(길이가 너무 길어서 링크로 대체합니다.)
13720 Bytes: https://www.acmicpc.net/source/share/af57adb11e25449592be9f3903947f91

272170 Bytes: https://www.acmicpc.net/source/share/0c8c3b66efdd4ed291fb45bc1cc8f554

 

+ 272170 Bytes 길이의 편지는 밑의 코드 테스트 겸 제출했으며, (2022.05.05 01:23 UTC+9 기준) 맞았습니다!! 를 받은 편지 중 가장 긴 편지입니다. 다들 짧은 편지만 작성하시다니 정성이 없으시네요

 

아래 코드는 Python으로 만든 Random Generator며, 답이 나올 확률은 계산해본 적 없습니다.

import sys
from random import randint

def randchar():
    val = randint(0, 61)
    if val < 10: return chr(val+48) # 0~9
    if val < 36: return chr(val+65-10) # A~Z
    return chr(val+97-36) # a~z

outputFile = open("output.txt", 'w')
t = 0
while True:
    ans, y = "", 0
    for l in range(990316):
        ch = randchar(); ans += ch
        x = ord(ch)
        p = pow(x, 814, 20200429)
        y += p; y %= 20200429
        # print(ch, x, y, p)
        if y == 20200402:
            print(ans, file=outputFile)
            print(f"Try {t+1}: Answer Found: Length {l+1}")
            sys.exit(0)
    print(f"Try {t+1}: Answer Not Found")
    t += 1