ABC182

AtCoder Beginner Contest 182
C - To 3
https://atcoder.jp/contests/abc182/tasks/abc182_c

package main
import(
    "fmt"
    "bufio"
    "os"
    "strconv"
    "strings"
)
var rdr=bufio.NewReaderSize(os.Stdin,1024*1024)
func readLine() string {
    buf := []byte{}
    for {
        l, p, e := rdr.ReadLine()
        if e != nil {
            panic(e)
        }
        buf = append(buf, l...)
        if !p {
            break
        }
    }
    return string(buf)
}
func readInts()[]int{
    s:=strings.Split(readLine()," ")
    res:=[]int{}
    for _,v:=range s{
        i,_:=strconv.Atoi(v)
        res=append(res,i)
    }
    return res
}

func main(){
  s:=strings.Split(readLine(),"")
  //使わない桁数、最大18桁あるので18+1=19とする
  minK:=19
  n:=len(s)
  for bits:=0;bits<(1<<uint64(n));bits++{
    var cp=make([]string,n)
    //元が変わってしまうので、いちいちコピーする
    copy(cp,s)
    k:=0
    sums:=0
    for i:=0;i<n;i++{
      if (bits>>uint64(i))&1==1{
        k++
      }else{
        j,_:=strconv.Atoi(s[i])
        sums+=j
      }
    }
    if sums%3==0 && minK>k{
      minK=k
    }
  }
  if minK==n{
    fmt.Println(-1)
  }else{
    fmt.Println(minK)
  }
}

・各桁の合計が3で割り切れる場合は3の倍数であること
・どの桁を「使わないか」を全探索する場合は、bit全探索を使用する
上記のことを考え、適当にbit全探索をしたら解けてしまいました。

参考URL

標準入力はこちら、bit全探索はこちらを参考にしました。ありがとうございます。