#124784 (Go) No.421 しろくろチョコレート

提出ソース

結果

問題	No.421 しろくろチョコレート
ユーザー	jugemjugemjugem
提出日時	2016-10-19 01:56:01
言語	Go (1.22.1)
結果	TLE
実行時間	-
コード長	7,321 bytes
コンパイル時間	14,653 ms
コンパイル使用メモリ	235,384 KB
実行使用メモリ	348,648 KB
最終ジャッジ日時	2024-11-22 15:04:32
合計ジャッジ時間	178,995 ms
ジャッジサーバーID （参考情報）	judge1 / judge3

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	TLE	-
testcase_01	TLE	-
testcase_02	TLE	-
testcase_03	TLE	-
testcase_04	TLE	-
testcase_05	TLE	-
testcase_06	TLE	-
testcase_07	TLE	-
testcase_08	TLE	-
testcase_09	TLE	-
testcase_10	TLE	-
testcase_11	TLE	-
testcase_12	AC	2 ms 10,496 KB
testcase_13	AC	2 ms 259,712 KB
testcase_14	AC	157 ms 11,648 KB
testcase_15	AC	2 ms 277,608 KB
testcase_16	TLE	-
testcase_17	TLE	-
testcase_18	TLE	-
testcase_19	AC	1 ms 10,496 KB
testcase_20	TLE	-
testcase_21	TLE	-
testcase_22	TLE	-
testcase_23	AC	2 ms 10,496 KB
testcase_24	AC	2 ms 174,080 KB
testcase_25	AC	2 ms 10,496 KB
testcase_26	AC	1 ms 202,480 KB
testcase_27	WA	-
testcase_28	TLE	-
testcase_29	TLE	-
testcase_30	MLE	-
testcase_31	TLE	-
testcase_32	TLE	-
testcase_33	TLE	-
testcase_34	TLE	-
testcase_35	TLE	-
testcase_36	TLE	-
testcase_37	TLE	-
testcase_38	MLE	-
testcase_39	TLE	-
testcase_40	TLE	-
testcase_41	TLE	-
testcase_42	TLE	-
testcase_43	TLE	-
testcase_44	TLE	-
testcase_45	TLE	-
testcase_46	TLE	-
testcase_47	TLE	-
testcase_48	TLE	-
testcase_49	TLE	-
testcase_50	TLE	-
testcase_51	TLE	-
testcase_52	TLE	-
testcase_53	TLE	-
testcase_54	TLE	-
testcase_55	TLE	-
testcase_56	TLE	-
testcase_57	TLE	-
testcase_58	TLE	-
testcase_59	TLE	-
testcase_60	MLE	-
testcase_61	MLE	-
testcase_62	TLE	-
testcase_63	TLE	-
testcase_64	AC	2 ms 18,484 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

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)
}

yukicoder

結果

テストケース

ソースコード