TopCoder SRM 624 Div2 oox 1067->1147

60th, 734.91pts, +0/0 challenge
Volatility: 420->414

前回マイナスの点を取って久しぶりのDiv2。250と500を早解きして1000は解けず。
9回目のRoom Win。

250: CostOfDancing

与えられたリストから小さい順に\(K\)個選んで総和を出力するだけ

class CostOfDancing:
    def minimum(self, K, danceCost):
        danceCost = list(danceCost)
        danceCost.sort()
        return sum(danceCost[:K])

後から考えるとこっちの方がコード数が少なくてよかったような

class CostOfDancing:
    def minimum(self, K, danceCost):
        return sum(sorted(danceCost)[:K])

500: BuildingHeightsEasy

与えられたリストから\(M\)個要素を選んで、その中の最大の要素とその他の要素の差の総和が最小のものを答える
ソートしてから\(M\)ずつ見ていくだけ

class BuildingHeightsEasy:
    def minimum(self, M, heights):
        heights = list(heights)
        heights.sort(reverse=True)
        ret = 100000000000000000
        for i in xrange(len(heights) - M + 1):
            cost = heights[i] * M - sum(heights[i:i + M])
            ret = min(ret, cost)
        return ret

1000: GameOfSegments

\(N\)角形が与えられる。
二人のプレイヤーが交互に以下の2つの線を引く操作のうち最善のものをしたとき、交差せずに最後まで書けるのはどちらかを答える

• いずれかの辺の上に線を引く
• いずれかの対角線に線を引く

終わった後にPracticeで挑戦したけど結局解けなかった。
以下の2つを使っててきとーな動的計画法とかgrundy数とか試したけどうまくいかず(？)

• 辺の上に線を引く時は\(N\)角形を\(N-2\)角形にしていると考えてよい
• また対角線を引くときには、\(N\)角形を\(i\)角形と\(N - i - 2 \)角形に分けていると考えてよい

考え方が間違っているのかコードが間違っているのか問題文を誤読しているのか……

追記、コードが間違っていましたorz

grundy数をそのまま実装するだけで解けますね。
grundy数は、0以上の整数のうち次に到達できる状態のgrundy数に含まれない最小のものになります
今回みたいに途中で2つに別れるときにはそれらのXORを取ればいいみたいです。
負けの時は0になります

この系統の問題は蟻本の「4-2 ゲームの必勝法を編み出せ！」の項目がわかりやすいです

プログラミングコンテストチャレンジブック [第2版]　?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える?

class GameOfSegments:
    def winner(self, N):
        if N <= 4:
            return 1
        grundy = [0] * (N + 1)
        grundy[2] = 1
        grundy[3] = 1
        
        for i in xrange(4, N + 1):
            temp = []
            temp.append(grundy[i - 2])
            for j in xrange(3, i):
                a = j
                b = i - a + 2
                temp.append(grundy[a - 2] ^ grundy[b - 2])
            check = set(temp)
            for j in xrange(N + 2):
                if j not in check:
                    grundy[i] = j
                    break
        return 2 if grundy[N] == 0 else 1