오늘의 문제 2020.5.19

이 그룹 에서 매일 문제를 푼다.

 

2020.5.19

 

| 오늘의 문제 |

A - 할로윈의 사탕

10178번: 할로윈의 사탕

기본문제이니 알아서 푸세욤

 

B - if

15549번: if

$int$ 형을 보면 -2147483648~2147483647 이다.

이때 생각난 것이 -2147483648을 넣으면 -x는 어떻게 될까?

이때 x는 2147483648이 되는데 오버플로우로 인해 -2147483648로 변하게 된다.

그러면 $int$형 -2147483648은 우리가 찾고자 하는 정답이다.

 

C - 소수 구하기

1929번: 소수 구하기

에라토스테네스의 체를 이용하여 100만까지의 모든 소수를 구한다음 범위안에 있는 소수를 출력해주면 된다.

 

#include<stdio.h> //에라토스테네스의 체
int i,j,m,n,a[1000001] = {0,1};

int main(){
	scanf("%d %d", &m, &n);
	for(i = 2;i <= n;i++){
		for(j=2;i*j <= n;j++)
			a[i*j] = 1;
	}
	for(i = m;i <= n;i++){
		if(!a[i]) printf("%d\n",i);
	} 
	return 0;
}

 

D - 뒤집기

15999번: 뒤집기

왜그렇게 많이 안푼건지는 잘 모르겠다.

 

만약 어떤 타일 $x$를 바꾸려고 할때 그 타일과 인접한 타일 중 $x$의 타일과 다른 색의 타일이 있으면 이 타일 $x$는 무조건 그 입력받은 색이여야 한다.

 

그렇지 않으면 (인접한 타일들의 색깔이 모두 같은 색이면) 이 색은 검은색이든 하얀색이든 상관이 없다.

 

이 두가지를 가지고 생각을 해보면 인접한 타일들의 색깔이 모두 같은 타일의 개수를 $cnt$라 두면 우리가 구해야 할 답은 $2^{cnt}$이다. (각각의 타일마다 검은색, 흰색이 있다.)

 

#include <bits/stdc++.h>
#pragma gcc optimize("O3")
#pragma gcc optimize("Ofast")
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair <int,int> pi;
typedef pair <ll,ll> pl;
int n,m,nx[4] = {1,0,-1,0},ny[4] = {0,1,0,-1};
char a[2005][2005];
ll g,mod = 1e9+7;

ll mpow(ll go) {
	if(!go) return 1LL;
	ll tmp = mpow(go/2);
	if(go % 2) return tmp*tmp*2LL%mod;
	return tmp*tmp%mod;
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	cin >> n >> m;
	for(int i = 1;i <= n;i++) cin >> a[i]+1;
	int dx,dy;
	for(int i = 1;i <= n;i++) {
		for(int j = 1;j <= m;j++) {
			g++;
			for(int k = 0;k < 4;k++) {
				dx = i+nx[k], dy = j+ny[k];
				if(dx < 1||dx > n||dy < 1||dy > m) continue;
				if(a[i][j] != a[dx][dy]) {
					g--;
					break;
				}
			}
		}
	}
	cout << mpow(g);
}

 

E - 팰린드롬?

10942번: 팰린드롬?

누가봐도 동적 계획법 같이 생겼다.

매 질문마다 팰린드롬인지 검사하면 $O(NM)$이라는 시간 복잡도가 나와 시간 초과를 받게된다.

 

그래서 이걸 동적계획법으로 풀 수 있다.

$d[i][j]$ : $i$~$j$까지의 문자열이 팰린드롬인가?

이걸 구하면 된다.

만약 $i+1$~$j-1$ 이 팰린드롬이고 $str[i] = str[j]$ 라면 $i$~$j$도 팰린드롬이다.

이걸 식으로 나타내면 $d[i][j] = d[i-1][j+1]$&$(str[i]==str[j])$ 로 나타낼 수 있다.

이걸 잘 구해주면 $O(N^{2}+M)$ 에 풀 수 있다.

 

#include <bits/stdc++.h>
using namespace std;
int a[2005];
int n,d[2005][2005];

void f(int l,int r) // l~r 이 팰린드롬 이다
{
    if(l < 1||r > n) return;
    if(a[l-1] == a[r+1]) {
        d[l-1][r+1] = 1;
        f(l-1,r+1);
    }
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);
    cin >> n;
    for(int i = 1;i <= n;i++) {
        cin >> a[i];
    }
    for(int i = 1;i <= n;i++) {
        d[i][i] = 1;
        f(i,i);
        if(i < n&&a[i] == a[i+1]) {
            d[i][i+1] = 1;
            f(i,i+1);
        }
    }
    int q,l,r;
    cin >> q;
    while(q--) {
        cin >> l >> r;
        cout << d[l][r] << '\n';
    }
    return 0;
}

 

F - 천상용섬

12758번: 천상용섬

풀이는 이 글에 있으니 보자!

 

G - JuQueen

10277번: JuQueen

딱 봐도 lazy느낌이 난다. 하지만 시간이 없어서(?) 못풀었다.

 

H - Dynamic Centroid

17101번: Dynamic Centroid

일단 $centroid$가 정해지면 각 노드가 추가될때 마다 $centroid$는 최대 한번만 이동한다는 것을 알 수 있다.

그래서 각 노드가 추가될 때 마다 $centroid$의 인접한 정점들의 서브 트리의 크기를 보고 $size/2$를 넘는지를 비교 해보면 된다.

 

하지만 이렇게 하면 자식이 너무 많을때는 시간 초과를 받게 된다.

어떤 정점 $v$가 추가 됬다고 하면 $v \rightarrow centroid$ 로 가는 경로 중에서 $centroid$의 인접한 정점만 확인해 보면 됨을 알 수 있다.

그 인접한 정점을 제외하고는 서브 트리의 크기가 변하지 않기 때문이다.

 

그러면 이제 우리가 해결해야 할 것은 서브 트리의 크기를 빨리 구하는 것이다.

 

이건 $dfs$ $ordering$을 하면 되지만, 나는 너무 바보같이 $hld$를 짰다.

근데 딱히 $hld$라고 하기도 뭐하다. $hld$만 사용 가능한 그런 테크닉 들을 쓰지 않았다.

그냥 $hld$를 위장한 $dfs$ $ordering$ 이다.

 

쨋든 $dfs$ $ordering$을 하면 트리가 일자로 펴지는데 각 정점마다 시작하는 $dfs$번호와 끝나는 $dfs$번호를 저장해 둔다. 그리고 나중에 서브 트리의 크기를 구할 때에는 그 시작 번호와 끝 번호 사이의 구간중 추가된 노드들의 개수를 세주면 된다. 이것은 세그먼트 트리로 쉽게 풀리고 (lazy를 안써도 된다.) 각 정점이 추가되는 것은 시작 번호에 1을 업데이트 해줌으로써 가능하다.

 

#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair <ll,ll> pl;
typedef pair <int,int> pi;
int n,p[500005],sz[500005],up[500005],re[500005];
int in[500005],out[500005],t[2000005],cen = 1;
int lazy[2000005],dep[500005],go;
vector <int> v[500005];

int query(int x,int l,int r,int rl,int rr) {
	if(l > rr||rl > r) return 0;
	if(rl <= l&&r <= rr) return t[x];
	int mid = (l + r) >> 1;
	return query(x*2,l,mid,rl,rr)+query(x*2+1,mid+1,r,rl,rr);
}

void update(int x,int l,int r,int wh) {
	if(l > wh||wh > r) return;
	if(l == r) {
		t[x]++;
		return;
	}
	int mid = (l + r) >> 1;
	update(x*2,l,mid,wh), update(x*2+1,mid+1,r,wh);
	t[x] = t[x*2]+t[x*2+1];
}

int dfs1(int x,int d) {
	dep[x] = d*(sz[x]=1);
	for(int i : v[x]) sz[x] += dfs1(i,d+1);
	return sz[x];
}

bool cmp(int x,int y) {
	return sz[x] > sz[y];
}

void dfs2(int x,int la) {
	in[x] = ++go;
	up[x] = la;
	re[go] = x;
	sort(v[x].begin(),v[x].end(),cmp);
	for(int i = 0;i < v[x].size();i++) {
		if(!i) dfs2(v[x][i],la);
		else dfs2(v[x][i],v[x][i]);
	}
	out[x] = go;
}

int get_sz(int x) {
	return query(1,1,n,in[re[x]],out[re[x]]);
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	cin >> n;
	p[1] = 1;
	for(int i = 2;i <= n;i++) {
		cin >> p[i];
		v[p[i]].push_back(i);
	}
	dfs1(1,1); dfs2(1,1);
	update(1,1,n,in[1]);
	cout << "1 ";
	cen = 1;
	int mx = 0,ms = 0,ss;
	for(int i = 2;i <= n;i++) {
		int x = i;
		update(1,1,n,in[x]);
		while(x != 1) {
			ss = get_sz(in[cen]+1);
			if(up[cen] == up[x]&&in[x] > in[cen]&&ss > ms) {
				ms = ss;
				mx = re[in[cen]+1];
			}
			ss = get_sz(in[up[x]]);
			if(up[x] != 1&&p[up[x]] == cen&&ss > ms) {
				ms = ss;
				mx = up[x];
			}
			x = p[up[x]];
		}
		if(cen != 1&&get_sz(in[cen]) <= i/2) cen = p[cen], ms = 0;
		else if(ms > i/2) cen = mx, ms = 0;
		cout << cen << ' ';
	}
}

 

I - 나는 행복합니다

16124번: 나는 행복합니다

안풀어서 모른다. 갓 tor012...

 

 

아래에 G번(JuQueen)풀이 써 둔거 있습니다. (tor012)