プログラマ-失敗率



スーパーゲーム開発者のオレリーは大きな悩みに陥った.彼女が作ったブランド「呉天成」は大きな成功を収めたが、最近は新しいユーザーの数が激減している.なぜなら、新しいユーザーと既存のユーザーの間の舞台の違いが大きすぎるからです.
どうすればいいか悩んだ彼女は、ゲームの時間を動的に増やして難易度を調整することにした.やはりスーパー開発者であり、ほとんどのロジックは実現しやすいが、失敗率を探す部分で危機に陥っている.オレリーの失敗率を求めるコードを完了します.
失敗率は次のように定義されます.
ステージに到着しても空になっていないプレイヤー数/ステージに到着したプレイヤー数
現在停止しているステージ番号を含む配列フェーズをパラメータとして指定した場合は、失敗率の高いステージからステージ番号を含む配列を降順に返すように、ソルバを完了します.

せいげんじょうけん


舞台の個数Nは1以上500以下の自然数である.
ステージの長さは1以上200000以下です.
ステージは、1以上N+1以下の自然数を含む.
各自然数は、ユーザが現在挑戦しているステージの番号を表します.
ただし、N+1は、最後のステージ(N番目のステージ)にクリアしたユーザを表す.
同じ失敗率の舞台があれば、トランペットの舞台を先に来てもらうことができます.
ステージに到着したプレイヤーがいない場合、そのステージの失敗率は0と定義されます.

I/O例


N stages result
5 [2, 1, 2, 6, 2, 4, 3, 3][3,4,2,1,5]
4 [4,4,4,4,4][4,1,2,3]

I/O例説明


I/O例#1
1番ステージには8人のユーザーが挑戦し、そのうち1人のユーザーはまだ通関していない.そのため、1番ステージの失敗率は以下の通り.
1ステージ失敗率:1/8
第2ステージには7人のユーザーが挑戦し、そのうち3人のユーザーはまだ通関していない.そのため、2番目の舞台の失敗率は以下の通りです.
フェーズ2失敗率:3/7
同様に、残りの舞台の失敗率は以下の通りである.
フェーズ3失敗率:2/4
フェーズ4失敗率:1/2
フェーズ5失敗率:0/1
各ステージの番号を失敗率の降順に並べます.
[3,4,2,1,5]
I/O例#2
すべてのユーザが最後のステージにいるため、4番目のステージの失敗率は1であり、残りのステージの失敗率は0である.
[4,1,2,3]

Solution


Java

import java.util.*;

class Solution {
    public int[] solution(int N, int[] stages) {
        class Pair implements Comparable<Pair> {
            public double fail;
            public int index;

            public Pair(double fail, int index) {
                this.fail = fail;
                this.index = index;
            }
            @Override
            public int compareTo(Pair pair) {
                if (this.fail < pair.fail) {
                    return 1;
                } else if (this.fail == pair.fail) {
                    return 0;
                } else {
                    return -1;
                }
            }
        }
        double[] fail = new double[N];
        int[] on_stages = new int[N];
        int[] pass_stages = new int[N];
        Arrays.fill(on_stages, 0);
        Arrays.fill(pass_stages, 0);
        for (int i = 0; i < stages.length; i++) {
            if (stages[i] == N + 1) {
                for (int j = 0; j < N; j++) {
                    pass_stages[j]++;
                }
                continue;
            }
            on_stages[stages[i] - 1]++;
            for (int j = 0; j < stages[i]; j++) {
                pass_stages[j]++;
            }
        }
        for (int i = 0; i < N; i++) {
            if (pass_stages[i] == 0) {
                fail[i] = 0;
                continue;
            }
            fail[i] = ((on_stages[i] * 1.0) / pass_stages[i]);
        }
        Pair[] failure = new Pair[N];
        for (int i = 0; i < N; i++) {
            failure[i] = new Pair(fail[i],i);
        }
        Arrays.sort(failure);
        int[] answer = new int[N];
        for (int i = 0; i < N; i++) {
            answer[i] = failure[i].index+1;
        }
        return answer;
    }
}
Compabiledの問題を理解します.もっときれいに絞れそうな気がします