#557 Virtual contest

 

무친 점수가 나와버렸다.

이 글을 쓰는 이유는 E번 게임이론 문제가 재밌어서 쓴다.

codeforces.com/contest/1162

A번
처음에 h로 초기화 해 놓은 후, 쿼리마다 업데이트 해주면 된다.
왜 그런지는 조금만 생각해보면 된다.

#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#include<queue>
#include<string>
#include<cstring>
#include<stack>
#include<map>
#include<set>

#define all(v) v.begin(),v.end()
using namespace std;
using ll = long long;
const ll n_ = 2050, inf = 1e18, mod = 1e9 + 7;

ll n, m, a, b, c, d, x, y, t, k, u, v, h;

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	//cin >> t;
	t = 1;
	while (t--) {
		cin >> n >> h >> m;
		vector<ll>v(n + 1, h);
		a = 0;
		while (m--) {
			cin >> a >> b >> c;
			for (int i = a; i <= b; i++)v[i] = min(v[i],c);
		}
		a = 0;
		for (int i = 1; i <= n; i++)a += v[i] * v[i];
		cout << a << '\n';
	}
}

 

B번

같은 위치의 것들을 비교로 해서 더 작은 배열, 더 큰 배열 두개로 나누어서 비교해보면 된다.
왜 그런지는 조금만 생각해보면 된다.

#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#include<queue>
#include<string>
#include<cstring>
#include<stack>
#include<map>
#include<set>

#define all(v) v.begin(),v.end()
using namespace std;
using ll = long long;
const ll n_ = 2050, inf = 1e18, mod = 1e9 + 7;

ll n, m, a, b, c, d, x, y, t, k, u, v, h;
ll A[n_][n_], B[n_][n_];
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	//cin >> t;
	t = 1;
	while (t--) {
		cin >> n >> m;
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= m; j++)cin >> A[i][j];
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= m; j++)cin >> B[i][j];

		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= m; j++) {
				if (A[i][j] > B[i][j])swap(A[i][j], B[i][j]);
			}
		bool ok = true;

		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= m; j++) {
				if (A[i][j] <= A[i][j - 1] || A[i][j] <= A[i - 1][j])ok = false; 
				if (B[i][j] <=B[i][j - 1] || B[i][j] <= B[i - 1][j])ok = false;
			}
		}
		if (ok)cout << "Possible";
		else cout << "Impossible";
	}
}

 

 

C번 

원소별로 처음 등장위치와 마지막 등장위치를 저장해 잘 따져보면 된다.
왜 그런지는 역시나 조금만 생각해보면 된다.

#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#include<queue>
#include<string>
#include<cstring>
#include<stack>
#include<map>
#include<set>

#define all(v) v.begin(),v.end()
using namespace std;
using ll = long long;
const ll n_ = 100500, inf = 1e18, mod = 1e9 + 7;

ll n, m, a, b, c, d, x, y, t, k, u, v, h;
ll A[n_][2];
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	//cin >> t;
	t = 1;
	while (t--) {
		cin >> n >> m;
		for (int i = 0; i < n_; i++) {
			A[i][0] = inf;
			A[i][1] = -inf;
		}
		vector<ll>v;
		for (int i = 0; i < m; i++) {
			cin >> a;
			v.push_back(a);
		}
		for (ll i = 0; i < v.size(); i++) {
			A[v[i]][0] = min(A[v[i]][0], i);
			A[v[i]][1] = i;
		}
		a = 0;
		A[0][1] = inf, A[n + 1][1] = inf;
		for (int i = 1; i <= n; i++) {
			if (A[i][0] > A[i - 1][1])a++;
			if (A[i][0] > A[i][1])a++;
			if (A[i][0] > A[i + 1][1])a++;
		}

		cout << a << '\n';
	}
}

E 

자!! 드디어 E번이다

이름부터 타노스 님게임이다. 하하 배워왔던 스프라그 그런디로 날먹할 수 있지 않을까? 라는 기쁜 마음가짐으로 D를 
제끼고 E번으로 갔다. 사실 D는 문제가 좀 역겹다. 

각설하고 문제를 대충 설명해 보자면, n개의 수로 된 수열이 있고, 각 플레이어는 자신의 턴마다 n/2개의 수를 골라 (n은 짝수다.) 원하는 만큼 감소시킬 수 있다. 단 0이 되면 그 수는 사라진다.
이때 n/2개를 고를 수 없게 된 플레이어가 패배한다.

 

생각을 조금만 해보면 풀 수 있는 문제다. 문제가 재밌다.

어떤 플레이어가 처음으로 0을 만들었다고 가정하자.

그렇다면 그 다음 플레이어는 n/2개를 없애버리면, 남은 돌의 개수는 최대 n/2-1개다.

따라서 먼저 0으로 만든 플레이어가 패배한다.

 

그렇다면 0으로 만든 플레이어가 패배하게 되는데, 이런 전략을 생각해볼 수 있다. 1이 n/2개 초과로 있으면, Alice는 처음에 무조건 1을 하나 골라야 해서 0이 나와서 질 수 밖에 없다. 근데 반대로, 1이 존재하는데 n/2개 이하로 있다면, n/2개 골라서 1로 만들어버리면, Bob은 무조건 0을 만들어야 해서 Alice가 이긴다.

만약 1이 없다면?

 

문제는 그럼 이렇게 바뀐다. 

먼저 0을 고르면 패배한다 → 먼저 1을 골라버리면 패배한다.

그러면 모든 수열에서 1을 빼주고 똑같은 원리를 적용하면

결국 등장하는 수들의 최솟값이 중요함을 알 수 있다.

등장하는 수들의 최솟값의 갯수가 n/2초과냐, 이하냐에 따라

Alice,Bob의 승리조건이 달라진다.

 

#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#include<queue>
#include<string>
#include<cstring>
#include<stack>
#include<map>
#include<set>

#define all(v) v.begin(),v.end()
using namespace std;
using ll = long long;
const ll n_ = 100500, inf = 1e18, mod = 1e9 + 7;

ll n, m, a, b, c, d, x, y, t, k, u, v, h;
ll A[n_][2];

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	//cin >> t;
	t = 1;
	while (t--) {
		cin >> n;
		vector<ll>v;
		bool ok = false;
		d = inf;
		b = 0;
		for (int i = 0; i < n; i++) {
			cin >> a;
			d = min(d, a);
			v.push_back(a);
		}
		for (int i = 0; i < n; i++) {
			a = v[i];
			if (a == d)b++;
		}
		if (b<=n/2)ok=true;
		if (ok)cout << "Alice";
		else cout << "Bob";
	}
}