Sumitomo Mitsui Trust Bank Programming Contest 2019::::Gratus' Blog

Sumitomo Mitsui Trust Bank Programming Contest 2019

알고리즘 문제풀이/AtCoder 2019. 12. 2. 02:44

Atcoder Beginner Contest 에 기업 후원이 붙은거 같은데, 사실 뭔지 잘 모르겠다. Rated range를 보니 ABC랑 똑같길래 뛰기로 했다. 코포에 가끔 있는 Round xxx (yyy cup) 같은 느낌? 근데 정식 ABC 라운드에는 세지 않는거 같다.

Performance : 2373

Rating Change : 1570 -> 1725 (+155)

Performance 가 엄청 높아서 그래도 200점은 줄 줄 알았는데... ㅠ

뭔가 시험기간이 슬슬 다가오니까 PS가 잘 되는거 같다. (그래서 학점관리가 안된다 ㅋㅋㅋ)

A. November 30

$\texttt{m1 != m2}$.

#include <bits/stdc++.h>
using namespace std;

int32_t main()
{
	int m1, m2, d1, d2;
	cin >> m1 >> d1 >> m2 >> d2;
	printf("%d\n",m1==m2?0:1);
}

B. Tax Rate

어떤 수 $n$ 이 $1.08 x$ 를 내림한 수일 때, 자연수 $x$를 찾는 문제. 1.08로 나눠도 상관이 없...나? 뭔가 실수 나눗셈을 해서 뭔가 찾는다는 행동이 매우 기분나쁘기 때문에 O(n) 으로 그냥 1부터 5만까지 답이 맞는지 확인하기로 했다. 결과적으로는 답이 ceil(n/1.08) 인지 아닌지만 보면 되는거 같긴한데, 실수오차는 항상 기분나쁘다.

#include <bits/stdc++.h>
using namespace std;

int32_t main()
{
	int t; cin >> t;
	for (int i = 1; i<=50000; i++)
	{
		int bef = i;
		if ((int)(bef * 1.08) == t)
		{
			printf("%d\n",i);
			return 0;
		}
	}
	printf(":(");
}

놀랍게도 이 문제를 1틀했는데, 이유는 실패 상황에서 출력 문자열이 :( 인걸 못 보고 -1을 출력해서..

아니 :( 같은걸 출력하게 시키는걸 처음 보는데다가, 결정적으로 쓱 보고 코딩했는데 예제 입출력에 보인 :(가 묘하게 슬쩍 볼때는 -1이랑 비슷하게 생겨서 못 봤다. 바로 세터 욕하고 다시 제출. 앳코더는 쉬운 문제에서 틀려도 마지막 제출 시간 + 5분 페널티라서 더 아프다.

C. 100 to 105

100, 101, 102, 103, 104, 105 원 짜리 물건을 적당히 사서 $X$원이 되게 할 수 있는지 묻는 문제.

최대 개수가 어차피 10만개 이하이고 (사실 1000개 이하였다) $k$개를 사면 $100k$ 이상 $105k$ 이하의 모든 가격을 만들 수 있기 때문에, 모든 '개수' 를 돌면서 시도한다.

#include <bits/stdc++.h>
using namespace std;
int32_t main()
{
	int t; cin >> t;
	for (int i = 1; i<=100000; i++)
	{
		if (100*i <= t && t <= 105*i)
		{
			printf("1\n");
			return 0;
		}
	}
	printf("0");
}

D. Lucky Pin

0부터 9까지의 숫자들로 구성된 긴 문자열이 주어졌을 때, 여기서 3개짜리 sub-sequence를 뽑아 PIN을 만들 수 있다. 가능한 PIN의 경우를 세는 문제.

단순한 Brute Force 솔루션은 $O(nC3)$, 즉 $O(n^3)$ 시간 복잡도니까 불가능하지만, 가능한 PIN이 세 자리 수이므로 많아야 1000개임에 주목한다. 한 PIN을 만들 수 있는지, 즉 예를들어 342면 3-4-2 순서로 나타나는 Sub-sequence가 있는지 판정하는 것은 $O(n)$ 에 가능. $n = 30000$ 이니까 1000n 은 충분히 가능한 복잡도고, 이렇게 돌리면 된다.

#include <bits/stdc++.h>
using namespace std;
int valid = 0;
string str;
int orig[30303];
int32_t main()
{
	int n;
	cin >> n;
	cin >> str;
	for (int i = 0; i < n; i++)
		orig[i] = str[i]-'0';
	for (int i = 0; i < 1000; i++)
	{
		int a = i/100;
		int b = (i/10)%10;
		int c = i%10;
		int ck = 0;
		for (int pos = 0; pos < n; pos++)
		{
			if (ck == 0 && (orig[pos] == a))
				ck = 1;
			else if (ck == 1 && (orig[pos] == b))
				ck = 2;
			else if (ck == 2 && (orig[pos] == c))
				ck = 3;
			else continue;
		}
		if (ck == 3) valid++;
	}
	cout << valid << '\n';
}

E. Colorful Hats 2

$n$명의 사람이 한 줄로 서 있고, RGB 세 가지 중 한 색의 모자를 쓰고 있다. 각 사람은 자기보다 앞에 있는 사람들 중 자기와 같은 색의 모자를 쓴 사람의 수를 세서 보고한다.

이를 이용해서 전체 색 배열의 경우의 수를 세는 문제인데,

우선 세 가지 색 자체에는 아무런 의미가 없으므로, 첫 번째 사람이 색깔 1을 골랐다고 치고 경우의 수에 3을 곱한다.

이다음 사람이 0을 보고했다면, 다른 색을 고른 것이므로 2를 골랐다고 치고 2를 곱한다.

만약 1을 보고했다면, 1번과 같은 색을 고른 것이므로 현재 각 색깔별 사람의 수는 (2, 0, 0) 이다. 어떤 색인지 확실하므로 1을 곱한다.

이를 반복하는데, 예를들어 현재 색깔별 사람 수가 (4, 3, 3) 이고 11번이 3을 보고했다면 현재 3명이 쓰고 있는 모자 중 어느 쪽인지 알 수 없다. 알 수 없으므로 둘 중 하나인 것이고, 경우의 수에 2를 곱하고 아무거나 골라서 +1 해서 (4, 4, 3) 으로 만든다. 결국 핵심은 '같은게 몇개인지 세서 곱하고', '아무거나 올려주기'.

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define int ll
#define usecppio ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
const int MOD = 1000000007;
int groups[3];
int a[101010];
int answer = 1;
int32_t main()
{
	usecppio
	int n;
	cin >> n;
	for (int i = 0; i<n; i++)
	{
		cin >> a[i];
		int ct = 0;
		int mark = -1;
		for (int j = 0; j<3; j++)
		{
			if (groups[j] == a[i])
			{
				ct++;
				mark = j;
			}
		}
		groups[mark]++;
		answer *= ct;
		answer %= MOD;
	}
	cout << answer << '\n';
}

F. Interval Running

E번을 시작 후 19분에 해결한 시점에서 이 대회가 뭔가 이상하다는 생각이 들긴 했는데, 앳코더 E번은 가끔 쉬운것도 나오는거 같아서 그러려니 하고 넘어왔다.

두 사람이 달리기를 하는데, A는 $T_1$ 분 동안 $a_1$ m / min, $T_2$ 분 동안 $a_2$ m / min 의 속도로 달리고 B는 같은 시간에 $b_1$, $b_2$ 의 속도로 달린다. 둘이 만나는 횟수를 찾는 문제.

우선 특이 케이스들을 쳐내자. 만약 A가 항상 빠르다면, 절대 만날리가 없다. B가 항상 빨라도 마찬가지.

A와 B가 $T_1 + T_2$ 시간, 즉 1 주기 동안 달리는 거리가 같다면 무한히 많이 만난다.

이제 앞에 빠른 사람과 뒤에 빠른 사람이 나뉘어지는데, (첫 조건을 통과했으므로)

만약 A가 1 주기 동안 더 먼 거리를 갈 수 있고, 거기에 더해서 A가 앞에 빠른 사람이라면 B는 항상 뒤에서 따라가다가 A가 다시 빨라지는 상황이 되므로 절대 만나지 않는다.

즉, 가능한 경우는 "앞에 빠른 사람" 이 1 주기동안 더 짧은 거리를 달리는 상황만 가능한데,

이경우 앞에 빠른 사람을 Without loss of generality A로 잡고, A가 앞에서 벌려놓은 차이를 B가 따라잡는 식으로 생각할 수 있다. 그런데 딱 따라잡는게 아니라 B가 조금 더 가게 되고, 이 조금 더 간 거리를 다시 A가 주기의 앞부분이 되면서 따라잡는다. 이 행동을 반복하다가, B가 조금 더 간 것들이 쌓여서 주기의 앞부분이 끝나고 다시 B가 따른 순간이 올 때까지 A가 B를 따라잡지 못한다면, 더이상 A와 B는 만날 수 없다.

정확한 공식을 유도하는 것은 조금 시간이 걸리지만, 문제 자체는 어렵지 않다. 케이스만 조금 분류하면 되는 거라서, Codeforce 기준 D2C~D? 정도 느낌이 들었다. ~~(사실 대회가 좀 선넘으면 B에도 낼거 같다)~~ 실제로 나도 20분 만에 풀기도 했고...

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define int ll
#define usecppio ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using pii = pair<int, int>;
using ppp = pair<int , pii>;
const int MOD = 1000000007;
int t1, t2, a1, a2, b1, b2;
int lena, lenb;
int32_t main()
{
	cin >> t1 >> t2 >> a1 >> a2 >> b1 >> b2;
	lena = (t1*a1 + t2*a2);
	lenb = (t1*b1 + t2*b2);
	if (lena == lenb)
	{
		cout << "infinity\n";
		return 0;
	}
	if ((a1 > b1 && a2 > b2) || (a1 < b1 && a2 < b2))
	{
		cout << "0\n";
		return 0;
	}
	if ((lena > lenb && a1 > b1) || (lena < lenb && a1 < b1))
	{
		cout << "0\n";
		return 0;
	}
	if (b1 > a1)
	{
		swap(a1, b1);
		swap(a2, b2);
		swap(lena, lenb);
	}
	int gap = (t1*a1 - t1*b1);
	int take = (t2*b2 - t2*a2);
	int loss = take-gap;
	cout << (gap/loss)*2 + (gap%loss==0?0:1) << '\n';
}

42분에 F번 AC를 받고 대회가 끝났다. 처음으로 대회중에 뭔가를 올솔브했다 :dhk:

은근히 E나 F가 말린 사람들이 좀 있어서 생각보다 Performance가 많이 높게 나온거 같다.

+ :( 에 의한 1틀만 아니었으면 100등 안에도 들 수 있었다. :( :( :( :( :(

'알고리즘 문제풀이 > AtCoder' 카테고리의 다른 글

AtCoder Beginner Contest 137 (0)	2019.08.11
AtCoder Beginner Contest 136 (2)	2019.08.06

Gratus' Blog