結果

問題 No.1005 BOT対策
ユーザー ID 21712
提出日時 2025-01-01 18:48:54
言語 Go
(1.23.4)
結果
WA  
実行時間 -
コード長 1,069 bytes
コンパイル時間 10,388 ms
コンパイル使用メモリ 234,020 KB
実行使用メモリ 7,900 KB
最終ジャッジ日時 2025-01-01 18:49:07
合計ジャッジ時間 11,620 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 21 WA * 6
権限があれば一括ダウンロードができます

ソースコード

diff # 

package main

import . "fmt"
import . "slices"

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func main() {
	var s, t string
	Scan(&s, &t)
	bs := []byte(s)
	bt := []byte(t)
	
	if len(t) > len(s) {
		Println(0)
		return
	}
	
	if len(t) == 1 {
		if Contains(bs, bt[0]) {
			Println(-1)
		} else {
			Println(0)
		}
		return
	}

	const X = 1e9
	
	dp := make([][]int, len(bs)+1)
	for i := range dp {
		dp[i] = make([]int, len(bt)+1)
		for j := range dp[i] {
			dp[i][j] = X
		}
	}
	
	dp[0][0] = 0
	
	for i, sc := range bs {
		for _, v := range dp[i][1:] {
			dp[i][0] = min(dp[i][0], v+1)
		}
		// Println(i,":",dp[i])
		cnt := 0
		for j, tc := range bt {
			if sc == tc {
				dp[i+1][j+1] = min(dp[i+1][j+1], dp[i][j])	
				cnt++
			} else if cnt == 0 {
				dp[i+1][0] = min(dp[i+1][0], dp[i][j])
			} else {
				for e:=1; e < j; e++ {
					if dp[i+1][e] < X {
						dp[i+1][e] = min(dp[i+1][e], dp[i][j])
					}
				}
			}
		}
		// Println(i+1,":",dp[i+1])
	}

	ans := Min(dp[len(bs)][:len(bt)])
	if ans < X {
		Println(ans)
	} else {
		Println(-1)
	}
}
0