AtCoder Beginner Contest 172 후기

https://atcoder.jp/contests/abc172

AtCoder Beginner Contest 172 - AtCoder

---

 

끝나고 너무너무 아쉬웠던 대회였습니다. 마지막 문제인 F번 문제가 자신 있던 님 게임 알고리즘 문제여서 자신만만하게

도전했는데 ,1시간동안 풀고도 결국 못 풀었습니다 :( 사실문제풀이는 님 게임이 주가 아니라 xor연산이 핵심이었습니다.

아직 해설을보고도 이해 못해서 백준에서 xor문제를 몰아서 풀까 생각 중입니다. xor은 특징이 많아서 문제를 많이 풀어봐야 알 것 같습니다.

A, B- 생략합니다.

C- 알고리즘 분류는 이분 탐색을 달 수 있을 것 같습니다. 단순히 그리디 하게 접근해서 두 개의 테이블 중 작은 것을 빼면 틀립니다. 다음과 같은 반례가 있기 때문이죠.

5 3 105
100 1 1 1 1 1
80 60 40

그러니 두 테이블의 누적합을 미리 구해놓은 다음, 이분탐색을 섞어서 코드를 완성했습니다.

#include <iostream>
#include <vector>
#include <string>
#include <string.h>
#include <algorithm>
#include <math.h>
using namespace std;
typedef long long ll;

int main()
{
	ll N, M, K, ans = 0;
	cin >> N >> M >> K;
	vector<ll>pSum1(N + 1, 0), pSum2(M + 1, 0);

	for (int i = 0; i < N; i++) {
		ll tmp;
		cin >> tmp;
		if (i == 0)pSum1[i] = tmp;
		else pSum1[i] = pSum1[i - 1] + tmp;
	}
	for (int i = 0; i < M; i++) {
		ll tmp;
		cin >> tmp;
		if (i == 0)pSum2[i] = tmp;
		else pSum2[i] = pSum2[i - 1] + tmp;
	}

	for (int i = 0; i < N; i++) {
		if (pSum1[i] > K)continue;
		int left = 0, right = M - 1, idx = -1;
		while (left <= right) {
			int mid = (left + right) / 2;
			if (pSum1[i] + pSum2[mid] <= K) {
				idx = mid;
				left = mid + 1;
			}
			else right = mid - 1;
		}
		ans = max(ans,(ll) i + idx + 2);
	}
	for (int i = 0; i < M; i++) {
		if (pSum2[i] > K)continue;
		int left = 0, right = N - 1, idx = -1;
		while (left <= right) {
			int mid = (left + right) / 2;
			if (pSum2[i] + pSum1[mid] <= K) {
				idx = mid;
				left = mid + 1;
			}
			else right = mid - 1;
		}
		ans = max(ans, (ll)i + idx + 2);
	}
	cout << ans;

}

 각각의 테이블에서 i까지를  선택했을때, 남은 시간으로 얼마나 많이 다음 테이블에서 책을 선택할 수 있을지 이분 탐색으로 구할 수 있습니다. 

D- 약수의 개수를 빨리 구할 수있는 방법만 알 수 있습니다. NlogN의 시간 복잡도로 약수의 개수를 구할 수 있는 간단한 알고리즘이 있으니 그것을 사용하면 10^7의 크기여도 충분히 시간 안에 돌아갑니다.

#include<iostream>
#include<vector>
#include <string.h>
using namespace std;
typedef long long ll;
const int MAX_N=1e7+2;
int cnt[MAX_N]={0,};


int main()
{
    for(int i=1;i<MAX_N;i++)
        for(int j=1;j<=MAX_N/i;j++) cnt[i*j]++;

    int N;
    cin>>N;
    ll sum=0;
    for(int i=1;i<=N;i++)
        sum+=(ll)cnt[i]*i;
    cout<<sum;
}