ABC081_C Not so Diverse

mapの降順ソート(Value)

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Scanner;

public class MainC {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int k = sc.nextInt();
		int[] a = new int[n];
		for(int i = 0 ; i < n ; i++) a[i] = sc.nextInt();
		Map<Integer, Integer> map = new HashMap<>();
		for(int i = 0 ; i < n ; i++) {
			if(map.containsKey(a[i])) {
				map.put(a[i], map.get(a[i]) + 1);
			} else {
				map.put(a[i], 1);
			}
		}
		List<Entry<Integer, Integer>> entry = new ArrayList<>(map.entrySet());
		Collections.sort(entry, new Comparator<Entry<Integer, Integer>>() {
			public int compare(Entry<Integer, Integer> obj1, Entry<Integer, Integer> obj2) {
				return obj2.getValue() - obj1.getValue();
			}
		});
		int ans = 0;
		for(int i = k ; i < entry.size() ; i++) {
			ans += entry.get(i).getValue();
		}
		System.out.println(ans);
	}
}

No.570 3人兄弟（その１）オブジェクトの順序を変える方法

Pair.aで昇順にしたかったらcompare(Pair p1, Pair p2), return p1.a - p2.a
Pair.aで降順にしたかったらcompare(Pair p1, Pair p2), return p2.a - p1.a
にすれば良い

package yukicoder174;

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

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int a = sc.nextInt();
		int b = sc.nextInt();
		int c = sc.nextInt();
		Pair[] p = {new Pair(a, 'A'), new Pair(b, 'B'), new Pair(c, 'C')};
		Arrays.sort(p, new Comparator<Pair>() {
			public int compare(Pair p1, Pair p2) {
				return Integer.compare(p2.a, p1.a);
			}
		});
		for(int i = 0 ; i < 3 ; i++) {
			System.out.println(p[i].c);
		}
	}

	public static class Pair {
		int a; char c;
		public Pair(int a, char c) {
			this.a = a; this.c = c;
		}
	}

}

文字列を逆順にする

String s = "abcdef" => "fedcba"
にすることが目標です。
普通に配列用意してループ回して行けば作れます。

public static String reverse(String s, int N) {
		char[] S = s.toCharArray();
		char[] R = new char[N];
		for(int i = 0 ; i < N ; i++) {
			R[N - i - 1] = S[i];
		}
		return String.valueOf(R);
	}

より実装を簡単にしたければ

s = new StringBuilder(s).reverse().toString();

の一行で出来ます。

深さ優先探索

以下のサイトの初めの方の問題を実装しました
URL: https://www.slideshare.net/chokudai/wap-atcoder2

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int m = sc.nextInt();
		int n = sc.nextInt();
		int ans = dfs(m, n);
		System.out.println(ans);
	}

	// m 個のりんごを n 人で分ける方法は何通りあるか
	public static int dfs(int m, int n) {
		if(n == 1) return 1;
		int ret = 0;
		// ret += dfs(m, n - 1) + dfs(m - 1, n - 1) + ... + dfs(0, n - 1)
		for(int i = 0 ; i <= m ; i++) ret += dfs(m - i, n - 1);
		return ret;
	}
}

AtCoder Beginner Contest 089

C - March
入力で与えられた文字の頭が
M, A, R, C, H
のいづれかの場合、それぞれカウントする。
求めたいのは、頭文字がM, A, R, C, H の文字から3つ選ぶ方法の組み合わせの個数なので
３重ループで愚直に数えれば良い

import java.util.Scanner;

public class MainC {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		String[] s = new String[n];
		for(int i = 0 ; i < n ; i++) s[i] = sc.next();
		long[] cnt = new long[5];
		for(int i = 0 ; i < n ; i++) {
			if(s[i].charAt(0) == 'M') cnt[0]++;
			if(s[i].charAt(0) == 'A') cnt[1]++;
			if(s[i].charAt(0) == 'R') cnt[2]++;
			if(s[i].charAt(0) == 'C') cnt[3]++;
			if(s[i].charAt(0) == 'H') cnt[4]++;
		}
		long ans = 0;
		for(int i = 0 ; i < 5 ; i++) {
			for(int j = i + 1 ; j < 5 ; j++) {
				for(int k = j + 1 ; k < 5 ; k++) {
					ans += cnt[i] * cnt[j] * cnt[k];
				}
			}
		}
		System.out.println(ans);
	}
}

D - Practical Skill Test
累積和で求めるのですね。時間内に解けなかったです。
前にコンテストで似たような問題があったので、ワーシャルフロイドで解けるんじゃね？とか思ったが制約的にきついしそれ以前にそれで解けるのかが疑問。

最初、盤面の値がどの盤面に属するのかをメモする。
次に、累積和で値が D + 1 以降の魔力を求める。D以下の値はその時点で魔力が使われないのでゼロ。
最後に、クエリーごとにR[i] - L[i] を出力すれば良い。R[i] - L[i] はR[i]で使われている魔力からL[i]で使われている魔力を引いているので、L[i]-R[i] 間で使われた魔力に相当する。

import java.util.Scanner;

public class MainD {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int h = sc.nextInt();
		int w = sc.nextInt();
		int d = sc.nextInt();
		int[][] a = new int[h][w];
		for(int i = 0 ; i < h ; i++) {
			for(int j = 0 ; j < w ; j++) {
				a[i][j] = sc.nextInt();
			}
		}
		int q = sc.nextInt();
		int[] l = new int[q];
		int[] r = new int[q];
		for(int i = 0 ; i < q ; i++) {
			l[i] = sc.nextInt();
			r[i] = sc.nextInt();
		}
		// 値がどの盤面の値かをメモ
		long[] px = new long[h * w + 1];
		long[] py = new long[h * w + 1];
		for(int i = 0 ; i < h ; i++) {
			for(int j = 0 ; j < w ; j++) {
				int value = a[i][j];
				px[value] = i;
				py[value] = j;
			}
		}
		// 盤面上の各値それぞれに対する魔力の合計値を求める
		long[] ruisekiwa = new long[90001];
		for(int i = d + 1 ; i <= h * w ; i++) {
			ruisekiwa[i] = ruisekiwa[i - d] + Math.abs(px[i] - px[i - d]) + Math.abs(py[i] - py[i - d]);
		}
		for(int i = 0 ; i < q ; i++) {
			System.out.println(ruisekiwa[r[i]] - ruisekiwa[l[i]]);
		}
	}
}

深さ優先探索の練習

深さ優先探索の処理の流れがわかりやすくコーディングしてあるサイトを発見したので、忘備録のために書きます。
参考にしたサイトのURL：https://qiita.com/shki/items/cc9806564a2690e90fdb

import java.util.Scanner;

public class Main {

	static final int SIZE = 2;
	static int count = 0;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		dfs(0, 0, 0);
		System.out.println(String.format("全部で%d通り", count));
	}

	public static void dfs(int x, int y, int hosuu) {
		System.out.println(String.format("現在の状態(%d, %d) %d歩目", x, y, hosuu));
		if(x == 2 && y == 2) {
			count++;
			System.out.println(String.format("末端に到着(%d通り目)。一つ前の状態に戻る", count));
			return;
		}
		if(x < SIZE) {
			System.out.println("右へ移動する分岐へ(x + 1)");
			dfs(x + 1, y, hosuu + 1);
			System.out.println(String.format("戻ってきた：状態(%d, %d) %d歩目", x, y, hosuu));
		} else {
			System.out.println("これより右へ進めないため右方向への分岐は行わない");
		}
		if(y < SIZE) {
			System.out.println("下へ移動する分岐へ(y + 1)");
			dfs(x, y + 1, hosuu + 1);
			System.out.println(String.format("戻ってきた：状態(%d, %d) %d歩目", x, y, hosuu));
		} else {
			System.out.println("これより下へ進めないため下方向への分岐は行わない");
		}
		if(hosuu > 0) {
			System.out.println("一つ前の状態に戻る");
		} else {
			System.out.println("一つ前の状態に戻る");
		}
	}

}

CODE FESTIVAL 2017 Final

問題のURL
https://cf17-final-open.contest.atcoder.jp/assignments

A問題
文字列 S が与えられます。
高橋君はこの文字列の好きな位置に好きなだけ文字 A を挿入することができます。
S を AKIHABARA に変えることはできるでしょうか？

五重ループでゴリ押しして解きました。バグが消えなくて焦った汗
一番簡単な解法は正規表現で書く方法だと思います。

import java.util.Scanner;
 
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String s = sc.next();
		String x = "^A?KIHA?BA?RA?$";
		System.out.println(s.matches(x) ? "YES" : "NO");
	}
}

B問題
すぬけ君は a、b、c の 3 種類の文字のみからなる文字列 S を持っています。
回文恐怖症のすぬけ君は S の文字を自由に並び替えて、2 文字以上の回文を部分文字列として含まないようにしようと思いました。 これが可能かどうかを判定して下さい。

最後のケースがWAになり最後まで解ききることができなかった。まじで悔しい！
aaabbbcccccはacacacbcbcbになるから回分だと勘違いをしていました。普通にこの部分文字列は気分含んでるんですけどね...泣
コンテスト終了後に解きました。

import java.util.Scanner;
 
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String s = sc.next();
		int n = s.length();
		int[] a = new int[3];
		for(int i = 0 ; i < n ; i++) {
			if(s.charAt(i) == 'a') {
				a[0]++;
			} else if(s.charAt(i) == 'b') {
				a[1]++;
			} else if(s.charAt(i) == 'c') {
				a[2]++;
			}
 		}
		boolean ok = true;
		if(a[0] >= 1 && a[1] >= 1 && a[2] >= 1) {
			// 3種類
			if(Math.abs(a[0] - a[1]) >= 2 || Math.abs(a[0] - a[2]) >= 2 || Math.abs(a[1] - a[2]) >= 2) {
				ok = false;
			}
		} else if((a[0] == 0 && a[1] >= 1 && a[2] >= 1) || (a[0] >= 1 && a[1] == 0 && a[2] >= 1) || (a[0] >= 1 && a[1] >= 1 && a[2] == 0)) {
			// 2種類
			if(!(n == 2 && s.charAt(0) != s.charAt(1))) {
				ok = false;
			}
		} else if((a[0] == 0 && a[1] >= 0 && a[2] >= 1) || (a[0] >= 0 && a[1] == 1 && a[2] >= 0) || (a[0] >= 1 && a[1] >= 0 && a[2] == 0)) {
			// 1種類
			if(n != 1) {
				ok = false;
			}
		}
			if(ok == true) {
			System.out.println("YES");
		} else {
			System.out.println("NO");
		}
	}
}

でも最近コンテストで300点問題解けるようなってきたので成長してきたと信じたい。
ABC_Cがあと6問で全部解き終わるけど難しいやつしか残ってないからきつい。けど頑張って埋めるか。