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版] ?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える?
- 作者: 秋葉拓哉,岩田陽一,北川宜稔
- 出版社/メーカー: マイナビ
- 発売日: 2012/01/28
- メディア: 単行本(ソフトカバー)
- 購入: 25人 クリック: 473回
- この商品を含むブログ (32件) を見る
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