結果

問題 No.2000 Distanced Characters
ユーザー HimaHima
提出日時 2022-07-08 22:41:55
言語 Go
(1.23.4)
結果
AC  
実行時間 14 ms / 2,000 ms
コード長 7,623 bytes
コンパイル時間 20,911 ms
コンパイル使用メモリ 221,168 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-12-28 07:25:30
合計ジャッジ時間 14,245 ms
ジャッジサーバーID
(参考情報)
judge2 / judge5
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 2
other AC * 13
権限があれば一括ダウンロードができます

ソースコード

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

package main
import (
"bufio"
"errors"
"fmt"
"math"
"os"
"sort"
"strconv"
)
var sc = bufio.NewScanner(os.Stdin)
var out = bufio.NewWriter(os.Stdout)
func solve(s string, d [][]int) [][]string {
const n = 26
const INF = 1 << 60
f := make([][]int, n)
for i := 0; i < n; i++ {
f[i] = make([]int, n)
for j := 0; j < n; j++ {
f[i][j] = INF
}
}
dp := make([]int, n)
for i := 0; i < n; i++ {
dp[i] = -1
}
for i := 0; i < len(s); i++ {
for j := 0; j < n; j++ {
if dp[j] >= 0 {
alpha, beta := j, int(s[i]-'a')
f[alpha][beta] = Min(f[alpha][beta], i-dp[j])
}
}
idx := int(s[i] - 'a')
dp[idx] = i
}
ans := make([][]string, n)
for i := 0; i < n; i++ {
ans[i] = make([]string, n)
for j := 0; j < n; j++ {
if d[i][j] <= f[i][j] {
ans[i][j] = "Y"
} else {
ans[i][j] = "N"
}
}
}
return ans
}
func main() {
buf := make([]byte, 1024*1024)
sc.Buffer(buf, bufio.MaxScanTokenSize)
sc.Split(bufio.ScanWords)
s := nextString()
d := make([][]int, 26)
for i := 0; i < 26; i++ {
d[i] = nextIntSlice(26)
}
ans := solve(s, d)
PrintVertically(ans)
}
func nextInt() int {
sc.Scan()
i, _ := strconv.Atoi(sc.Text())
return i
}
func nextIntSlice(n int) []int {
s := make([]int, n)
for i := range s {
s[i] = nextInt()
}
return s
}
func nextFloat64() float64 {
sc.Scan()
f, _ := strconv.ParseFloat(sc.Text(), 64)
return f
}
func nextString() string {
sc.Scan()
return sc.Text()
}
func PrintInt(x int) {
defer out.Flush()
fmt.Fprintln(out, x)
}
func PrintFloat64(x float64) {
defer out.Flush()
fmt.Fprintln(out, x)
}
func PrintString(x string) {
defer out.Flush()
fmt.Fprintln(out, x)
}
func PrintHorizonaly(x []string) {
defer out.Flush()
fmt.Fprintf(out, "%s", x[0])
for i := 1; i < len(x); i++ {
fmt.Fprintf(out, " %s", x[i])
}
fmt.Fprintln(out)
}
func PrintVertically(x [][]string) {
defer out.Flush()
for _, v := range x {
//fmt.Fprintln(out, v)
PrintHorizonaly(v)
}
}
func Abs(x int) int {
if x < 0 {
return -x
}
return x
}
func Min(x, y int) int {
if x < y {
return x
}
return y
}
func Max(x, y int) int {
if x < y {
return y
}
return x
}
func Floor(x, y int) int {
return x / y
}
func Ceil(x, y int) int {
return (x + y - 1) / y
}
func Sqrt(x int) int {
x2 := int(math.Sqrt(float64(x))) - 1
for (x2+1)*(x2+1) <= x {
x2++
}
return x2
}
func Gcd(x, y int) int {
if x == 0 {
return y
}
if y == 0 {
return x
}
/*
if x < y {
x, y = y, x
}
*/
return Gcd(y, x%y)
}
func Lcm(x, y int) int {
// x*yGcd
// Gcd(x, y)x
ret := x / Gcd(x, y)
ret *= y
return ret
}
func Pow(x, y, p int) int {
ret := 1
for y > 0 {
if y%2 == 1 {
ret = ret * x % p
}
y >>= 1
x = x * x % p
}
return ret
}
func Inv(x, p int) int {
return Pow(x, p-2, p)
}
func Permutation(N, K int) int {
v := 1
if 0 < K && K <= N {
for i := 0; i < K; i++ {
v *= (N - i)
}
} else if K > N {
v = 0
}
return v
}
func Factional(N int) int {
return Permutation(N, N-1)
}
func Combination(N, K int) int {
if K == 0 {
return 1
}
if K == 1 {
return N
}
return Combination(N, K-1) * (N + 1 - K) / K
}
type Comb struct {
n, p int
fac []int // Factional(i) mod p
finv []int // 1/Factional(i) mod p
inv []int // 1/i mod p
}
func NewCombination(n, p int) *Comb {
c := new(Comb)
c.n = n
c.p = p
c.fac = make([]int, n+1)
c.finv = make([]int, n+1)
c.inv = make([]int, n+1)
c.fac[0] = 1
c.fac[1] = 1
c.finv[0] = 1
c.finv[1] = 1
c.inv[1] = 1
for i := 2; i <= n; i++ {
c.fac[i] = c.fac[i-1] * i % p
c.inv[i] = p - c.inv[p%i]*(p/i)%p
c.finv[i] = c.finv[i-1] * c.inv[i] % p
}
return c
}
func (c *Comb) Factional(x int) int {
return c.fac[x]
}
func (c *Comb) Combination(n, k int) int {
if n < k {
return 0
}
if n < 0 || k < 0 {
return 0
}
ret := c.fac[n] * c.finv[k]
ret %= c.p
ret *= c.finv[n-k]
ret %= c.p
return ret
}
// H
func (c *Comb) DuplicateCombination(n, k int) int {
return c.Combination(n+k-1, k)
}
func (c *Comb) Inv(x int) int {
return c.inv[x]
}
func NextPermutation(x sort.Interface) bool {
n := x.Len() - 1
if n < 1 {
return false
}
j := n - 1
for ; !x.Less(j, j+1); j-- {
if j == 0 {
return false
}
}
l := n
for !x.Less(j, l) {
l--
}
x.Swap(j, l)
for k, l := j+1, n; k < l; {
x.Swap(k, l)
k++
l--
}
return true
}
func DivideSlice(A []int, K int) ([]int, []int, error) {
if len(A) < K {
return nil, nil, errors.New("")
}
return A[:K+1], A[K:], nil
}
type IntQueue struct {
q []int
}
func NewIntQueue() *IntQueue {
return new(IntQueue)
}
func (this *IntQueue) Push(v int) {
this.q = append(this.q, v)
}
func (this *IntQueue) Pop() (int, error) {
if this.Size() == 0 {
return -1, errors.New("")
}
ret := this.q[0]
this.q = this.q[1:]
return ret, nil
}
func (this *IntQueue) Size() int {
return len(this.q)
}
func (this *IntQueue) PrintQueue() {
fmt.Println(this.q)
}
type Pos struct {
X int
Y int
D int
}
type Queue struct {
ps []Pos
}
func NewQueue() *Queue {
return new(Queue)
}
func (this *Queue) Push(p Pos) {
this.ps = append(this.ps, p)
}
func (this *Queue) Pop() *Pos {
if len(this.ps) == 0 {
return nil
}
p := this.ps[0]
this.ps = this.ps[1:]
return &p
}
func (this *Queue) Find(x, y int) bool {
for _, v := range this.ps {
if x == v.X && y == v.Y {
return true
}
}
return false
}
func (this *Queue) Size() int {
return len(this.ps)
}
type UnionFind struct {
par []int // parent numbers
rank []int // height of tree
size []int
}
func NewUnionFind(n int) *UnionFind {
if n <= 0 {
return nil
}
u := new(UnionFind)
// for accessing index without minus 1
u.par = make([]int, n+1)
u.rank = make([]int, n+1)
u.size = make([]int, n+1)
for i := 0; i <= n; i++ {
u.par[i] = i
u.rank[i] = 0
u.size[i] = 1
}
return u
}
func (this *UnionFind) Find(x int) int {
if this.par[x] == x {
return x
} else {
// compress path
// ex. Find(4)
// 1 - 2 - 3 - 4
// 1 - 2
// L-3
// L 4
this.par[x] = this.Find(this.par[x])
return this.par[x]
}
}
func (this *UnionFind) Size(x int) int {
return this.size[this.Find(x)]
}
func (this *UnionFind) ExistSameUnion(x, y int) bool {
return this.Find(x) == this.Find(y)
}
func (this *UnionFind) Unite(x, y int) {
x = this.Find(x)
y = this.Find(y)
if x == y {
return
}
// rank
if this.rank[x] < this.rank[y] {
//yrootxroot
this.par[x] = y
this.size[y] += this.size[x]
} else {
// this.rank[x] >= this.rank[y]
//xrootyroot
this.par[y] = x
this.size[x] += this.size[y]
if this.rank[x] == this.rank[y] {
this.rank[x]++
}
}
}
func PrintUnionFind(u *UnionFind) {
// for debuging. not optimize.
fmt.Println(u.par)
fmt.Println(u.rank)
fmt.Println(u.size)
}
type BinaryIndexedTree struct {
n int
nodes []int
eval func(x1, x2 int) int
}
func NewBinaryIndexTree(n int, f func(x1, x2 int) int) *BinaryIndexedTree {
bt := new(BinaryIndexedTree)
// 1-indexed
bt.n = n + 1
bt.nodes = make([]int, bt.n)
bt.eval = f
return bt
}
//i(0-indexed)v
func (bt *BinaryIndexedTree) Update(i, v int) {
//bt1-indexed
i++
for i < bt.n {
bt.nodes[i] = bt.eval(bt.nodes[i], v)
i += i & -1
}
}
//i(0-indexed)
func (bt *BinaryIndexedTree) Query(i int) int {
i++
res := 0
for i > 0 {
res = bt.eval(bt.nodes[i], res)
i -= i & -i
}
return res
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0