[BOJ 2458]キー順(Javaプール)

質問する

1番からN番まで番号が貼られていた生徒について、2人の生徒の身長を比較し、結果の一部を得た.しかし、N人とも身長が異なると仮定する.例えば、6人の生徒に対して身長を6回しか比較しなかった結果、以下のようになった.

1番学生の身長<5番学生の身長

3番学生の身長<4番学生の身長

5番学生の身長<4番学生の身長

4番学生の身長<2番学生の身長

4番学生の身長<6番学生の身長

5番学生の身長<2番学生の身長

この比較結果から、すべての生徒の中で、一番背の小さい生徒から自分が何位であるかを知ることができ、以下のような図を描いて自分が何位であるかを簡単に確認することができる.a番学生の身長がb番学生の身長より小さい場合は、aからbまでの矢印で表します.

1番は5番より低く、5番は4番より低いので、1番は4番より低いです.では、1番、3番、5番はいずれも4番未満です.また、4番が2番と6番より小さいので、4番には自分より小さい学生が3人、自分より大きい学生が2人いて、自分の身長が何位なのか正確に知ることができます.しかし、4番以外の生徒たちは自分の身長がどれくらいなのか分からない.
学生の身長を比較するときは、自分の身長を知っている学生が何人いるかを計算し、プログラムを書いてください.

入力

第1行は、生徒数N(2≦N≦500)と2人の生徒の身長比較回数M(0≦M≦N(N−1)/2)を与える.次のM行は、2つの整数aおよびbを与え、2人の学生の身長を比較した結果を表す.これは、a番の学生がb番の学生より低いことを意味する.

しゅつりょく

自分の身長がどれくらい分かる学生が何人いるかを印刷します.

方法

floyd‐washallアルゴリズムを適用して解いてみましょう.
このアルゴリズムはO(n^3)の時間を必要とする.問題の要求から見ると,学生数はN(2<=N<=500)であるため,最悪の場合でも125000000回の演算が必要となる可能性があり,これは時間的に完全に可能である.

int型二重配列graphを作成しましょう.図中(i,j)は、iとjを比較すると、iがjより小さいと仮定することを指す.

floyd-グラフィック内のすべての値を大きな値に初期化してshallアルゴリズムと適用し、自身と比較する必要がないため、0に入れます.

入力した値に基づいて一方向図を記入します.(i,jは大きい場合と小さい場合が同時に存在しないため,一方向でなければならない.

floyd-とshallアルゴリズムを適用して接続図を生成します.リレーションシップ(a->b、b->c==a->c)を式化できるようになりました.

1番からn番(i->j,j->i)に移動し、いずれかの条件が満たされていることを確認します.すべての状況で満足している場合は、resultを1に上げるだけです.

ソースコード

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class HeightLevel {

    static int STANDARD = 100000;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = br.readLine().split(" ");
        int n = Integer.parseInt(input[0]);
        int m = Integer.parseInt(input[1]);
        int[][] graph = new int[n + 1][n + 1];
        int result = 0;

        for (int i = 0; i <= n; i++) {
            Arrays.fill(graph[i], STANDARD);
            graph[i][i] = 0;
        }

        for (int i = 0; i < m; i++) {
            input = br.readLine().split(" ");
            graph[Integer.parseInt(input[0])][Integer.parseInt(input[1])] = 1;
        }

        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= n; j++) {
                for (int k = 0; k <= n; k++) {
                    graph[j][k] = Math.min(graph[j][k], graph[j][i] + graph[i][k]);
                }
            }
        }

        for (int i = 1; i <= n; i++) {
            if (checkLevel(graph, i, n)) result++;
        }

        System.out.println(result);
        br.close();
    }

    public static boolean checkLevel(int[][] graph, int num, int n) {
        for (int i = 1; i <= n; i++) {
            if (graph[i][num] >= STANDARD && graph[num][i] >= STANDARD) {
                return false;
            }
        }
        return true;
    }
}

結果