AtCoder Beginner Contest 307 B - racecar

AtCoderをやり始めた。 全然問題が解けないので、復習する。

atcoder.jp

問題

英小文字のみからなる$N$個 の文字列 $S_1,S2,...S_N$が与えられる。 $ 1以上N以下$の相異なる$整数i,j$であって、$S_i, S_j$をこの順に連結した文字列が回文となるようなものが存在するか判定せよ。 ただし、長さ$M$の文字列$T$が回文であるとは、任意の$ 1 \leq i \leq M $について、$T$の$i$文字目と$(M+1-i)$文字目が一致していることをいう。

制約

• $ 2 \leq N \leq 100 $
• $ 1 \leq |S_i| \leq 50 $
• $ Nは整数 $
• $ S_i は英小文字からなる文字列 $
• $ S_i はすべて異なる $

何も考えず書いたコード（間違い）

package main
 
import (
    "fmt"
    "strings"
)
 
func main() {
    var N int
    fmt.Scanf("%d", &N)
 
    S := make([]string, N)
    for i := 0; i < N; i++ {
        fmt.Scan(&S[i])
    }
 
    ans := "No"
    for i := 0; i < N; i++ {
        for j := i + 1; j < N; j++ {
            slice := strings.Split(S[i]+S[j], "")
            len := len(slice)
            // fmt.Println(slice)
            for k := 0; k <= len/2; k++ {
                // fmt.Println("slice", slice[k], slice[len-k-1])
                if k == len/2 {
                    ans = "Yes"
                    break
                }
                if slice[k] != slice[len-k-1] {
                    break
                }
            }
            if ans == "Yes" {
                break
            }
        }
        if ans == "Yes" {
            break
        }
    }
 
    fmt.Println(ans)
}

間違いポイント

• まず、コードは汚いけど考え方は正しかった。
• j := i + 1としているが、j := 0からすべき。でないと、網羅できないケースがでてくることに気がつけなかった。
• 文字列判定は止めるべし。

正しい解

package main

import "fmt"

func main() {
    var N int
    fmt.Scanf("%d", &N)

    S := make([]string, N)
    for i := 0; i < N; i++ {
        fmt.Scanf("%s", &S[i])
    }

    ex := false
    for i := 0; i < N; i++ {
        for j := 0; j < N; j++ {
            f := S[i]
            s := S[j]
            if s == f {
                continue
            }

            ex = chmatch(f + s)
            if ex {
                break
            }
        }
        if ex {
            break
        }
    }

    if ex {
        fmt.Println("Yes")
    } else {
        fmt.Println("No")
    }
}

func chmatch(m string) bool {
    for i := 0; i < len(m)/2; i++ {
        if m[i] == m[len(m)-1-i] {
            continue
        } else {
            return false
        }
    }
    return true
}

ポイント

• j := 0から開始して、ケースを網羅できた。
• 文字列判定をやめて、boolの判定へ変更し、スッキリさせた。
• コンテスト中は、普段のパフォーマンスが全然だせない。文字列判定とか普段使わない方法でやったり、変な焦りがあるので、徐々に克服を目指すべし。