結果

問題 No.421 しろくろチョコレート
ユーザー jugemjugemjugem
提出日時 2016-10-19 01:53:05
言語 Go
(1.23.4)
結果
TLE  
実行時間 -
コード長 7,312 bytes
コンパイル時間 11,759 ms
コンパイル使用メモリ 222,788 KB
実行使用メモリ 353,888 KB
最終ジャッジ日時 2024-11-22 15:00:39
合計ジャッジ時間 179,678 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 1 WA * 10 TLE * 50 MLE * 4
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

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)
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0