Codeforces Round #372 (Div. 2)

코드포스 후기 #4

Codeforces Round #372 (Div. 2)
2016/09/17(토) 22:35

새벽에 하는거 은근 부담인데 밤10시 인근에 하니깐 좋았다!

게다가 토요일 ^^

A. Crazy Computer

수열의 차이가 일정한 수 $c$ 초과이면 앞의 숫자들을 다 날리고 마지막에 남는 숫자의 갯수를 세는 문제

앞에서부터 날릴 필요 없이 뒤에서 출발해서 break문으로 탈출~

import java.util.Scanner;

public class ProblemA {
	public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int c = sc.nextInt();
		
		int[] num = new int[n+1];
		for (int i=1; i<=n; i++) {
			num[i] = sc.nextInt();
		}
		
		int cnt = 1;
		for (int i=n-1; i>0; i--) {
			if (num[i+1] - num[i] <= c) {
				cnt++;
			} else {
				break;
			}
		}
		
		System.out.println(cnt);
	}
}

B. Complete the Word

알파벳 A-Z를 하나씩 가지고 있는 길이 26짜리 substring이 존재도록 문자열을 채우는 문제 (불가능하면 -1)

처음엔 문제에서 말하는 substring의 개념을 잘못 생각해서(떨어져 있는 문자들을 모아서 만들 수 있는 걸로) 풀었다가 제출 전에 문자열 덩어리인거라고 깨닫고 다시 코딩했다.

시간은 좀 버렸지만 다행히 감점없이 한번에 통과할 수 있었다. 후우

처음부터 26자씩 스캔하면서 주어진 문자열에서 dup이 발생하는지 체크해서 dup이 없는 substring 부분을 찾으면 그 부분을 A-Z로 적절하게 채우고 나머지 부분은 전부 A를 출력했다.

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 s = br.readLine();
		
		if (s.length() < 26) {
			System.out.println(-1);
		} else {
			int front = 0;
			boolean[] checked = null;
			while (front <= s.length()-26) {
				checked = new boolean[26];
				boolean isDup = false;
				for (int i=0; i<26; i++) {
					char ch = s.charAt(front+i);
					if (ch == '?') {
						continue;
					} else if (checked[ch-'A']) {
						isDup = true;
						break;
					} else {
						checked[ch-'A'] = true;
					}
				}
				
				if (isDup) {
					front++;
				} else {
					break;
				}
			}
			
			if (front == s.length()-25) {
				System.out.println(-1);
			} else {
				int cur = 0;
				for (int i=0; i<s.length(); i++) {
					char ch = s.charAt(i);
					if (ch == '?') {
						if (i >= front && i < front+26) {
							while (checked[cur]) cur++;
							System.out.print((char)('A'+cur++));
						} else {
							System.out.print('A');
						}
					} else {
						System.out.print(ch);
					}
				}
			}
		}
	}
}

C. Plus and Square Root

뭔가 수식으로 풀 수 있는 문제가 나오면 은근 기분이 좋다.

머리 좀 굴린 댓가로 코드가 엄청 짧게 나오는ㅋㅋ

문제의 조건이 구구절절 있는데 내맘대로 요약하면...!

$k$의 배수에 제곱근을 취해서 $k+1$의 배수가 되게 모든 $k \le n$에 대해서 삽질을 하는거다.

레벨 $k$가 된 직후 화면에 나오는 숫자를 $x_k$라고 할 때,

$x_k=(k-1)k$ 라고 가정해보면, $x_{k+1}=k(k+1)$이다.

${x_{k+1}}^2=k^2(k^2+2k+1)=(k^3+2k^2+k)k\\ \qquad=(k-1)k+(k^3+2k^2+1)k=x_k+(k^3+2k^2+1)k$

따라서 레벨 $k$에서 $+$연산을 $k^3+2k^2+1$번 해주면 된다. (레벨 1→2 케이스만 예외로 처리)

import java.util.Scanner;

public class ProblemC {
	public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		
		System.out.println(2);
		for (long k=2; k<=n; k++) {
			System.out.println((k+2)*k*k+1);
		}
	}
}

D. Complete The Graph

미제출

E. Digit Tree

미제출

Final Standings

Rank	Points	Extras	A 500	B 1000	C 1500	D 2000	E 2500
493	2404	-	488 00:06	836 00:41	1080 01:10

D번 뭔가 풀수 있을듯 말듯 궁리하다가 결국 제출은 못했다.

여태까지 계속 solved 3문제였는데 4문제 풀고싶다!

Rating Changes

Rank	Points	Rating
493	2404	1648 → 1696 (+48)

감점없이 푸니깐 점수가 살짝 오른다.

엉금엉금 기어가더라도 레이팅 꾸준히 올랐으면..!

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