tookunn’s diary

主に競技プログラミング関係

Codeforces #369 Div2 A~C

Codeforces

A

問題

考察

・"OO"があれば"++"に変えるだけ。

ソースコード

import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.NoSuchElementException;
 
import java.util.*;
 
public class Main {
	int N;
	public void solve() {
		N = nextInt();
		boolean find = false;
		String[] ss = new String[N];
		for(int i = 0;i < N;i++){
			String s = next();
			if(!find && s.indexOf("OO") != -1){
				s = s.replaceFirst("OO","++");
				find = true;
			}
			ss[i] = s;
		}
		
		if(!find){
			out.println("NO");
			return;
		}
		out.println("YES");
		
		for(int i = 0;i < N;i++){
			out.println(ss[i]);
		}
	}
 
	public static void main(String[] args) {
		out.flush();
		new Main().solve();
		out.close();
	}
 
	/* Input */
	private static final InputStream in = System.in;
	private static final PrintWriter out = new PrintWriter(System.out);
	private final byte[] buffer = new byte[2048];
	private int p = 0;
	private int buflen = 0;
 
	private boolean hasNextByte() {
		if (p < buflen)
			return true;
		p = 0;
		try {
			buflen = in.read(buffer);
		} catch (IOException e) {
			e.printStackTrace();
		}
		if (buflen <= 0)
			return false;
		return true;
	}
 
	public boolean hasNext() {
		while (hasNextByte() && !isPrint(buffer[p])) {
			p++;
		}
		return hasNextByte();
	}
 
	private boolean isPrint(int ch) {
		if (ch >= '!' && ch <= '~')
			return true;
		return false;
	}
 
	private int nextByte() {
		if (!hasNextByte())
			return -1;
		return buffer[p++];
	}
 
	public String next() {
		if (!hasNext())
			throw new NoSuchElementException();
		StringBuilder sb = new StringBuilder();
		int b = -1;
		while (isPrint((b = nextByte()))) {
			sb.appendCodePoint(b);
		}
		return sb.toString();
	}
 
	public int nextInt() {
		return Integer.parseInt(next());
	}
 
	public long nextLong() {
		return Long.parseLong(next());
	}
 
	public double nextDouble() {
		return Double.parseDouble(next());
	}
}

B

問題

考察

・0が含まれてない縦,横,斜めの合計値がすべてが同じであることを確認する。
・0が含まれてる縦または横,斜めの合計値とさっき確認した合計値との差を0のマスに入れて,あとはすべての縦,横,斜めの合計値が同じであるかを確認する。
・実装が辛い以外の感情が無い。

ソースコード

import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.NoSuchElementException;

public class B {
	int N;
	long[][] a;
	int y,x;

	public boolean check1(){
		long[] row = new long[N];
		long[] col= new long[N];
		long[] dia = new long[2];
		for(int i = 0;i < N;i++){
			if(i == y)continue;
			for(int j = 0;j < N;j++){
				row[i] += a[i][j];
			}
		}

		for(int i = 0;i < N;i++){
			if(i == x);
			for(int j = 0;j < N;j++){
				col[i] += a[j][i];
			}
		}

		boolean f1 = true;
		for(int i= 0;i < N;i++){
			if(i == y && i == x){
				f1 = false;
				break;
			}

			dia[0] += a[i][i];
		}
		boolean f2 = true;
		for(int i = 0;i < N;i++){
			if(i == y && N - i - 1== x){
				f2 = false;
				break;
			}

			dia[1] += a[i][N - i - 1];
		}

		long max = 0;
		long min = (long)1e18 + 7;

		if(f1){
			max = Math.max(max,dia[0]);
			min = Math.min(min,dia[0]);
		}

		if(f2){
			max = Math.max(max,dia[1]);
			min = Math.min(min, dia[1]);
		}

		for(int i = 0;i < N;i++){
			if(i == y)continue;
			max = Math.max(max, row[i]);
			min = Math.min(min, row[i]);
		}

		for(int i = 0;i < N;i++){
			if(i == x)continue;
			max = Math.max(max,col[i]);
			min = Math.min(min,col[i]);
		}
		return max == min;
	}

	public long check2(){
		long[] row = new long[N];
		long[] col = new long[N];
		long[] dia = new long[2];
		for(int i = 0;i < N;i++){
			for(int j = 0;j < N;j++){
				row[i] += a[i][j];
				col[j] += a[i][j];
			}
		}

		long d1 = row[(y+1)%N] - row[y];
		long d2 = col[(x+1)%N] - col[x];

		if(d1 != d2)return -1;

		a[y][x] = d1;
		for(int i = 0;i < N;i++){
			dia[0] += a[i][i];
		}
		for(int i = 0;i < N;i++){
			dia[1] += a[i][N - i - 1];
		}

		if(dia[0] != dia[1])return -1;

		row = new long[N];
		col = new long[N];

		for(int i = 0;i < N;i++){
			for(int j = 0;j < N;j++){
				row[i] += a[i][j];
				col[j] += a[i][j];
			}
		}
		long pre = dia[0];
		for(int i = 0;i < N;i++){
			if(pre != row[i])return -1;
		}

		for(int i = 0;i < N;i++){
			if(pre != col[i])return -1;
		}
		return d1 <= 0 ? -1 : d1;


	}

	public void solve() {
		N = nextInt();
		a = new long[N][N];
		for(int i = 0;i < N;i++){
			for(int j = 0;j < N;j++){
				a[i][j] = nextInt();
				if(a[i][j] == 0){
					y = i;
					x = j;
				}
			}
		}

		if(N == 1){
			out.println(1);
			return;
		}

		if(!check1()){
			out.println(-1);
			return;
		}
		long res = check2();
		out.println(res);
	}

	public static void main(String[] args) {
		out.flush();
		new B().solve();
		out.close();
	}
}

C

問題

考察

・ $dp[i][j][k] =$ (i-1)番目の時に色jを選んで、分割数がkの時にi番目の木の色を決める時の塗料の量
・この解法の計算量は $O(NK(M^2))$ だが, $O(NKM)$ の解法もあるらしい。
codeforces.com

ソースコード(メモ化再帰)

import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.NoSuchElementException;

import java.util.*;

public class Main {
	static long INF = (long)1e18;
	int N,M,K;
	int[] c;
	int[][] ps;
	long[][][] dp;
	
	public long dfs(int n,int pre,int k){
		
		if(n == N){
			if(k == K){
				return 0;
			}else{
				return INF;
			}
		}
		
		if(dp[n][pre][k] != -1){
			return dp[n][pre][k];
		}
		
		long ret = INF;
		
		if(c[n] != 0){
			long res;
			if(c[n] == pre){
				res = dfs(n + 1,c[n],k);
			}else{
				res = dfs(n + 1,c[n],k + 1);
			}
			ret = Math.min(ret,res);
		}else{
			
			for(int next = 1;next <= M;next++){
				long res;
				if(next == pre){
					res = dfs(n + 1,next,k);
				}else{
					res = dfs(n + 1,next,k + 1);
				}
				ret = Math.min(ret,res + ps[n][next - 1]);
			}
		}
		
		return dp[n][pre][k] = ret;
	}
	
	public void solve() {
		N = nextInt();
		M = nextInt();
		K = nextInt();
		c = new int[N];
		ps = new int[N][M];
		dp = new long[100 + 1][100 + 2][100 + 1];
		for(int i = 0;i < N;i++){
			c[i] = nextInt();
		}
		
		for(int i = 0;i < N;i++){
			
			for(int j = 0;j < M;j++){
				ps[i][j] = nextInt();
			}
		}
		
		for(int i = 0;i < 100 + 1;i++){
			for(int j = 0;j < 100 + 2;j++){
				for(int k = 0;k < 100 + 1;k++){
					dp[i][j][k] = -1;
				}
			}
		}
		
		long ans = dfs(0,0,0);
		out.println(ans == INF ? -1 : ans);
		
	} 

	public static void main(String[] args) {
		out.flush();
		new Main().solve();
		out.close();
	}
}

ソースコード(fordp)

import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.NoSuchElementException;

import java.util.*;

public class Main {
	static long INF = (long)1e18;
	int N,M,K;
	int[] c;
	int[][] ps;
	long[][][] dp;
	
	public void solve() {
		N = nextInt();
		M = nextInt();
		K = nextInt();
		c = new int[N];
		ps = new int[N][M];
		dp = new long[100 + 1][100 + 2][100 + 2];
		for(int i = 0;i < N;i++){
			c[i] = nextInt();
		}
		
		for(int i = 0;i < N;i++){
			
			for(int j = 0;j < M;j++){
				ps[i][j] = nextInt();
			}
		}
		for(int i = 0;i < 100 + 1;i++){
			for(int j = 0;j < 100 + 2;j++){
				for(int k = 0;k < 100 + 2;k++){
					dp[i][j][k] = INF;
				}
			}
		}
		
		if(c[0] == 0){
			for(int i = 1;i <= M;i++){
				dp[0][i][1] = ps[0][i - 1];
			}
		}else{
			dp[0][c[0]][1] = 0;
		}
		
		for(int i = 1;i < N;i++){
			if(c[i] == 0){
				for(int pre = 1;pre <= M;pre++){
					for(int next = 1;next <= M;next++){
						for(int k = 1;k <= K;k++){
							if(pre == next){
								dp[i][next][k] = Math.min(dp[i][next][k],dp[i - 1][pre][k] + ps[i][next - 1]);
							}else{
								dp[i][next][k + 1] = Math.min(dp[i][next][k + 1],dp[i - 1][pre][k] + ps[i][next - 1]);
							}
						}
					}
				}
			}else{
				int next = c[i];
				for(int pre = 1;pre <= M;pre++){
					for(int k = 1;k <= K;k++){
						if(next == pre){
							dp[i][next][k] = Math.min(dp[i][next][k],dp[i - 1][pre][k]);
						}else{
							dp[i][next][k + 1] = Math.min(dp[i][next][k + 1],dp[i - 1][pre][k]);
						}
					}
				}
			}
		}
		
		long ans = INF;
		
		for(int i = 1;i <= M;i++){
			ans = Math.min(ans,dp[N - 1][i][K]);
		}
		
		out.println(ans == INF ? -1 : ans);
		
	} 

	public static void main(String[] args) {
		out.flush();
		new Main().solve();
		out.close();
	}
}