pre{ white-space: pre; } .entry-content pre{ word-wrap: normal; }

重複ありの数列でも順列を返す関数

自分用のメモ
結局ネットにあったコードを使ったら出来たので、今後のために載せます。

参照URL:http://d.hatena.ne.jp/tomerun/20081203/1228321480

import java.util.Arrays;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int[] a = new int[n];
		for(int i = 0 ; i < n ; i++) {
			a[i] = sc.nextInt();
		}
		Arrays.sort(a);
		do {
			for(int i = 0 ; i < n ; i++) {
				System.out.print(a[i]);
			}
			System.out.println();
		} while(nextPermutation(a));
	}

	// nextPermutation
	public static boolean nextPermutation(int[] a) {
		for (int i = a.length - 1; i > 0; --i) {
			if (a[i - 1] < a[i]) {
				int swapIndex = find(a[i - 1], a, i, a.length - 1);
				int temp = a[swapIndex];
				a[swapIndex] = a[i - 1];
				a[i - 1] = temp;
				Arrays.sort(a, i, a.length);
				return true;
			}
		}
	    return false;
	}

	// destより大きい要素の中で最小のもののインデックスを二分探索で探す
	private static int find(int dest, int[] a, int s, int e) {
		if (s == e) {
			return s;
		}
		int m = (s + e + 1) / 2;
		return a[m] <= dest ? find(dest, a, s, m - 1) : find(dest, a, m, e);
	}
}

今の段階では内容を全くと行っていいほど理解していませんが、いつか理解していきたい(遠い目)
深さ優先探索でも実装できればしていきたいなあ。

重複のない数列の順列を返す関数

自分用のメモ
無駄なところがあると思いますが、初心者なので許してください。

import java.util.Scanner;

public class Main {

	static int n;
	static int[] c;
	static boolean[] used;
	static int[] perm;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();
		c = new int[n];
		for(int i = 0 ; i < n ; i++) c[i] = sc.nextInt();
		used = new boolean[n];
		perm = new int[n];
		dfs(0, n);
	}

	public static void dfs(int pos, int n) {
		if(pos == n) {
			for(int i = 0 ; i < n ; i++) {
				System.out.print(perm[i]);
			}
			System.out.println();
			return;
		}
		// permのpos番目をc[0]~c[n-1]のどれにするか
		for(int i = 0 ; i < n ; i++) {
			if(used[i] == false) {
				perm[pos] = c[i];
				// c[i]を使ったので、i番目は使ったというフラグを立てる
				used[i] = true;
				dfs(pos + 1, n);
				// 戻ってきたら、i番目のフラグを戻す
				used[i] = false;
			}
		}
		return;
	}

}

数列に重複する数字がある場合も深さ優先探索で実装したいが実力的にまだ時間が掛かりそう
実装できたら上げる予定

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);
	}
}

No.79 過小評価ダメ・ゼッタイ

最初はmapに突っ込んで、カウントの方針でAC通した。

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int[] l = new int[n];
		for(int i = 0 ; i < n ; i++) {
			l[i] = sc.nextInt();
		}
		Map<Integer, Integer> map = new HashMap<>();
		for(int i = 0 ; i < n ; i++) {
			map.put(l[i], 0);
		}
		for(int i = 0 ; i < n ; i++) {
			map.put(l[i], map.get(l[i]) + 1);
		}
		int max = -1001001001;
		int ans = 0;
		for(int key : map.keySet()) {
			if(max < map.get(key) || max == map.get(key) && ans < key) {
				ans = key;
				max = map.get(key);
			}
		}
		System.out.println(ans);
 	}
}

mapに突っ込まなくても、レベル：1 ~ 6の範囲で小さいから、配列に突っ込んでカウントしてもいいことも解答に乗ってたので、この方針でも解いてみた。

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int[] level = new int[7];
		for(int i = 0 ; i < n ; i++) {
			int temp = sc.nextInt();
			level[temp]++;
		}
		int ans = -1; int cnt = -1;
		for(int i = 1 ; i < 7 ; i++) {
			if(cnt <= level[i]) {
				cnt = level[i];
				ans = i;
			}
		}
		System.out.println(ans);
 	}
}

No.156 キャンディー・ボックス

最も少ない箱から一つづつキャンディーを取ってくればいいので、ソートして貪欲に取っていけばok

import java.util.Arrays;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int m = sc.nextInt();
		int[] c = new int[n];
		for(int i = 0 ; i < n ; i++) c[i] = sc.nextInt();
		Arrays.sort(c);
		int ans = 0;
		for(int i = 0 ; i < n ; i++) {
			m -= c[i];
			if(m >= 0) ans++;
		}
		System.out.println(ans);
 	}
}

yukicoder No.239 にゃんぱすー

列ごとに"nyanpass"を数えていき、ちょうど n - 1個 だけ"nyanpass"が存在することがわかれば、その時の列番号を返せばいい。
ただし、2列以上にn - 1 だけ"nyanpass"以上にすると特定することはできないので、その時は -1 を返す。

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		String[][] a = new String[n][n];
		for(int i = 0 ; i < n ; i++) {
			for(int j = 0 ; j < n ; j++) {
				a[i][j] = sc.next();
			}
		}
		int ret = 0; int cnt1 = 0;
		for(int i = 0 ; i < n ; i++) {
			int cnt2 = 0;
			for(int j = 0 ; j < n ; j++) {
				if(a[j][i].equals("nyanpass")) {
					cnt2++;
					if(cnt2 == n - 1) {
						cnt1++;
						ret = i + 1;
					}
				}
			}
		}
		if(cnt1 == 1) {
			System.out.println(ret);
		} else {
			System.out.println(-1);
		}
 	}
}

分からなかったから他の人のコード見たけど、a[j][i] みたいに i と j を逆にすれば列ごとに見れることを学べた。
ただ星1にしては難しかった気がする。

yukicoder No.279 木の数え上げ

文字列が与えられるので、部分文字列treeの個数を数える。

各t, r, e の文字の個数を数えて、min(t, min(r, e / 2))を出力すればいい

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String s = sc.next();
		int t = 0, r = 0, e = 0;
		for(int i = 0 ; i < s.length() ; i++) {
			if(s.charAt(i) == 't') {
				t++;
			} else if(s.charAt(i) == 'r') {
				r++;
			} else if(s.charAt(i) == 'e') {
				e++;
			}
		}
		System.out.println(Math.min(Math.min(t, r), e / 2));
	}
}