AtCoder Beginner Contest 079

ABCの３完でした。
連続して3完できて30分くらいで3問解けたので、成長した感がありました。

A問題
同じ数字:○
異なる数字:✕
とすると、yesの場合は○○○✕と✕○○○の二通りある。noの場合はそれ以外。

import java.util.Scanner;
 
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String s = sc.next();
		if(s.charAt(0) == s.charAt(1) && s.charAt(1)== s.charAt(2) || s.charAt(1) == s.charAt(2) && s.charAt(2)== s.charAt(3)) {
			System.out.println("Yes");
		} else {
			System.out.println("No");
		}
	}
}

B問題
問題文の通りに実装
動的計画法の一番シンプルな題材だと思う。

import java.util.Scanner;
 
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		long[] l = new long[n + 1];
		l[0] = 2;
		l[1] = 1;
		for(int i = 2 ; i <= n ; i++) {
			l[i] = l[i - 1] + l[i - 2];
		}
		System.out.println(l[n]);
	}
}

C問題
0以上9以下の数字が4つ与えられるので、それぞれの数字間に+か-を入れた結果が7に等しければ、その計算式を出力する問題。
'+'と'-'を入れる方法は全部で2^3=8通りあるので、頑張って全ての場合をif文で書きました。

import java.util.Scanner;
 
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String s = sc.next();
		int a = Integer.valueOf(String.valueOf(s.charAt(0)));
		int b = Integer.valueOf(String.valueOf(s.charAt(1)));
		int c = Integer.valueOf(String.valueOf(s.charAt(2)));
		int d = Integer.valueOf(String.valueOf(s.charAt(3)));
		if(a + b + c + d == 7) {
			System.out.println(a + "+" + b + "+" + c + "+" + d + "=" + (a + b + c + d));
			return;
		} else if(a + b + c - d == 7) {
			System.out.println(a + "+" + b + "+" + c + "-" + d + "=" + (a + b + c - d));
			return;
		} else if(a + b - c + d == 7) {
			System.out.println(a + "+" + b + "-" + c + "+" + d + "=" + (a + b - c + d));
			return;
		} else if(a - b + c + d == 7) {
			System.out.println(a + "-" + b + "+" + c + "+" + d + "=" + (a - b + c + d));
			return;
		} else if(a + b - c - d == 7) {
			System.out.println(a + "+" + b + "-" + c + "-" + d + "=" + (a + b - c - d));
			return;
		} else if(a - b + c - d == 7) {
			System.out.println(a + "-" + b + "+" + c + "-" + d + "=" + (a - b + c - d));
			return;
		} else if(a - b - c + d == 7) {
			System.out.println(a + "-" + b + "-" + c + "+" + d + "=" + (a - b - c + d));
			return;
		} else if(a - b - c - d == 7) {
			System.out.println(a + "-" + b + "-" + c + "-" + d + "=" + (a - b - c - d));
			return;
		}
		System.out.println(1);
	}
}

最後の1を出力するコードをなぜかいたのかは未だにわからないです。多分打ち間違いか本番で焦って書いたかのどちらかです。
あと、TL上でビット演算で解いた人が多かったので、自分でも解いてみました。

import java.util.Scanner;
 
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String a = sc.next();
		int[] x = new int[4];
		for(int i = 0 ; i < 4 ; i++) {
			x[i] = a.charAt(i) - '0';
		}
		for(int i = 0 ; i < 8 ; i++) {
			int sum = x[0];
			String s = "" + (char)(x[0] + '0');
			for(int j = 0 ; j < 3 ; j++) {
				if((i & (1 << j)) == 0) {
					sum += x[j + 1];
					s += '+';
					s += "" + (char)(x[j + 1] + '0');
				} else {
					sum -= x[j + 1];
					s += '-';
					s += "" + (char)(x[j + 1] + '0');
				}
			}
			if(sum == 7) {
				s += '=';
				s += '7';
				System.out.println(s);
				return;
			}
		}
	}
}

ほぼyoutubeの解説動画で出てくるコードと同じなので、詳しくはそちらを参考にして下さい。

D問題
dfsでやるのかなと思って粘ってみましたがだめでした。ワーシャルフロイドで解けると聞いて、最初は「はっ？」ってなりました。
たしかにiからjに移るのに魔力cijが必要であることから、iとjを頂点, cijをコストとみなせば有名な最短路問題に帰結できますね。
これを思いつければあとはワーシャルフロイドを使って全てのiから1にするのに必要な魔力の最小値を求めて和を求めれば解けますね。

import java.util.Scanner;
 
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int h = sc.nextInt();
		int w = sc.nextInt();
		int[][] c = new int[10][10];
		int[][] A = new int[h][w];
		for(int i = 0 ; i < 10 ; i++) {
			for(int j = 0 ; j < 10 ; j++) {
				c[i][j] = sc.nextInt();
			}
		}
		for(int i = 0 ; i < h ; i++) {
			for(int j = 0 ; j < w ; j++) {
				A[i][j] = sc.nextInt();
			}
		}
		for(int k = 0 ; k < 10 ; k++) {
			for(int i = 0 ; i < 10 ; i++) {
				for(int j = 0 ; j < 10 ; j++) {
					c[i][j] = Math.min(c[i][j], c[i][k] + c[k][j]);
				}
			}
		}
		int ans = 0;
		for(int i = 0 ; i < h ; i++) {
			for(int j = 0 ; j < w ; j++) {
				if(A[i][j] >= 0) {
					ans += c[A[i][j]][1];
				}
			}
		}
		System.out.println(ans);
	}
}