[AtCoder] AtCoder Beginner Contest 312

https://atcoder.jp/contests/abc312/tasks

Tasks - UNIQUE VISION Programming Contest 2023 Summer(AtCoder Beginner Contest 312)

F번이 아쉬워서 글 남겨본다. 한 5판 정도만 더 하면 민트는 갈 거 같은데, 앳코더는 이번 년도 블루를 목표로 해야겠다.

 

A. 

걍 if문 쓰면 된다.

 

B.

격자판 위에서 브루트포스. 구현을 좀 더럽게 했는데, 더 좋은 방법이 떠오르지 않는다.

 

C.

조금 생각해 보면 답의 단조성이 성립하므로, $X$를 이분 탐색 돌리면 된다.

시간복잡도는 $O(nlogn)$

 

D.

(를 +1, )를 -1로 생각해 보자.

$n <= 3000$이라서 $n^2$ DP를 돌리고 싶어 진다.

dp[i][j] := i번째까지 봤을 때의 문자열의 합이 j-3000인 경우의 수라고 정의하면 된다.

올바른 괄호 문자열이어야 하므로, 문자열을 만드는 과정에서도 해당 dp값이 음수가 되면 안 된다.

위 조건을 지키면서 dp 상태를 전이한 이후에 답은 dp[n-1][3000]이다.

 

E.

안 읽고, 안 풀었어요

 

F.

순서를 잘 고르면 그리디 하게 답을 찾을 수 있을 것 같았다.

한 두 번의 시행착오를 겪고 고르는 순서를 0, 1, 2 순서대로 고르면 될 것 같았다.

우선 모두 X값이 큰 것부터 선택하는 게 이득이므로, 모두 내림차순 정렬을 해준다.

추후의 계산을 위해서 각각의 T에 대해서 누적합을 구해놓는다.

T=0인 것의 개수를 i로 정해두고, T=1, 2일 때를 최대한으로 선택한다. 이는 이분탐색으로 찾을 수 있다.

아래는 AC 코드이다.

범위를 제대로 체크 안 해서 계속 틀렸었는데, 처음부터 모든 범위를 생각하면서 구현하는 습관을 들여야겠다.

ll n, m, ans;
vector<ll> a[3];
ll p[3][200005];

void solve()
{
	cin >> n >> m;
	for (int i = 0; i < n; i++)
	{
		ll t, x; cin >> t >> x;
		a[t].push_back(x);
	}
	for (int i = 0; i < 3; i++) sort(all(a[i]), greater<ll>());
	for (int i = 0; i < 3; i++)
	{
		if(a[i].size()) p[i][0] = a[i][0];
		for (int j = 1; j < a[i].size(); j++)
			p[i][j] = p[i][j - 1] + a[i][j];
	}
	// 0 -> 1 -> 2
	for (int i = 0; i <= m && i <= a[0].size(); i++)
	{
		ll res = 0;
		if (i - 1 >= 0) res += p[0][i - 1];
		ans = max(ans, res); // 1 and 2 -> 0
		ll lo = 1, hi = min(m - i, (ll)a[1].size());
		while (lo <= hi) // 1 and 2 -> [1, min(m - i, (ll)a[1].size())]
		{
			ll mid = (lo + hi) / 2;
			if (mid > p[2][a[2].size() - 1])
			{
				hi = mid - 1;
				continue;
			}
			ll idx = lower_bound(p[2], p[2] + a[2].size(), mid) - p[2] + 1;
			if (i + mid + idx <= m)
			{
				ans = max(ans, res + p[1][mid - 1]);
				lo = mid + 1;
			}
			else hi = mid - 1;
		}
	}
	cout << ans;
}