結果

問題 No.1156 Nada Picnic 2
ユーザー ID 21712ID 21712
提出日時 2024-12-23 22:14:24
言語 Go
(1.23.4)
結果
AC  
実行時間 506 ms / 2,000 ms
コード長 1,303 bytes
コンパイル時間 14,575 ms
コンパイル使用メモリ 225,604 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-12-23 22:14:40
合計ジャッジ時間 14,426 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 15 ms
5,248 KB
testcase_01 AC 139 ms
5,248 KB
testcase_02 AC 506 ms
5,248 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

package main

import . "fmt"

func main() {
	var n int
	Scan(&n)
	switch n {
		case 1:
		solve("シイタ","ケヤマ", "イキタイ")
		case 2:
		solve("オオツカ","コクサイ","ビジツカン")
		case 3:
		solve("spring","eight","picnic")
	}
}

func solve(ss ...string) {
	t, m := index(ss...)
	d := len(m)
	v := make([]int, d)
	dfs(d, t, 0, v, func() bool {
		sum, ok := calc(v, m, ss...)
		if ok {
			Println(sum)
		}
		return ok
	})
}

func calc(v []int, m map[rune]int, ss ...string) (sum int, ok bool) {
	for i, s := range ss {
		var x int
		for _, r := range s {
			x = x * 10 + v[m[r]]
		}
		if i+1 < len(ss) {
			sum += x
		} else {
			return sum, sum == x
		}
	}
	return
}

func index(ss ...string) (t int, m map[rune]int) {
	m = map[rune]int{}
	var i int
	for _, s := range ss {
		for _, r := range s {
			if _, ok := m[r]; !ok {
				m[r] = i
				i++
				t++
			}
			break
		}
	}
	for _, s := range ss {
		for _, r := range s {
			if _, ok := m[r]; !ok {
				m[r] = i
				i++
			}
		}
	}
	return
}

func dfs(d, t, u int, v []int, callback func() bool) bool {
	if d == 0 {
		return callback()
	}
	s := 0
	if t > 0 {
		s++
	}
	for i:=s; i <= 9; i++ {
		if (u&(1<<i)) != 0 {
			continue
		}
		v[len(v)-d] = i
		if dfs(d-1,t-1,u|(1<<i),v, callback) {
			return true
		}
	}
	return false
}
0