TopCoder SRM 646 Div1 o-- 1284->1319

199th, 145.04pts, +0/-0 challenge
Volatility: 417->384

久しぶりの参加
めずらしくDiv1 Easyが解けて、4ヶ月以上ぶりに、Div1で正の点数をとってレートが上がった

SRM 646 - Togetterまとめ

250: TheConsecutiveIntegersDivOne

最大で47個の整数が与えられるので、そのうちから\(k\)個を選んで、連続した整数を作るのに必要な操作の回数を答える
1回の操作では、1つの数を\(\pm 1\)することができる

最大でも47個しかないので、ソートしてから、\(k\)個選んでどの数を固定して残りを連続にするかを全通り試しても間に合う
問題文にはdistinctってあるのに、同じ数が出るかと思ってコードを書いたりテストしたりして時間を無駄にしたorz

同じ数があっても動くようになっているコード

# -*- coding: utf-8 -*-
import math,string,itertools,fractions,heapq,collections,re,array,bisect

class TheConsecutiveIntegersDivOne:
    def find(self, numbers, k):
        if k == 1:
            return 0
        L = len(numbers)
        numbers = list(numbers)
        numbers.sort()
        result = 1e12
        for i in xrange(L - k + 1):
            mem = numbers[i:i+k]
            M = len(mem)
            for j in xrange(M):
                count = 0
                
                temp = mem[j]
                for l in xrange(j - 1, -1, -1):
                    if temp == mem[l]:
                        count += 1
                    elif temp > mem[l]:
                        count += abs(temp - mem[l]) - 1
                    else:
                        count += abs(temp - mem[l]) + 1
                    temp -= 1
                temp = mem[j]
                for l in xrange(j + 1, M):
                    if temp == mem[l]:
                        count += 1
                    elif temp < mem[l]:
                        count += abs(temp - mem[l]) - 1
                    else:
                        count += abs(temp - mem[l]) + 1
                    temp += 1
                if count < result:
                    result = count
        return result