読者です 読者をやめる 読者になる 読者になる

TopCoder SRM 516 Div1 Medium: RowsOrdering

問題

読解問題は無理なのでkmjp先生の訳を見た。

kmjp.hatenablog.jp

コード

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;

public class RowsOrdering {
	private final int MOD = (int) 1e9 + 7;

	public int order(String[] rows) {
		int H = rows.length;
		int M = rows[0].length();
		int[][] table = new int[H][M];

		// 各文字に各数字を割り当てる
		for (int h = 0; h < H; h++) {
			for (int row = 0; row < M; row++) {
				char c = rows[h].charAt(row);
				if ('a' <= c && c <= 'z') {
					table[h][row] = c - 'a' + 1;
				} else {
					table[h][row] = c - 'A' + 27;
				}
			}
		}

		// 各列ごとの各数字の登場回数をカウントしておく
		int[][] cnt = new int[51][M];
		for (int h = 0; h < H; h++) {
			for (int row = 0; row < M; row++) {
				cnt[table[h][row]][row]++;
			}
		}

		// 各列の文字に登場回数が小さい順に数字を割り当てたときの列内の和
		int[] rowSums = new int[M];
		for (int row = 0; row < M; row++) {
			ArrayList<Integer> rowCnts = new ArrayList<Integer>();
			for (int j = 0; j < 51; j++) {
				if (cnt[j][row] > 0) {
					rowCnts.add(cnt[j][row]);
				}
			}
			Collections.sort(rowCnts, Collections.reverseOrder());
			for (int j = 0; j < rowCnts.size(); j++) {
				rowSums[row] += rowCnts.get(j) * j;
			}
		}

		Arrays.sort(rowSums);
		long ans = 0;
		for (int row = 0; row < M; row++) {
			ans *= 50;
			ans += rowSums[row];
			ans %= MOD;
		}

		// 0000...0000を0番目として数えているが、実際には1番目なので、各数字の順位は1つずつ大きくなる。
		// よって合計でH大きくなる
		return (int) ans + H;
	}
}