GoogleCodeJam2012 1B A "Safety in Numbers"

問題: https://code.google.com/codejam/contest/1836486/dashboard#s=p0

最低点の人が複数入れば最低点の人がeliminatedされないということだったので２人以上で同じ最低点になるように計算してった．

import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;
import java.io.File;

public class A {
  public static void main(String[] args) throws Exception {
    Scanner s = new Scanner(new File("A-large.in"));
    for (int t = 1, T = s.nextInt(); t <= T; ++t) {
      int n = s.nextInt();
      int a[][] = new int[n][2], x = 0;
      for (int i = 0; i < n; ++i) {
        a[i][0] = i;
        x += a[i][1] = s.nextInt();
      }
      Arrays.sort(a, new Comparator<int[]>() {
        @Override
        public int compare(int[] o1, int[] o2) {
          return o1[1] - o2[1];
        }
      });
      int m = 2;
      while (m < n) {
        double sum = x;
        for (int i = 0; i < m; ++i) {
          sum += a[i][1];
        }
        if (sum / m <= a[m][1]) {
          break;
        }
        ++m;
      }
      double sum = x;
      for (int i = 0; i < m; ++i) {
        sum += a[i][1];
      }
      double[] y = new double[n];
      for (int i = 0; i < m; ++i) {
        y[a[i][0]] = 100 * (sum / m - a[i][1]) / x;
      }
      String result = "Case #" + t + ": ";
      for (double Y : y) {
        result += String.format("%.5f ", Y);
      }
      System.out.println(result.trim());
    }
  }
}

追記

ついでにGoでも書いてみた．中身はJavaのやつと一緒．

package main

import (
	"fmt"
	"github.com/nise-nabe/fastio"
	"os"
	"sort"
	"strings"
)

type Pair struct {
	Index int
	Value float64
}

type Pairs []*Pair

func (p Pairs) Len() int {
	return len(p)
}

func (p Pairs) Swap(i, j int) {
	p[i], p[j] = p[j], p[i]
}

func (p Pairs) Less(i, j int) bool {
	if p[i].Value == p[j].Value {
		return p[i].Index < p[j].Index
	}
	return p[i].Value < p[j].Value
}

func main() {
	s := fastio.NewInOut(os.Stdin, os.Stdout)
	for t, T := 1, s.Next(); t <= T; t++ {
		n := s.Next()
		a, x := Pairs{}, 0.
		for i := 0; i < n; i++ {
			a = append(a, &Pair{i, float64(s.Next())})
			x += a[i].Value
		}
		sort.Sort(a)
		m, sum := 2, 0.
		for m < n {
			sum = x
			for i := 0; i < m; i++ {
				sum += a[i].Value
			}
			if sum/float64(m) <= a[m].Value {
				break
			}
			m++
		}
		sum = x
		for i := 0; i < m; i++ {
			sum += a[i].Value
		}
		y := make([]float64, n)
		for i := 0; i < m; i++ {
			y[a[i].Index] = 100. * (sum/float64(m) - a[i].Value) / x
		}

		result := make([]string, n)
		for i, v := range y {
			result[i] = fmt.Sprintf("%.5f", v)
		}
		s.Println("Case #", t, ": ", strings.Join(result, " "))
	}
	s.Flush()
}