Submission #1174793
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 int, loopCnt uint) {
// グローバル変数の初期化
// _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 = 4
endTemp = 0
R = 10000
startTime := time.Now()
T := 9990 * 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(9991 * 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 = loopCnt % 50
selectedColumn := currentStage[i]
for _, j = range dotList[i] {
currentMark := currentStage[i][j]
m = xorshift() % 256
nextMark = currentMark
if m < 5 {
nextMark = _minus
} else if m < 25 {
nextMark = _plus
} else {
nextMark = _dot
}
if nextMark != currentMark {
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
if loopCnt%1024 == 0 {
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
Submission Time |
|
Task |
A - ○×ブロック |
User |
fmhr |
Language |
Go (1.6) |
Score |
6958 |
Code Size |
5845 Byte |
Status |
AC |
Exec Time |
10000 ms |
Memory |
9108 KB |
Judge Result
Set Name |
test_01 |
test_02 |
test_03 |
test_04 |
test_05 |
test_06 |
test_07 |
test_08 |
test_09 |
test_10 |
Score / Max Score |
627 / 2500 |
717 / 2500 |
719 / 2500 |
734 / 2500 |
726 / 2500 |
694 / 2500 |
704 / 2500 |
647 / 2500 |
681 / 2500 |
709 / 2500 |
Status |
|
|
|
|
|
|
|
|
|
|
Set Name |
Test Cases |
test_01 |
subtask_01_01.txt |
test_02 |
subtask_01_02.txt |
test_03 |
subtask_01_03.txt |
test_04 |
subtask_01_04.txt |
test_05 |
subtask_01_05.txt |
test_06 |
subtask_01_06.txt |
test_07 |
subtask_01_07.txt |
test_08 |
subtask_01_08.txt |
test_09 |
subtask_01_09.txt |
test_10 |
subtask_01_10.txt |
Case Name |
Status |
Exec Time |
Memory |
subtask_01_01.txt |
AC |
10000 ms |
7088 KB |
subtask_01_02.txt |
AC |
10000 ms |
6912 KB |
subtask_01_03.txt |
AC |
10000 ms |
6912 KB |
subtask_01_04.txt |
AC |
10000 ms |
6912 KB |
subtask_01_05.txt |
AC |
10000 ms |
6784 KB |
subtask_01_06.txt |
AC |
10000 ms |
6912 KB |
subtask_01_07.txt |
AC |
10000 ms |
6912 KB |
subtask_01_08.txt |
AC |
10000 ms |
6912 KB |
subtask_01_09.txt |
AC |
10000 ms |
9108 KB |
subtask_01_10.txt |
AC |
10000 ms |
6912 KB |