結果
| 問題 | No.421 しろくろチョコレート |
| ユーザー |
 jugemjugemjugem
|
| 提出日時 | 2016-10-19 01:53:05 |
| 言語 | Go (1.22.1) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 7,312 bytes |
| コンパイル時間 | 14,029 ms |
| コンパイル使用メモリ | 234,872 KB |
| 実行使用メモリ | 29,604 KB |
| 最終ジャッジ日時 | 2024-05-02 04:29:49 |
| 合計ジャッジ時間 | 20,971 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge4 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | TLE | - |
| testcase_01 | -- | - |
| testcase_02 | -- | - |
| testcase_03 | -- | - |
| testcase_04 | -- | - |
| testcase_05 | -- | - |
| testcase_06 | -- | - |
| testcase_07 | -- | - |
| testcase_08 | -- | - |
| testcase_09 | -- | - |
| testcase_10 | -- | - |
| testcase_11 | -- | - |
| testcase_12 | -- | - |
| testcase_13 | -- | - |
| testcase_14 | -- | - |
| testcase_15 | -- | - |
| testcase_16 | -- | - |
| testcase_17 | -- | - |
| testcase_18 | -- | - |
| testcase_19 | -- | - |
| testcase_20 | -- | - |
| testcase_21 | -- | - |
| testcase_22 | -- | - |
| testcase_23 | -- | - |
| testcase_24 | -- | - |
| testcase_25 | -- | - |
| testcase_26 | -- | - |
| testcase_27 | -- | - |
| testcase_28 | -- | - |
| testcase_29 | -- | - |
| testcase_30 | -- | - |
| testcase_31 | -- | - |
| testcase_32 | -- | - |
| testcase_33 | -- | - |
| testcase_34 | -- | - |
| testcase_35 | -- | - |
| testcase_36 | -- | - |
| testcase_37 | -- | - |
| testcase_38 | -- | - |
| testcase_39 | -- | - |
| testcase_40 | -- | - |
| testcase_41 | -- | - |
| testcase_42 | -- | - |
| testcase_43 | -- | - |
| testcase_44 | -- | - |
| testcase_45 | -- | - |
| testcase_46 | -- | - |
| testcase_47 | -- | - |
| testcase_48 | -- | - |
| testcase_49 | -- | - |
| testcase_50 | -- | - |
| testcase_51 | -- | - |
| testcase_52 | -- | - |
| testcase_53 | -- | - |
| testcase_54 | -- | - |
| testcase_55 | -- | - |
| testcase_56 | -- | - |
| testcase_57 | -- | - |
| testcase_58 | -- | - |
| testcase_59 | -- | - |
| testcase_60 | -- | - |
| testcase_61 | -- | - |
| testcase_62 | -- | - |
| testcase_63 | -- | - |
| testcase_64 | -- | - |
ソースコード
package main
import (
"bufio"
"fmt"
"os"
)
type Choco struct {
lineMax int
colMax int
board [][]string
}
func MakeChoco(lineMax int, colMax int) *Choco {
board := make([][]string, lineMax)
for i := 0; i < lineMax; i++ {
board[i] = make([]string, colMax)
}
return &Choco{lineMax, colMax, board}
}
func (this *Choco) Load(stream *os.File) {
sc := bufio.NewScanner(stream)
for i := 0; i < this.lineMax; i++ {
if sc.Scan() {
s := sc.Text()
for j := 0; j < this.colMax; j++ {
this.board[i][j] = string(s[j])
}
}
}
}
func (this *Choco) Disp() {
fmt.Printf("data size %d %d\n", this.lineMax, this.colMax)
for i := 0; i < this.lineMax; i++ {
for j := 0; j < this.colMax; j++ {
fmt.Printf("%d", this.board[i][j])
}
fmt.Printf("\n")
}
}
func (this *Choco) IsNg(pos *Pos, other *Pos) bool {
// fmt.Printf("check\n")
// this.Disp()
// fmt.Println(this.board[pos.l][pos.c] == ".")
// fmt.Println(this.board[pos.l][pos.c] == this.board[other.l][other.c])
return this.IsNgPos(pos) || this.board[pos.l][pos.c] == this.board[other.l][other.c]
}
func (this *Choco) IsNgPos(pos *Pos) bool {
return this.board[pos.l][pos.c] == "."
}
func (this *Choco) CalcScore(lhs *Pos, rhs *Pos) int {
if lhs.l == rhs.l && lhs.c == rhs.c-1 {
return 100
}
if lhs.c == rhs.c && lhs.l == rhs.l-1 {
return 100
}
if this.board[lhs.l][lhs.c] != this.board[rhs.l][rhs.c] {
return 10
}
fmt.Print("this block expect never call.")
os.Exit(1)
return -1
}
func (this *Choco) Put(pos *Pos) {
this.board[pos.l][pos.c] = "."
}
func (this *Choco) Clone() Choco {
choco := MakeChoco(this.lineMax, this.colMax)
for i := 0; i < this.lineMax; i++ {
for j := 0; j < this.colMax; j++ {
choco.board[i][j] = this.board[i][j]
}
}
return *choco
}
type Pos struct {
l int
c int
}
func MakePos(seq *Seq, choco Choco) *Pos {
l := seq.index / choco.colMax
c := seq.index % choco.colMax
return &Pos{l, c}
}
func (this *Pos) Disp() {
fmt.Printf("%d %d", this.l, this.c)
}
type Seq struct {
index int
}
func MakeSeq(index int) *Seq {
return &Seq{index}
}
func (this *Seq) Disp() {
fmt.Printf("%d", this.index)
}
func (this *Seq) GetPos(choco Choco) *Pos {
return MakePos(this, choco)
}
func (this *Seq) IsOver(choco Choco) bool {
return this.index >= choco.colMax*choco.lineMax
}
func (this *Seq) IsNg(now *Seq, choco Choco) bool {
// fmt.Println(*this)
// fmt.Println(*now)
return choco.IsNg(this.GetPos(choco), now.GetPos(choco))
}
func (this *Seq) IsNgPos(choco Choco) bool {
return choco.IsNgPos(this.GetPos(choco))
}
func (this *Seq) NextIndex() *Seq {
return MakeSeq(this.index + 1)
}
func (this *Seq) CalcScore(other *Seq, choco Choco) int {
return choco.CalcScore(this.GetPos(choco), other.GetPos(choco))
}
type CandidateSlice struct {
slice []*Seq
}
func MakeCandidateSlice(now *Seq, choco Choco) *CandidateSlice {
slice := make([]*Seq, 0)
t := now.NextIndex()
for !t.IsOver(choco) {
if !t.IsNg(now, choco) {
slice = append(slice, t)
}
t = t.NextIndex()
}
return &CandidateSlice{slice}
}
func (this *CandidateSlice) Disp() {
for _, s := range this.slice {
s.Disp()
fmt.Printf("\n")
}
}
func (this *CandidateSlice) GetSlice() []*Seq {
return this.slice
}
type EatOne struct {
score int
seq *Seq
}
func MakeEatOne(seq *Seq) *EatOne {
return &EatOne{1, seq}
}
func (this EatOne) GetScore() int {
return this.score
}
func (this EatOne) Disp() {
fmt.Printf("score = %d : ", this.score)
this.seq.Disp()
fmt.Printf("\n")
}
func (this EatOne) GetLhsSeq() *Seq {
return this.seq
}
type EatPair struct {
score int
lhs *Seq
rhs *Seq
}
func MakeEatPair(lhs *Seq, rhs *Seq, choco Choco) *EatPair {
score := lhs.CalcScore(rhs, choco)
return &EatPair{score, lhs, rhs}
}
func (this EatPair) GetScore() int {
return this.score
}
func (this EatPair) Disp() {
fmt.Printf("score = %d : ", this.score)
this.lhs.Disp()
fmt.Printf(" , ")
this.rhs.Disp()
fmt.Printf("\n")
}
func (this EatPair) GetLhsSeq() *Seq {
return this.lhs
}
type Scorerable interface {
GetScore() int
Disp()
GetLhsSeq() *Seq
}
type Result struct {
prev *Result
eat Scorerable
choco Choco
}
func MakeResult(eat Scorerable, choco Choco) *Result {
return &Result{nil, eat, choco}
}
func (this *Result) MakeResultChain(eat Scorerable, choco Choco) *Result {
return &Result{this, eat, choco}
}
func (this *Result) MakeResultOverWrite(eat Scorerable, choco Choco) {
this.eat = eat
this.choco = choco
}
func (this *Result) Disp() {
this.eat.Disp()
}
func (this *Result) DispChain() {
r := this
for r != nil {
r.Disp()
r = r.prev
}
return
}
func (this *Result) GetLhsSeq() *Seq {
return this.eat.GetLhsSeq()
}
func (this *Result) GetChoco() Choco {
return this.choco
}
func (this *Result) CalcChaindScore() int {
r := this
score := 0
for r != nil {
score = score + r.eat.GetScore()
r = r.prev
}
return score
}
type ResultContainer struct {
container []*Result
}
func MakeResultContainer() *ResultContainer {
container := make([]*Result, 0)
return &ResultContainer{container}
}
func (this *ResultContainer) push(new Result) {
this.container = append(this.container, &new)
}
func (this *ResultContainer) pop() Result {
ret := this.container[len(this.container)-1]
this.container = this.container[0 : len(this.container)-1]
return *ret
}
func (this *ResultContainer) IsEmpty() bool {
return len(this.container) == 0
}
func TryResolve(choco Choco) int {
best := 0
var bestResult *Result = nil
results := MakeResultContainer()
t := MakeSeq(0)
// １つだけ食べる場合をContainerにPush
for !t.IsOver(choco) {
if !t.IsNgPos(choco) {
e := MakeEatOne(t)
c := choco.Clone()
c.Put(t.GetPos(choco))
// c.Disp()
r := MakeResult(e, c)
results.push(*r)
}
t = t.NextIndex()
}
// コンテナから取り出して、次の候補をPush
for !results.IsEmpty() {
res := results.pop()
score := res.CalcChaindScore()
if score > best {
best = score
bestResult = &res
}
// 次に１つだけ食べるパターンをpush
t := res.eat.GetLhsSeq().NextIndex()
for !t.IsOver(res.GetChoco()) {
if !t.IsNgPos(res.GetChoco()) {
e := MakeEatOne(t)
cp := res.GetChoco()
c := cp.Clone()
c.Put(t.GetPos(res.GetChoco()))
r := res.MakeResultChain(e, c)
results.push(*r)
}
t = t.NextIndex()
}
// 今回2つ食べるパターンをpush
switch res.eat.(type) {
case *EatOne:
candidate := MakeCandidateSlice(res.GetLhsSeq(), res.GetChoco())
for _, can := range candidate.GetSlice() {
// fmt.Printf("ok")
cp := res.GetChoco()
c := cp.Clone()
c.Put(can.GetPos(res.GetChoco()))
eatPair := MakeEatPair(res.GetLhsSeq(), can, res.GetChoco())
if res.prev == nil { // 初回だけペアをトップレベルに登録
result := MakeResult(eatPair, c)
results.push(*result)
} else { // 初回以降は、すべてResultをチェインさせる
result := res
result.MakeResultOverWrite(eatPair, c)
results.push(result)
}
}
default:
break
}
}
bestResult.DispChain()
return best
}
func main() {
var n, m int
fmt.Scanf("%d %d", &n, &m)
choco := MakeChoco(n, m)
choco.Load(os.Stdin)
best := TryResolve(*choco)
fmt.Printf("%d\n", best)
}