TopCoder SRM 330 DIV 2 Level One Sortness

5番目に易しい問題。カテゴリは初めての「Search」。正解率98.57%。

またもややってしまいました。「問題文を読まない」失敗。
というか、「読めなかった」んですけど(T-T)。

Example見て、ソートした後の位置と現在位置の距離の合計を出すのかと思った

でも、それだとExample0の「3,2,1」が全部「2」なのが説明できない(2は0のはず)

降順に並んでるときは前のときの距離を引き継ぐルール? ←勝手な俺ルール

でもそれだとExample3の計算合わないよなぁ……

という馬鹿。

Problem Statement

The sortness of a sequence of distinct numbers is the average of the sortness of each element. The sortness of an element is the number of higher elements that come before it in the sequence plus the number of lower elements that come after it in the sequence. The lower the sortness of a sequence, the closer it is to being sorted. Only a sorted sequence has a sortness of 0.

For example, in the sequence {3,2,1,4,6,7,5,8} the numbers 1,2,3 and 5 have a sortness of 2, numbers 6 and 7 have a sortness of 1 and numbers 4 and 8 have a sortness of 0. The sortness of the sequence is the average of all those sortness values: (2+2+2+2+1+1+0+0)/8 = 1.25.

You will be given a sequence of distinct numbers a as a int[]. Return the sortness of a.

要素のsortnessは、「要素の前にある要素の数字より大きな要素の数」と「要素の後にある要素の数字より小さな要素の数」の合計である。
と、書いてあるらしい。

using System;
using System.Collections;
using System.Collections.Generic;
using System.Text;

public class Sortness {
    public double getSortness(int[] a) {

        double sortness = 0.0;
        int score = 0;
        int score_total = 0;

        for (int i = 0; i < a.Length; i++)
        {
                for (int j = 0; j < i; j++)
                {
                        if ( a[i] < a[j] ) score++;
                }
                for (int j = i+1; j < a.Length; j++)
                {
                        if ( a[i] > a[j] ) score++;
                }
                //Console.WriteLine(score);
                score_total += score;
                score = 0;
        }
        sortness = 1.0 * score_total / a.Length;
        return sortness;
    }

    static void Main(string[] args)
    {
        Sortness obj = new Sortness();
        //int[] a = {3,2,1,4,6,7,5,8};
        //int[] a = {1,2,3};
        //int[] a = {5,4,3,2,1};
        int[] a = {1,5,8,7,9,6,10,12,11,3,4,2};

        Console.WriteLine(obj.getSortness(a));
    }
}

sortnessの合計とa.Lengthは両方Integerなので、そのまま割り算するとsortnessもIntegerになっちゃう……のかな?
よく分からないので、1.0を入れて回避してみた。
でも、Linuxのmonoの環境上だと、出力はExample1が0、Example2が4になって、0.0と4.0にならない。
TopCoderのサイト上ではちゃんと0.0と4.0になって、無事通過。

Sortness_103pts

スコアは103.51。逆算すると3871秒。1時間4分31秒(^^;
論外ですな。
平均正解時間は11分11秒とのこと。

でも、この問題のどこが「Search」なんだろうか?よく分からない。

カテゴリー: TopCoder パーマリンク

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です