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