Submission #1172751

---

Source Code Expand

package main

import (
	"fmt"
	"io"
	"log"
	"math"
	"os"
	"time"
)

var canChange [50][50]bool
var dotList [50][]int
var dotCount int

func init() {
	log.SetFlags(log.Lshortfile)
}

func main() {
	// defer profile.Start().Stop()
	solve(os.Stdin, os.Stdout)
}

var (
	_O     uint8
	_X     uint8 = 1
	_dot   uint8 = 2
	_plus  uint8 = 3
	_minus uint8 = 4
	_non   uint8 = 5
)

func solve(in io.Reader, out io.Writer) (bestScoreLast, loopCnt int) {
	// グローバル変数の初期化
	// _test.go でなんども回すときに必要
	for i, c := range canChange {
		for j := range c {
			canChange[i][j] = false
		}
	}
	for i := range dotList {
		dotList[i] = make([]int, 0, 50)
	}
	dotCount = 0
	//////
	// 時間を無制限にして探索するときに使う
	// c := make(chan os.Signal, 2)
	// signal.Notify(c, os.Interrupt, syscall.SIGTERM)
	// go func() {
	// 	<-c
	// 	ansPrint(ansLast)
	// 	os.Exit(1)
	// }()
	///////
	var stage field
	stage.input(in)
	/// zhash 初期化
	zhashCheck := make(map[uint]struct{})
	var z, nz uint
	var zhashSeed [50][50][5]uint
	for i := 0; i < 50; i++ {
		for j := 0; j < 50; j++ {
			for k := 0; k < 5; k++ {
				zhashSeed[i][j][k] = uint(xorshift())
				z += zhashSeed[i][j][k]
			}
		}
	}
	// 初期状態
	currentStage := stage
	currentDropStage := stage.drop()
	currentScore := score(stage.drop())
	// stage.drop().print(out)
	// SA 初期設定
	var startTemp, endTemp, temp, probability, R float64
	var forceNext bool
	startTemp = 10
	endTemp = 1
	R = 10000
	startTime := time.Now()
	T := 9900 * time.Millisecond
	// stage.print(out)
	// log.Println("")
	// stage.drop().print(out)
	// log.Print(bestScore)
	bestScoreLast = currentScore
	ans := stage
	ansLast := ans
	timeout := false
	go func() {
		time.Sleep(9950 * time.Millisecond)
		timeout = true
	}()
	continueCnt := 0
	var i, m uint
	var j, nextScore int
	var nextMark uint8
	var tmpColumn column
	var t time.Duration
	var ok bool
	for {
		if timeout {
			break
		}
		nz = z
		// i = xorshift() % 50
		i = uint(loopCnt % 50)
		selectedColumn := currentStage[i]
		for _, j = range dotList[i] {
			currentMark := currentStage[i][j]
			m = xorshift() % 100
			nextMark = currentMark
			if m < 2 {
				nextMark = _minus
			} else if m < 10 {
				nextMark = _plus
			} else {
				nextMark = _dot
			}
			selectedColumn[j] = nextMark
			nz -= zhashSeed[i][j][currentMark]
			nz += zhashSeed[i][j][nextMark]
		}
		_, ok = zhashCheck[nz]
		if !ok {
			zhashCheck[nz] = struct{}{}
		} else {
			continueCnt++
			continue
		}
		tmpColumn = currentDropStage[i]
		currentDropStage[i] = selectedColumn.drop()
		nextScore = score(currentDropStage)
		// SA
		t = time.Now().Sub(startTime)
		temp = startTemp + (endTemp-startTemp)*(float64(t.Nanoseconds())/float64(T.Nanoseconds()))
		probability = math.Exp(float64(nextScore-currentScore) / temp)
		forceNext = probability > float64(float64(xorshift()%uint(R)))/R
		// forceNext = false // ここをつかうと山登り法になる
		// log.Println(temp, s, bestScore, probability, forceNext)
		if nextScore >= currentScore || (forceNext) {
			currentStage[i] = selectedColumn
			currentScore = nextScore
			z = nz
			if nextScore > bestScoreLast {
				bestScoreLast = nextScore
				ansLast = currentStage
			}
		} else {
			currentDropStage[i] = tmpColumn
		}
		loopCnt++
	}
	ansLast.print(out)
	return
}

func (s *field) input(in io.Reader) {
	var S string
	for j := 49; j > -1; j-- {
		fmt.Fscan(in, &S)
		for i := 0; i < 50; i++ {
			switch S[i] {
			case 'o':
				s[i][j] = _O
			case 'x':
				s[i][j] = _X
			case '.':
				s[i][j] = _dot
				canChange[i][j] = true
				dotList[i] = append(dotList[i], j)
				dotCount++
			}
		}
	}
}

func (s field) print(out io.Writer) {
	int2string := [...]string{"o", "x", ".", "+", "-", "_"}
	for j := 49; j > -1; j-- {
		for i := 0; i < 50; i++ {
			fmt.Fprint(out, int2string[s[i][j]])
		}
		fmt.Fprintln(out, "")
	}
}

type point struct {
	i, j int
}

var di = [4]int{1, 0, -1, 0}
var dj = [4]int{0, 1, 0, -1}
var nextPoints []point

func score(n field) int {
	var done [50][50]bool
	var sk [2]int
	for i := 0; i < 50; i++ {
		for j := 0; j < 50; j++ {
			if !done[i][j] {
				k := n[i][j]
				if k <= 1 {
					s := 0
					nextPoints = append(nextPoints, point{i: i, j: j})
					for len(nextPoints) != 0 {
						s++
						p := nextPoints[len(nextPoints)-1]
						nextPoints = nextPoints[:len(nextPoints)-1]
						for l := 0; l < 4; l++ {
							ni := p.i + di[l]
							nj := p.j + dj[l]
							if ni > -1 && nj > -1 && ni < 50 && nj < 50 &&
								!done[ni][nj] && n[ni][nj] == k {
								done[ni][nj] = true
								nextPoints = append(nextPoints, point{i: ni, j: nj})
							}
						}
					}
					if s > sk[k] {
						sk[k] = s
					}
				}
			}
		}
	}
	return sk[0] + sk[1]
}

type column [50]uint8
type field [50]column

func (s field) drop() (r field) {
	for i := 0; i < 50; i++ {
		r[i] = s[i].drop()
	}
	return r
}

func (c column) drop() (r column) {
	for i, b := range c {
		r[i] = b
	}
	for {
		flag := false
		for i := 0; i < len(c); i++ {
			if r[i] == _dot {
				if i+1 == len(c) {
					r[i] = _non
				} else if r[i+1] == _minus {
					r[i] = _non
				} else {
					r[i], r[i+1] = r[i+1], r[i]
				}
				flag = true
			}
		}
		if !flag {
			break
		}
	}
	return
}

var (
	x uint32 = 123456789
	y uint32 = 362436069
	z uint32 = 521288629
	w uint32 = 88675123
	t uint32
)

func xorshift() uint {
	t = x ^ (x << 11)
	x = y
	y = z
	z = w
	w = w ^ (w >> 19) ^ (t ^ (t >> 8))
	return uint(w)
}

Submission Info

Judge Result