CF 717 D2 후기

너무 졸려서 1솔하고 자러갔습니다....

1035인데도 11시 넘어가니까 눈이 감기네요ㅎㅎ

 

A. Tit for Tat

제일 앞에 있는 원소를 감소시키고 맨 뒤에있는 원소는 증가시키면 자연스럽게 사전 역순으로 정렬을 할 수 있다는 관찰로 풀었습니다.

		int idx = 0;
		for (int i = 0; i < k; i++) {
			if (idx>n-1) break;
			if (arr[idx] > 0) {
				arr[idx]--;
				arr[n-1]++;
			}
			else {
				idx++;
				i--;
			}
		}

이런식으로 인덱스를 하나씩 전진시키면서 문제를 해결했습니다.

 

B. AGAGA XOOORRR

대회중에 풀지 못하고 끝나고 나서 해설보면서 업솔한 문제입니다.

풀이를 보고 푼 문제라 풀이의 정당성에 대해서는 의문이 있지만, 풀이를 그대로 구현해서 제출하니 AC를 받았습니다.

주어진 배열을 앞부분과 뒷부분(사실 중간) 이렇게 2가지로 나누고 앞부분=중간 부분=전체 합 이런 경우 YES를 출력합니다.

이때 물론 배열 전체 XOR값이 0인경우는 YES를 출력하게 먼저 예외처리를 해줍니다.

N^2 풀이지만 N이 2,000이라 충분합니다.

		if (total==0) cout << "YES" << "\n";
		else {
			int pre = arr[0];
			for (int i = 1; i < n; i++) {
				int mid = arr[i];
				for (int j = i+1; j < n; j++) {
					if (pre==mid && mid==total) {
						flag = true;
					}
					mid^=arr[j];
				}
				pre^=arr[i];
			}
			if (flag) cout << "YES" << "\n";
			else cout << "NO" << "\n";
		}

 

정말 오랜만에 CP라서 기분이 좋았습니다.

이번 주말에 또 코테가 있는데 결과가 좋으면 좋겠네요🙂