結果

問題 No.1005 BOT対策
コンテスト
ユーザー ID 21712
提出日時 2025-01-01 18:08:17
言語 Go
(1.23.4)
結果
WA  
実行時間 -
コード長 728 bytes
コンパイル時間 10,020 ms
コンパイル使用メモリ 233,188 KB
実行使用メモリ 9,952 KB
最終ジャッジ日時 2025-01-01 18:08:29
合計ジャッジ時間 11,131 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge7
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 23 WA * 4
権限があれば一括ダウンロードができます

ソースコード

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)
	
	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:len(bt)] {
			dp[i][0] = min(dp[i][0], v+1)
		}
		for j, tc := range bt {
			if sc == tc {
				dp[i+1][j+1] = min(dp[i+1][j+1], dp[i][j])	
			} else {
				dp[i+1][0] = min(dp[i+1][0], dp[i][j])
			}
		}
		dp[i+1][len(bt)] = X
	}
	
	ans := Min(dp[len(bs)])
	if ans < X {
		Println(ans)
	} else {
		Println(-1)
	}
}
0