結果

問題 No.1617 Palindrome Removal
コンテスト
ユーザー ID 21712
提出日時 2026-05-18 02:48:19
言語 Go
(1.26.1)
コンパイル:
env GOCACHE=/tmp go build _filename_
実行:
./Main
結果
AC  
実行時間 469 ms / 2,000 ms
コード長 1,696 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 15,326 ms
コンパイル使用メモリ 282,572 KB
実行使用メモリ 6,400 KB
最終ジャッジ日時 2026-05-18 02:48:42
合計ジャッジ時間 20,717 ms
ジャッジサーバーID
（参考情報） 		judge1_0 / judge3_0
純コード判定待ち
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

package main

import . "fmt"
import "math/bits"

func main() {
	var s string
	Scan(&s)
	b := []byte(s)
	ans := solve(b)
	Println(ans)
}

func solve(b []byte) int {
	m := map[byte]bool{}
	for i, ch := range b {
		m[ch] = true
		if ch != b[len(b)-1-i] {
			return len(b)
		}
	}
	if len(b) % 2 == 0 {
		if len(m) == 1 {
			return 0
		} else {
			return len(b)-2
		}
	} else if len(m) == 1 || len(b) <= 3 {
		return -1
	} else {
		return len(b)-2
	}
}

func init() {
	check()
}

func check() {
	buf := make([]byte, 100)
	for odd := 0; odd <= 1; odd++ {
		for half := 1; half <= 3; half++ {
			size := half*2+odd
			kind := 1
			for i := 0; i < half+odd; i++ {
				kind *= 3
			}
			b := buf[:size]
			for i := 0; i < kind; i++ {
				for j,x := 0,i; j < half+odd; j++ {
					b[j] = byte(x%3)
					b[size-1-j] = b[j]
					x /= 3
				}
				ans := solve(b)
				expect := bruteforce(b)
				if ans != expect {
					println("b=",Sprintf("%#v",b))
					println("ans=",ans)
					println("expect=",expect)
					return
				}
			}
		}
	}
}

func bruteforce(b []byte) int {
	ans := -1
	size := len(b)
	buf := make([]byte, size)
	for i := 0; i < (1<<size); i++ {
		c := size - bits.OnesCount(uint(i))
		if c % 2 != 0 {
			continue
		}
		tmp := buf[:0]
		for j,x := 0,i; j < size; j++ {
			if (x&1) != 0 {
				tmp = append(tmp, b[j])
			}
			x >>= 1
		}
		if size-c != len(tmp) {
			println("b=",Sprintf("%#v",b))
			println("i=",Sprintf("%b",i))
			println("c=",c)
			println("tmp=",Sprintf("%#v",tmp))
			panic("bug")
		}
		if len(tmp) == 0 {
			ans = max(ans, 0)
			continue
		}
		for u,v := 0,len(tmp)-1; u<v; u,v=u+1,v-1 {
			if tmp[u]!=tmp[v] {
				ans = max(ans, len(tmp))
				break
			}
		}
	}
	return ans
}
0