AtCoder Beginner Contest 137

Performance : 1506 

Rating : 1178 -> 1237 (+59)

 

ABC까지 풀고, D를 읽었는데 어떻게 풀지 생각이 안나서 한참동안 뇌절한 후 E를 읽었는데 절대 못 풀거 같아서 버리고 다시 돌아와서 D를 꽤 오래 걸려서 풀었다. 정작 솔루션은 간단한데 왜...흠;;

---

A. +-x

풀이 생략. 시키는 대로 구현하면 된다.

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

int main()
{
	int a, b;
	cin >> a >> b;
	cout << max(max(a+b,a-b),a*b);
}

---

B. One Clue

$x-k+1$ 부터 $x+k-1$ 까지 출력해주면 된다.

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

int main()
{
	int k, x;
	cin >> k >> x;
	for (int i = x-k+1; i<=x+k-1; i++)
		cout << i <<' ';
}

---

C. Green Bin

String을 직접 해싱하기는 귀찮고, 어차피 시간도 넉넉해 보이니 (그렇게 넉넉하진 않았지만 뭐...) 

각 String이 주어질 때마다 sort 한 다음 map에 집어넣자. sort한 결과가 같으면 서로 anagram이다. 

마지막에는 각 map을 돌면서 각 string의 출현 횟수가 $k$일때 

$$\sum \binom{k}{2}$$

한 값이 답인데, $k = 1$ 일 수 있으므로 따로 처리해 주면 된다.

#include <bits/stdc++.h>
#define ll long long
#define all(x) ((x).begin()),((x).end())
#define usecppio ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;

int n;
inline ll ct(ll k)
{
	return max(k*(k-1)/2,0LL);
}
map <string, ll> m;
int main()
{
	usecppio
	cin >> n;
	for (int i = 0; i<n; i++)
	{
		string str;
		cin >> str;
		sort(all(str));
		m[str]++;
	}
	ll ans = 0;
	for (auto it:m)
		ans += (ct(it.second));
	cout << ans;
}

---

D. Summer Vacation

어떤 일을 처리하면 $a_i$ 일 후에 $b_i$의 보상을 받을 수 있다. $m$일 전에 최대한 많은 보상을 받고 싶다.

 

처음에는 $a_i$ 일 동안 일을 해야 한다는 걸로 문제를 잘못 이해해서, 0-1 Knapsack 문제라고 생각했다. 근데 Knapsack이 되기에는 $n$ 이나 $w$ (이경우에는 총 일자) 가 너무 커서 시간에도 안맞을거 같은데 이걸 어떻게 하라는 거지 라면서 꽤 오래 고민하다가 E도 읽어보고... 

 

하튼 그러다가 다시 돌아와서 풀었다.

$m$일이 지나면 보상을 못 받으니까. 만약 이 일을 할거라면 $m-a_i$ 일 이전에 해야 한다. 

끝에서부터 앞으로 오면서, $i$일 째에 할 수 있는 일들을 priority queue에 보관한다. 그리고 매일 그 우선순위 큐 맨 위에서 일을 골라서 수행하면 (가장 가치가 높은 일을 처리하면), 맨 끝에서부터 가능한 최선을 Greedy하게 뽑아오는 셈이 되는데 이 경우가 최선임을 어렵지 않게 보일 수 있다.

 

#include <bits/stdc++.h>
#define all(x) ((x).begin()),((x).end())
#define usecppio ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
using pii = pair<int, int>;

priority_queue <int> pq;
vector <pii> work; //(lastdate, money)
int n, m;
int money;
int32_t main()
{
	usecppio
	cin >> n >> m;
	work.resize(n);
	for (int i = 0; i<n; i++)
	{
		int a, b;
		cin >> a >> b;
		work[i] = {m-a+1,b};
	}
	sort(all(work));
	for (int date = m; date > 0; date--)
	{
		if (!work.empty())
		{
			while(work.back().first==date)
			{
				pq.push(work.back().second);
				work.pop_back();
			}
		}

		if (!pq.empty())
		{
			money += pq.top();
			pq.pop();
		}
	}
	cout << money;
}

---

E번이랑 F번은 꽤 어려워 보였는데, 남은 시간동안 F번을 생각해 봤다. E번은 그래프 문제인데 대충 절대 못풀거 같아 보였기 때문에...

 

약간 잘못 생각했던 부분을 그대로 코딩하고 그나마도 디버깅에서 꼬인 것 때문에, 몇번 틀리고 라운드가 끝났다 :(

 

(언젠가 추가 예정)

$f(i) \equiv a_i \mod p$ 인 $p-1$차 다항식 $f(x)$를 찾는 문제로, $a_i$가 1 또는 0임을 이용하면

- $a_i$ 가 0일때는 다항식에 $(x-i)$ 를 곱해 주면 된다.

- $a_i$ 가 1인 것들끼리 모아서, 다항식을 만들어 주면 된다. 대충 $(x-i)$ 들 몇개의 곱과, 1로 만들고 싶은것 하나만 따로 놔주면 될 것 같다. 

---

D 푸는데 난이도에 비해 너무 오래 걸렸다 :(

요새 뭔가 업솔빙을 제대로 안해서 그런지 뭔가 공부가 제대로 안되는거 같은데, 언젠가 이거 F번은 꼭 업솔빙 해야지..ㅠㅠ