読者です 読者をやめる 読者になる 読者になる

唯物是真 @Scaled_Wurm

プログラミング(主にPython2.7)とか機械学習とか

TopCoder SRM 646 Div1 o-- 1284->1319

topcoder 競技プログラミング

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

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

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

600: TheGridDivOne

座標圧縮してダイクストラかと思ったけど、時間とやる気がなくて書けず。

-->