【Scala】AtCoder Beginner Contest 197の「C - ORXOR」をbit全探索を使わずに解く

概要

AtCoder Beginner Contest 197のC問題C - ORXORについて、解説を読むと、bit全探索を使うのが良いとあります。もちろん、こういった問題を見てぱっとbit全探索が思いつけば良いのですが、思いつかない場合もあると思います。（私は思いつきませんでした）
ということで、少し愚直めに実装した内容をメモ書きしたいと思います。実装言語はScalaです。

実装の方針

• まずは1区間しかない状態からスタートし、どの箇所で区切るかというのを全部試します。区切りの結果を二重のコレクションで保持します。
• 一重目のコレクションでOR演算の結果を取得して、そのOR演算の結果をXOR演算します。
• 一桁ずつ桁を動かしていき、区切った場合と区切らなかった場合で再起で関数呼び出しを行います。区切った場合はXOR演算で結果を取得します。

実装サンプル

提出結果はこちらです。実装内容は以下にも記載します。

object Main extends App {
  val n = scala.io.StdIn.readInt();
  val aVector = scala.io.StdIn.readLine().split(" ").map(_.toLong).toVector
 
  // 適当な値で結果を初期化
  var result = 222222222222L
 
  // 与えられた区間のOR演算結果を取得
  def getOr(orVector: Vector[Long]): Long = {
    orVector.reduceLeft((z, n) => z | n)
  }
 
  // 二重のVectorに対してXOR演算結果を取得
  def judgeResult(targetVecVector: Vector[Vector[Long]]): Unit = {
    // 各区間毎にOR演算結果を取得の後にXOR演算
    val xor = targetVecVector.map(getOr).reduce((z, n) => z ^ n)
    // 取得した値がresultより小さかったら更新
    if (xor < result) {
      result = xor
    }
  }
  
  // 区切りを試す関数
  def splitAndJudge(targetVector: Vector[Vector[Long]], splitIndex: Int, count: Int): Unit = {
    if (count < n) {
      // そのままの状態で再起呼び出し
      splitAndJudge(targetVector, splitIndex + 1, count + 1)
      // 区間を分割
      // 最終区切り以外をそのまま取得
      var newTargetVector = targetVector.dropRight(1)
      // 最終区切りを分割
      val lastVector = targetVector.last
      val lastSplit = lastVector.splitAt(splitIndex)
      newTargetVector :+= lastSplit._1
      newTargetVector :+= lastSplit._2
      // 分割を行ったら結果取得
      judgeResult(newTargetVector)
      // 分割した状態で再起呼び出し
      splitAndJudge(newTargetVector, 1, count + 1)
    }
  }
  
  var vecVec = Vector.empty[Vector[Long]]
  // まずは1区間に全値がある状態でスタート
  vecVec :+= aVector
  // 1区間に全値がある状態でresult値を更新
  judgeResult(vecVec)
  // 区切りを試す
  splitAndJudge(vecVec, 1, 1)
  println(result)
 
}