Codeforces Round #710 (Div. 3) 참가 후기

Codeforces Round #710 (Div.3)

3번째로 참가한 코드포스, 지금까지 참가만 했다 하면 서버가 터져서 Unrated되었는데 이번에는 무사히 넘어갔다.

A. Strange Table

어떤 $n\times m$ 크기의 배열에 대해 번호를 매기는데 번호를 매기는 방식은 우리가 흔히 위에서부터 왼쪽에서 오른쪽으로 매기는 방식을 "numbering by rows"로 정의하고 이와 다르게 왼쪽부터 위에서 아래로 매기는 망식을 "numbering by columns"로 정의하였다. 문제에서 원하는 것은 다음과 같다.

Polycarp doesn't have much time, so he asks you to find out what would be the cell number in the numbering "by rows", if in the numbering "by columns" the cell has the number x?

이 문장이 해석이 도통 안되어서 예제 입력 보면서 추측하려고 했으나 실패했다. 차근차근 읽어보니 numbering by columns로 $x$가 있던 위치가 만약 numbering by rows였다면 그 값은 얼마인지 묻는 것이다.

1. $x$가 $(i,\ j)\ (i,\ j \ge\ 0)$ 위치에 있다는 것만 알면 numbering by rows로 매겨지는 cell number는 $mi +j + 1$이 된다.
2. numbering by columns에서 각 행은 오른쪽으로 갈수록 $n$씩 늘어나므로 어떤 행의 cell number를 $n$으로 나눈 나머지는 모두 동일함을 알 수 있으므로 $x\ \%\ n$을 통해 몇번째 행에 위치하는지 알 수 있다(나누어 떨어지는 경우는 예외 처리)
3. 각 행에서 오른쪽으로 한 칸 갈때마다 $n$씩 늘어나므로 몇 칸 떨어져 있는지는 $n$으로 나눠서 쉽게 구할 수 있다.

시간 급하다고 문제 대충 읽고 입력 데이터만 보고 추측하다가 낭패를 봤다. 추측하더라도 잘 안되면 바로 문제를 다시 읽어봤어야 했었다.

public class A {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
		for (int tc = 0; tc < T; tc++) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			int n = Integer.parseInt(st.nextToken());
			int m = Integer.parseInt(st.nextToken());
			long x = Long.parseLong(st.nextToken());
			long ret = (((x % n == 0) ? n : (x % n)) - 1) * (long)m + (x - (x % n == 0 ? n : x % n)) / (long)n + 1;
			System.out.println(ret);
		}
	}

}

B. Partial Replacement

길이 $n$인 문자열 $s$가 주어지는데 문자열은 '.'(점) 혹은 '*'(별)로만 이루어져 있다. 그리고 다음에 규칙에 따라 최소한의 수만큼 '*'을 'x'로 치환하여야 한다.

1. 처음과 마지막 '*'은 'x'로 치환되어야 한다.
2. 'x'들 끼리의 거리($j - i$)는 최대 $k$여야 한다

가장 먼저 생각난 것은 '*'이 하나 혹은 둘밖에 없을 경우.
문제에서 주이저는 '*'들 끼리는 상기한 2번 조건을 만족시킨다 했으므로 더 이상 치환할 필요가 없다.
이외의 경우가 문제인데 앞에서부터 차근 차근 가장 마지막 'x'부터의 거리가 $k$가 되기 전에 치환해주는 식으로 하려고 했는데 맨 마지막에 'x'가 또 있는 것도 그렇고 이것 저것 고려해줘야할게 너무 많았다. 그래서 완전탐색으로 길을 돌렸다. 문자열의 어떤 지점에서 이전 정보는 가장 마지막으로 등장한 'x'의 위치 외에는 아무것도 필요하지 않음을 깨닫고 DP를 적용했다.

public class B {
	static int N; static int K;
	static int tail;
	static String S;
	static int[][] cache;
	
	static final int INF = 987654321;
	// S[i]부터 *을 x로 바꾸기 시작할 때, 최소한으로 바꾸는 횟수
	// last는 가장 마지막으로 나온 x의 위치
	static int dp(int i, int last) {
		if (i == tail) return i - last <= K ? 0 : INF;
		if (cache[i][last] != -1) return cache[i][last];
		if (S.charAt(i) == '.') return dp(i + 1, last);
		// 이번 위치부터 마지막 'x'까지 거리가 K를 넘으면 문자열의 끝에는 'x'가 무조건 있으므로 불가능하다.
        	if (i - last > K) return INF;
		// 안바꾸는 경우
		int min = dp(i + 1, last);
		// 바꾸기
		min = Math.min(min, 1 + dp(i + 1, i));
		return cache[i][last] = min;
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
		for (int tc = 0; tc < T; tc++) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			N = Integer.parseInt(st.nextToken());
			K = Integer.parseInt(st.nextToken());
			S = br.readLine();
			int head = N; tail = 0;
			for (int i = 0; i < S.length(); i++)
				if (S.charAt(i) == '*') {
					head = Math.min(head, i);
					tail = Math.max(tail, i);
				}
			if (head == tail) {System.out.println(1); continue;}
			if (tail - head <= K) {System.out.println(2); continue;}
			cache = new int[N][N];
			for (int i = 0; i < N; i++) Arrays.fill(cache[i], -1);
			System.out.println(2 + dp(head, head));
		}
	}

}

C. Double-ended Strings

주어진 문자열 $a$와 $b$의 양 끝을 지워가며 둘이 같게 만드는 최소 횟수를 구하는 문제.
이전 선택의 정보가 필요 없으므로 DP를 적용한다.

바로 전 문제에서 DP를 사용해서 그런지 보자마자 감히 딱 잡혀서 10분만에 풀었다.

public class C {
	static String A; static String B;
	static int[][][][] cache;
	
	static int dp(int ai, int aj, int bi, int bj) {
		if (aj - ai == bj - bi) {
			boolean same = true;
			for (int k = 0; k < aj - ai; k++)
				if (A.charAt(ai + k) != B.charAt(bi + k)) {same = false; break;}
			if (same) return 0;
		}
		if (cache[ai][aj][bi][bj] != 0) return cache[ai][aj][bi][bj];
		int min = 100;
		// A
		if (aj - ai > 0) {
			min = Math.min(min, 1 + dp(ai + 1, aj, bi, bj));
			min = Math.min(min, 1 + dp(ai, aj - 1, bi, bj));
		}
		// B
		if (bj - bi > 0) {
			min = Math.min(min, 1 + dp(ai, aj, bi + 1, bj));
			min = Math.min(min, 1 + dp(ai, aj, bi, bj - 1));
		}
		return cache[ai][aj][bi][bj] = min;
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
		for (int tc = 0; tc < T; tc++) {
			A = br.readLine();
			B = br.readLine();
			if (A.equals(B)) {System.out.println(0); continue;}
			cache = new int[A.length() + 1][A.length() + 1][B.length() + 1][B.length() + 1];
			System.out.println(dp(0, A.length(), 0, B.length()));
		}
	}
	
}