最終結果が出てから投稿しようかと思ったけど、まだまだかかりそうなので投稿。
マラソンマッチに1度は参加してみたいなーと思っていたのですが、今回やっと初参加しました。
目標は↓な感じです。
マラソンマッチに初submitした。53/82位、何も考えてないコードなのに意外とよかった……(初日) 半分より上にいきたいけど、ほとんどやる気が無いから無理だろうなぁ
一瞬100位以内に入れるかと思いましたが、途中で諦めました(´・ω・｀)
仮スコア
745996.78, 128位
300人以上いるので、一応半分より上にいけましたかね……？
問題の概要
2000ターンの間、雲から雪が降ってくる。
マス目に雪が残っているとターンごとに罰金がかかる。
そこで作業員を雇って雪を掃除させる。
作業員も毎ターンごとに賃金が必要になる。
作業員は1ターンに上下左右いずれかに一回移動することができ、作業員が雪のあるマスにいるとその場所の雪は掃除される。
一度雇った作業員は解雇できない。
アプローチ
作業員をばらつかせる
どこに雪が降ってもいいように作業員をばらつかせる。
一番近い作業員の反対側に移動するようにした
壁や角の辺りに作業員がいる状態になっていたので、無駄になっていたかも。
雪の掃除
基本的に作業員を一番近い雪に向かわせる。
同じ雪に複数の作業員が向かわないように制限。
また雪が遠い場合には一定確率で近づかないようにした。
作業員数の制限
基本的にはあまり作業員を増やしすぎないようにした方がいい。
他の作業員から一定距離以上離れた場所に雪が降ったら作業員を増やすようにした。
この距離は罰金と賃金のバランスや、ステージの広さによって調整。
TLE？
Pythonで書いているせいか、非常に簡単なアルゴリズムを書いているのにTLEしていそうなことに気づきました。
この時点で100位ギリギリぐらいだったため、C++やJavaで書きなおすほどの気力はありませんでした。
諦めて作業員の最大数を減らして対処しました。
するとスコアが上がったのでおそらくTLEしていたのだと思います(？)。
結局作業員の最大数を35にしたのですが、実際の最大値が100であることを考えるとどんだけ遅いんだろうって感じです……。
制限時間が20秒で作業員を100まで出した時の手元の実行時間が十数秒だったのですが、マラソンマッチの本番だとどれぐらいでTLEするんでしょうね？
雲の予測
何もしなかった
パーティクルフィルタという単語がなぜか頭に浮かんだものの、触ったことがないし使えるかどうかもよくわからなかったので手を出さず。
反省点
- フィールドの角の辺りに作業員を配置していたのが無駄だった気がする。
- 作業員のばらつかせ具合がよくなかった
- 古い雪から掃除したほうがよかったかも
- 作業員を一番近い雪に貪欲に向かわせるだけなのが悪かった？
- 先の何ターンか分の移動を読むとか、巡回セールスマンとか最小費用流(2分マッチング)とか頭に浮かんだけど、どうすればいいのかいまいちよくわからず……
- 雲の予測をすべきだった？
- Pythonでやってる人ほとんどいなかった(´・ω・｀)
- やっぱり遅いからですかね？
他の方々のアプローチ
Forumで一位の人とかのアプローチが公開されているので見ると勉強になります。
ソースコード
import sys import random import math class SnowCleaning(object): def init(self, boardSize, salary, snowFine): self.boardSize = boardSize self.salary = salary self.snowFine = snowFine self.clean = [] self.count = 0 self.cover = set() self.turn = 0 self.neighbor = {} self.totalSalary = 0 self.totalSnowFine = 0 self.largeFine = False return 0 def nextDay(self, snowFalls): self.turn += 1 if self.salary / float(self.snowFine) <= 1 / 5.0: MD = 5 elif self.salary / float(self.snowFine) <= 1 / 2.5: MD = 6 elif self.salary / float(self.snowFine) <= 1 / 2.0: MD = 6 elif self.salary / float(self.snowFine) >= 3: MD = 25#20 elif self.salary / float(self.snowFine) >= 2: MD = 15 elif self.salary / float(self.snowFine) >= 1.5: MD = 12 else: MD = 8 if self.boardSize > 40: MD += 2 if self.turn >= 500 and self.totalSnowFine * 0.8 <= self.totalSalary: self.largeFine = True candidate = [] for j in xrange(len(self.clean)): temp = [] x, y = self.clean[j] for k in self.cover: t_x, t_y = k sq = abs(t_x - x) + abs(t_y - y) temp.append((sq, (x, y), (t_x, t_y))) temp.sort() candidate += temp[:5] used_s = set() used_e = set() result = {} temp = -1 candidate.sort() for j in candidate: sq, (x, y), (t_x, t_y) = j if sq >= temp and (x, y) not in used_s and (t_x, t_y) not in used_e: temp = sq t_list = result.get((x, y), []) for k in candidate: in_sq, (in_x, in_y), (in_t_x, in_t_y) = k if in_sq == sq and in_x == x and in_y == y and (in_t_x, in_t_y) not in used_e: t_list.append((in_t_x, in_t_y)) used_s.add((in_x, in_y)) used_e.add((in_t_x, in_t_y)) result[(x, y)] = t_list todo = [] for j in xrange(len(self.clean)): cand = [] x, y = self.clean[j] if len(result.get((x, y), [])) > 0: min_dist = abs(result[(x, y)][0][0] - x) + abs(result[(x, y)][0][1] - y) else: min_dist = 100000000 nearest = result.get((x, y), []) if min_dist != 100000000 and len(nearest) > 0 and min_dist > 0.00001: min_neighbor = 100000000 min_x = -1 min_y = -1 if sq <= 1: for t_x, t_y in nearest: if min_neighbor > self.neighbor.get((t_x, t_y), 0): min_neighbor = self.neighbor.get((t_x, t_y), 0) for t_x, t_y in nearest: if min_neighbor == self.neighbor.get((t_x, t_y), 0): if t_y > y: cand.append('R') if t_y < y: cand.append('L') if t_x > x: cand.append('D') if t_x < x: cand.append('U') else: for t_x, t_y in nearest: if t_y > y: cand.append('R') if t_y < y: cand.append('L') if t_x > x: cand.append('D') if t_x < x: cand.append('U') if (random.random() >= 0.8 and min_dist > MD - 1) or len(cand) == 0: cand = [] nearest = [] min_dist = 10000000000 possible = [] for k in xrange(len(self.clean)): t_x, t_y = self.clean[k] if t_x == x and t_y == y: continue for t_x, t_y in possible: sq = abs(t_x - x) + abs(t_y - y) if min_dist > sq: min_dist = sq nearest = [] if min_dist >= sq: nearest.append((t_x, t_y)) if len(nearest) > 0: for t_x, t_y in nearest: if t_x < x and x < self.boardSize - 1: cand.append('D') if t_x > x and x > 0: cand.append('U') if t_y < y and y < self.boardSize - 1: cand.append('R') if t_y > y and y > 0: cand.append('L') if len(cand) == 0: if y > 0: cand.append('L') if y < self.boardSize - 1: cand.append('R') if x > 0: cand.append('U') if x < self.boardSize - 1: cand.append('D') next = random.choice(cand) todo.append('M %d %s' % (j, next)) if next == 'L': self.clean[j] = (x, y - 1) if next == 'R': self.clean[j] = (x, y + 1) if next == 'U': self.clean[j] = (x - 1, y) if next == 'D': self.clean[j] = (x + 1, y) if self.clean[j] in self.cover: self.cover.remove(self.clean[j]) for d_x, d_y in [(0, 1), (0, -1), (1, 0), (-1, 0)]: d_key = (self.clean[j][0] + d_x, self.clean[j][1] + d_y) self.neighbor[d_key] = self.neighbor.get(d_key, 0) - 1 for j in xrange(len(snowFalls) / 2): x = int(snowFalls[j * 2]) y = int(snowFalls[j * 2 + 1]) key = (x, y) if key not in self.cover: self.cover.add(key) for d_x, d_y in [(0, 1), (0, -1), (1, 0), (-1, 0)]: d_key = (key[0] + d_x, key[1] + d_y) self.neighbor[d_key] = self.neighbor.get(d_key, 0) + 1 min_dist = 100000000000 for j in xrange(len(self.clean)): t_x, t_y = self.clean[j] sq = abs(t_x - x) + abs(t_y - y) if min_dist > sq: min_dist = sq if key not in self.clean and self.count < 35 and min_dist > MD and key: self.cover.remove(key) for d_x, d_y in [(0, 1), (0, -1), (1, 0), (-1, 0)]: d_key = (key[0] + d_x, key[1] + d_y) self.neighbor[d_key] = self.neighbor.get(d_key, 0) - 1 self.clean.append(key) todo.append('H %d %d' % key) self.count += 1 if self.turn == 2000 and self.count < 100 and self.salary < self.snowFine: for x, y in self.cover: key = (x, y) if self.count >= 100: break self.clean.append(key) todo.append('H %d %d' % key) self.count += 1 self.totalSalary += self.salary * len(self.clean) self.totalSnowFine += self.snowFine * len(self.cover) return todo if __name__ == '__main__': SC = SnowCleaning() boardSize = int(raw_input()) salary = int(raw_input()) snowFine = int(raw_input()) SC.init(boardSize, salary, snowFine) for i in xrange(2000): snowCnt = int(raw_input()) snowFalls = [] for j in xrange(2 * snowCnt): x = int(raw_input()) snowFalls.append(x) result = SC.nextDay(snowFalls) print len(result) for line in result: print line sys.stdout.flush()
