Codeforces Round #478 (Div. 2)

코드포스 후기 #9

Codeforces Round #478 (Div. 2)
2018/05/02(화) 23:05

요즘 코드잼 덕분에 알고리즘 공부 재개한 기념으로 1년 4개월 만에 코드포스 참가!

마지막으로 참가한게 라운드 390이었는데 오늘 참가하면서 보니 라운드 478번이더라. 얼마나 오래 쉬었는지 체감하는 부분..

지난 라운드(390)에서 오랜만에 했다가 처참한 결과를 얻었던 경험이 있어서...

또 그렇게 될까봐 시작하기 전부터 엄청 쫄아있었다. 하하..

그리고 대회 중간에 마우스 배터리가 다돼서 마우스를 못쓰는 상황에 처하기도 했으나,

이미 그 때는 풀 수 있는 문제는 다 제출한 상태였어서 그냥 느긋하게 충전시켜놓고 연습장에 끄적끄적만 하면서 남은 문제는 대충 풀이를 생각해보기도 했는데 시간안에 구현못하겠다 하고 빠른 포기!

오랜만에 남기는 후기이지만 다행히 후기를 쓰기 위한 서식을 잘 만들어 놓아서 귀찮음을 이겨내고 쓰고있다.

예전의 나에게 감사하는 마음을 가지게 됨과 동시에 열심히 하자는 또 잠깐의 다짐(ㅠㅠ)

A. Aramic script

주어진 word들에 대응하는 root를 찾고 서로 다른 root의 개수를 구하는 문제.

1) word를 root 대응 시키는 건 비트마스크를 통해 root를 숫자로 표현했다.

2) 서로 다른 것들의 개수를 구하는 부분은 Set class를 사용했다. Set에 계속 add 한다음에 마지막에 size를 출력하는 방식

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.Set;

public class ProblemA {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		String[] word = br.readLine().split(" ");
		Set<Integer> set = new HashSet<Integer>();
		for (int i=0; i<n; i++) {
			int root = 0;
			String w = word[i];
			for (int j=0; j<w.length(); j++) {
				root |= 1 << (w.charAt(j)-'a');
			}
			set.add(root);
		}
		
		System.out.println(set.size());
	}
}

B. Mancala

one move만 고려하면 되는 문제라 그냥 무식하게 풀었다.

14개 case 각각에 대해 score를 구하고 그 중에 max를 출력

다만 $a_i$가 꽤 큰 숫자이니까 1개씩 놓아가면 큰일날 것 같고 14로 나눈 몫과 나머지를 이용해서 각 칸에 저장되는 스톤의 개수를 구했다.

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class ProblemB {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] tmp = br.readLine().split(" ");
		int[] hole = new int[14];
		for (int i=0; i<14; i++) {
			hole[i] = Integer.parseInt(tmp[i]);
		}
		long max = 0;
		for (int i=0; i<14; i++) {
			long res = 0;
			int x = hole[i] / 14;
			int y = hole[i] % 14;
			if (x % 2 == 0) {
				res += x;
			}
			for (int j=1; j<14; j++) {
				int c = (i+j)%14;
				int z = hole[c] + x;
				if (j <= y) z++;
				if (z % 2 == 0) {
					res += z;
				}
			}
			if (res > max) {
				max = res;
			}
		}
		System.out.println(max);
	}
}

C. Valhalla Siege

warrior가 일렬로 서서 죽어나가는 문제...(?)

각 warrior strength($a_i$)의 부분합($a_0$~$a_i$)를 구해놓고 binary search로 어디까지 죽어나가는지 index를 구하면 쉽게 풀린다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;

public class ProblemC {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] tmp = br.readLine().split(" ");
		int n = Integer.parseInt(tmp[0]);
		int q = Integer.parseInt(tmp[1]);
		tmp = br.readLine().split(" ");
		long[] S = new long[n];
		S[0] = Integer.parseInt(tmp[0]);
		for (int i=1; i<n; i++) {
			S[i] = S[i-1] + Integer.parseInt(tmp[i]);
		}
		tmp = br.readLine().split(" ");
		long sum = 0;
		for (int i=0; i<q; i++) {
			long k = Long.parseLong(tmp[i]);
			sum += k;
			if (sum >= S[n-1]) {
				System.out.println(n);
				sum = 0;
			} else {
				int res = Arrays.binarySearch(S, sum);
				if (res >= 0) {
					int cnt = res + 1;
					System.out.println(n-cnt);
				} else {
					int cnt = -res - 1;
					System.out.println(n-cnt);
				}
			}
		}
	}
}

D. Ghosts

미제출

두 유령이 마주치는 조건식까지는 구했는데 그냥 임의의 두 점 비교하는 $n^2$ 방법밖에 생각못해서 흠...

E. Hag's Khashba

미제출

풀이는 생각했는데 남은 시간동안 코드 짤 엄두가 나지 않아서 손도 안댔다.

다각형의 무게중심을 구한다음에 무게중심의 위치를 갱신해나가면서 query가 들어왔을 때 그 점의 좌표는 무게중심+다각형 정보 기준으로 구하는 걸로...

Final Standings

Rank	Points	Extras	A 500	B 1000	C 1500	D 2000	E 2500
489	2630	-	486 00:07	908 00:23	1236 00:44	-1

그래도 알고리즘 대회 자체를 오랜만에 하는건 아니라서 그런지 다행히 평타?는 친 것 같다.

C까지 푸는데 44분걸렸는데 나머지 1시간 넘게는 D, E 번갈아보다가 D 한번 건드려보고 끝...

Rating Changes

Rank	Points	Rating
489	2630	1663 → 1682 (+19)

오랜만에 한 것 치고 선방했다고 생각했으나 굉장히 찔끔 올라서 슬프다..ㅠㅠ

보라색을 목표로 다시 한 번...!

※ 링크 : 대회공지 / 출제자해설