結果
問題 | No.2000 Distanced Characters |
ユーザー |
|
提出日時 | 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 |
ソースコード
package mainimport ("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 = 26const INF = 1 << 60f := 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))) - 1for (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*yのオーバーフロー対策のため先にGcdで割る// Gcd(x, y)はxの約数のため割り切れるret := x / Gcd(x, y)ret *= yreturn ret}func Pow(x, y, p int) int {ret := 1for y > 0 {if y%2 == 1 {ret = ret * x % p}y >>= 1x = x * x % p}return ret}func Inv(x, p int) int {return Pow(x, p-2, p)}func Permutation(N, K int) int {v := 1if 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 intfac []int // Factional(i) mod pfinv []int // 1/Factional(i) mod pinv []int // 1/i mod p}func NewCombination(n, p int) *Comb {c := new(Comb)c.n = nc.p = pc.fac = make([]int, n+1)c.finv = make([]int, n+1)c.inv = make([]int, n+1)c.fac[0] = 1c.fac[1] = 1c.finv[0] = 1c.finv[1] = 1c.inv[1] = 1for i := 2; i <= n; i++ {c.fac[i] = c.fac[i-1] * i % pc.inv[i] = p - c.inv[p%i]*(p/i)%pc.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.pret *= c.finv[n-k]ret %= c.preturn ret}//重複組み合わせ Hfunc (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() - 1if n < 1 {return false}j := n - 1for ; !x.Less(j, j+1); j-- {if j == 0 {return false}}l := nfor !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 intY intD 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 numbersrank []int // height of treesize []int}func NewUnionFind(n int) *UnionFind {if n <= 0 {return nil}u := new(UnionFind)// for accessing index without minus 1u.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] = iu.rank[i] = 0u.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 4this.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}// rankif this.rank[x] < this.rank[y] {//yがrootの木にxがrootの木を結合するthis.par[x] = ythis.size[y] += this.size[x]} else {// this.rank[x] >= this.rank[y]//xがrootの木にyがrootの木を結合するthis.par[y] = xthis.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 intnodes []inteval func(x1, x2 int) int}func NewBinaryIndexTree(n int, f func(x1, x2 int) int) *BinaryIndexedTree {bt := new(BinaryIndexedTree)// 1-indexedbt.n = n + 1bt.nodes = make([]int, bt.n)bt.eval = freturn bt}//i(0-indexed)をvに更新するfunc (bt *BinaryIndexedTree) Update(i, v int) {//bt内部では1-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 := 0for i > 0 {res = bt.eval(bt.nodes[i], res)i -= i & -i}return res}