AtCoder Beginner Contest 179

오랜만에 글을 쓰는거 같다.

깔쌈했다.

 

풀이가 성의 없어 보여도 이해해 주길 바란다...

그냥 간단하게 끄적이는 거라 풀이가 많이 부실 할 수 있다.

 

A - Plural Form

 

맨 뒷 글자가 's'면 'es'를 붙이고, 아니면 's'를 붙인다.

 

#include <bits/stdc++.h>
#define x first
#define y second
#pragma gcc optimize("O3")
#pragma gcc optimize("Ofast")
#pragma gcc optimize("unroll-loops")
using namespace std;
const long long INF = 1e18;
const int mod = 100003;
typedef long long ll;
typedef long double ld;
typedef pair <int,int> pi;
typedef pair <ll,ll> pl;
typedef vector <int> vec;
char a[10005];
 
int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	cin >> a+1;
	int n = strlen(a+1);
	if(a[n] != 's') cout << a+1 << 's';
	else cout << a+1 << "es";
}

 

B - Go to Jail

 

연속 3개가 모두 $D[0] = D[1]$인지 확인해 주면 된다.

 

#include <bits/stdc++.h>
#define x first
#define y second
#pragma gcc optimize("O3")
#pragma gcc optimize("Ofast")
#pragma gcc optimize("unroll-loops")
using namespace std;
const long long INF = 1e18;
const int mod = 100003;
typedef long long ll;
typedef long double ld;
typedef pair <int,int> pi;
typedef pair <ll,ll> pl;
typedef vector <int> vec;
int a[105][2],n;
 
int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	cin >> n;
	for(int i = 1;i <= n;i++) cin >> a[i][0] >> a[i][1];
	for(int i = 1;i <= n-2;i++) {
		if(a[i][0] == a[i][1]&&a[i+1][0] == a[i+1][1]&&a[i+2][0] == a[i+2][1]) {
			cout << "Yes";
			return 0;
		}
	}
	cout << "No";
	return 0;
}

 

C - A x B + C

 

$A$에 대해 가능한 경우의 수가 $N$가지 있다 ($1~N$)

각 $A$에 대해 $B$가 가능한 경우는 $N/A$ 가지가 있고 $A, B$ 가 정해지면 $C$는 자동으로 정해진다. $C$는 자연수 이기 때문에 $A$ 가 $N$의 약수인 경우에는 1을 빼줘야 한다.

 

#include <bits/stdc++.h>
#define x first
#define y second
#pragma gcc optimize("O3")
#pragma gcc optimize("Ofast")
#pragma gcc optimize("unroll-loops")
using namespace std;
const long long INF = 1e18;
const int mod = 100003;
typedef long long ll;
typedef long double ld;
typedef pair <int,int> pi;
typedef pair <ll,ll> pl;
typedef vector <int> vec;
int n;
 
int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	cin >> n;
	ll ans = 0;
	for(int i = 1;i <= n;i++) {
		ans += n/i;
		if(i*(n/i) == n) ans--;
	}
	cout << ans;
	return 0;
}

 

D - Leaping Tak

각 구간의 합집합을 구한다음 합집합을 다시 구간으로 나눈다.

예시로
1~3

1~5

4~7

9~10

가 있다고 하자.

$S = ${$1,2,3,4,5,6,7,9,10$} 이고 이걸 다시 구간으로 나타내면 1~7, 9~10 임을 알 수 있다.

다시 작업한 구간은 최대 10개로 나눠지므로 각 구간마다 누적합으로 각 위치에 올 수 있는 경우의 수를 동적 계획법으로 구해줄 수 있다.

 

#include <bits/stdc++.h>
#define x first
#define y second
#pragma gcc optimize("O3")
#pragma gcc optimize("Ofast")
#pragma gcc optimize("unroll-loops")
using namespace std;
const long long INF = 1e18;
const long long mod = 998244353;
typedef long long ll;
typedef long double ld;
typedef pair <int,int> pi;
typedef pair <ll,ll> pl;
typedef vector <int> vec;
int n,k;
pi a[25];
ll d[200005],sd[200005];
vector <pi> gu;
 
int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	cin >> n >> k;
	for(int i = 1;i <= k;i++) cin >> a[i].x >> a[i].y;
	sort(a+1,a+k+1);
	int l = a[1].x, r = a[1].y;
	for(int i = 2;i <= k;i++) {
		if(r+1 < a[i].x) {
			gu.push_back({l,r});
			r = 0, l = a[i].x;
		}
		r = max(r,a[i].y);
	}
	gu.push_back({l,r});
	d[1] = 1;
	sd[1] = 1;
	for(int i = 2;i <= n;i++) {
		for(pi j : gu) {
			int l = max(0,i-j.y), r = max(0,i-j.x);
			d[i] = (d[i]+sd[r]-sd[l-1]+mod)%mod;
		}
		sd[i] = sd[i-1]+d[i];
	}
	cout << d[n];
 	return 0;
}

 

E - Sequence Sum

 

어떤 값 A가 있다고 하자. A가 처음 등장하는 위치와 다시 등장하는 위치를 각각 $st, en$ 이라고 하면, $st$까지는 반복이 없다가 그 뒤로 $st+1~en$값이 반복될 것이다.

이 부분을 잘 처리해주면 만점을 받는다.

 

#include <bits/stdc++.h>
#define x first
#define y second
#pragma gcc optimize("O3")
#pragma gcc optimize("Ofast")
#pragma gcc optimize("unroll-loops")
using namespace std;
const long long INF = 1e18;
const long long mod = 998244353;
typedef long long ll;
typedef long double ld;
typedef pair <int,int> pi;
typedef pair <ll,ll> pl;
typedef vector <int> vec;
ll n,X,m,sum,ans;
ll d[300005],sd[300005];
int c[200005],st,i,en;
 
int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	cin >> n >> X >> m;
	d[1] = sd[1] = ans = X;
	c[X] = 1;
	st = en = n+1;
	for(i = 2;i <= min(n,m+5);i++) {
		d[i] = d[i-1]*d[i-1]%m;
		sd[i] = sd[i-1]+d[i];
		ans += d[i];
		if(c[d[i]]) {
			st = i;
			break;
		}
		c[d[i]] = 1;
	}
	for(i = st+1;i <= min(n,m*2+10);i++) {
		d[i] = d[i-1]*d[i-1]%m;
		sum += d[i];
		sd[i] = sd[i-1]+d[i];
		if(d[i] == d[st]) {
			en = i;
			break;
		}
	}
	if(st == n+1) cout << ans;
	else {
		if(en == n+1) cout << ans+sum;
		else {
			cout << ans+sum*((n-st)/(en-st))+(sd[st+(n-st)%(en-st)]-sd[st]);
		}
	}
 	return 0;
}

 

F - Simplified Reversi

 

저자는 segment tree with lazy를 썻지만 다른 사람들은 잘 모르겠다

우리가 쓰려는 함수는 총 4개다.

 

$updateX(l,r,val)$ : x축 좌표 l~r에 min(val)을 취한다.

$updateY(l,r,val)$ : y축 좌표 l~r에 min(val)을 취한다.

$queryX(wi)$ : x축 좌표 wi값을 리턴한다.

$queryY(wi)$ : y축 좌표 wi값을 리턴한다.

 

잘 설명은 못하지만 일단 해보겠다.

만약 (1,wi) 부터 x축으로 뻗는다고 하면 도달하는 곳은 y축에서 좌표가 wi인 곳 중에서 가장 작은 x좌표이다.

y축도 똑같다.

이걸 잘 구현하면 된다. (?)

 

그냥 가벼운 마음으로 듣길 바란다...

풀이를 원한다면 코드를 보고 해석하는게 더 나을 수도 있다. (하지만 코드도 더럽ㄷ..읍읍)

 

#include <bits/stdc++.h>
#define x first
#define y second
#pragma gcc optimize("O3")
#pragma gcc optimize("Ofast")
#pragma gcc optimize("unroll-loops")
using namespace std;
const int INF = 1e9;
const long long mod = 998244353;
typedef long long ll;
typedef long double ld;
typedef pair <int,int> pi;
typedef pair <ll,ll> pl;
typedef vector <int> vec;
int tx[800005],ty[800005],lx[800005],ly[800005];
int n,Q;

void pushX(int x,int l,int r) {
	tx[x] = min(tx[x],lx[x]);
	if(l ^ r) {
		lx[x*2] = min(lx[x*2],lx[x]);
		lx[x*2+1] = min(lx[x*2+1],lx[x]);
	}
	lx[x] = INF;
}

void pushY(int x,int l,int r) {
	ty[x] = min(ty[x],ly[x]);
	if(l ^ r) {
		ly[x*2] = min(ly[x*2],ly[x]);
		ly[x*2+1] = min(ly[x*2+1],ly[x]);
	}
	ly[x] = INF;
}

void updateX(int x,int l,int r,int rl,int rr,int val) {
	if(rl > rr) return;
	pushX(x,l,r);
	if(rl > r||l > rr) return;
	if(rl <= l&&r <= rr) {
		lx[x] = min(lx[x],val); pushX(x,l,r);
		return;
	}
	int mid = (l + r) >> 1;
	updateX(x*2,l,mid,rl,rr,val), updateX(x*2+1,mid+1,r,rl,rr,val);
	tx[x] = min(tx[x*2],tx[x*2+1]);
}

void updateY(int x,int l,int r,int rl,int rr,int val) {
	if(rl > rr) return;
	pushY(x,l,r);
	if(rl > r||l > rr) return;
	if(rl <= l&&r <= rr) {
		ly[x] = val; pushY(x,l,r);
		return;
	}
	int mid = (l + r) >> 1;
	updateY(x*2,l,mid,rl,rr,val), updateY(x*2+1,mid+1,r,rl,rr,val);
	ty[x] = min(ty[x*2],ty[x*2+1]);
}

void build(int x,int l,int r) {
	tx[x] = ty[x] = lx[x] = ly[x] = n;
	if(l == r) return;
	int mid = (l + r) >> 1;
	build(x*2,l,mid), build(x*2+1,mid+1,r);
}

int queryX(int x,int l,int r,int wi) {
	pushX(x,l,r);
	if(wi < l||r < wi) return n;
	if(l == r) return tx[x];
	int mid = (l + r) >> 1;
	return min(queryX(x*2,l,mid,wi),queryX(x*2+1,mid+1,r,wi));
}

int queryY(int x,int l,int r,int wi) {
	pushY(x,l,r);
	if(wi < l||r < wi) return n;
	if(l == r) return ty[x];
	int mid = (l + r) >> 1;
	return min(queryY(x*2,l,mid,wi),queryY(x*2+1,mid+1,r,wi));
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	cin >> n >> Q;
	ll ans = 1LL*(n-2)*(n-2);
	build(1,1,n);
	for(int i = 1;i <= Q;i++) {
		int op,x; cin >> op >> x;
		if(op & 1) {
			int tmp = queryY(1,1,n,x);
			ans -= max(0,tmp-2);
			updateX(1,1,n,1,tmp-1,x);
		}
		else {
			int tmp = queryX(1,1,n,x);
			ans -= max(0,tmp-2);
			updateY(1,1,n,1,tmp-1,x);
		}
	}
	cout << ans;
 	return 0;
}