Hatena::Grouptopcoder

TopCoderの学習のお時間 RSSフィード

戦績(topcoder.com) / 戦績(competitiveprogramming.info) / 過去記事 / 日記

 | 

2013-04-16

[] Google Code Jam 2013 Qualification Round 23:22 はてなブックマーク -  Google Code Jam 2013 Qualification Round - TopCoderの学習のお時間


D-large以外を解いた。修行のためにScalaで。

調べつつ書いてるので望ましくないスタイルの書き方も含まれていると思う



  • A

やるだけ。

object A {

  val sc = new java.util.Scanner(System.in)

  def main(args: Array[String]) {
    val T = sc.nextInt()
    for (t <- 1 to T) {
      printf("Case #%d: %s\n", t, solve())
    }
  }

  def solve(): String = {
    val board = new Array[String](4)
    for (i <- 0 to 3) {
      board(i) = sc.next()
    }
    if (win(board, 'X')) return "X won"
    if (win(board, 'O')) return "O won"
    if (board.exists(_.contains('.'))) return "Game has not completed"
    return "Draw"
  }

  def win(board: Array[String], hand: Char): Boolean = {
    def test(target: Char) = target == hand || target == 'T'
    for (line <- board) if (line.forall(test)) return true // horz
    for (i <- 0 to 3) {
      val l = for (line <- board) yield line(i) // vert
      if (l.forall(test)) return true
    }
    if ((for (i <- 0 to 3) yield board(i)(i)).forall(test)) return true // diag\
    if ((for (i <- 0 to 3) yield board(i)(3 - i)).forall(test)) return true // diag/
    return false
  }

}

  • B

各高さのセルが、自分以下の高さのセルだけからなる行または列に含まれているかをチェック

object B {

  val sc = new java.util.Scanner(System.in)

  def main(args: Array[String]) {
    val T = sc.nextInt()
    for (t <- 1 to T) {
      printf("Case #%d: %s\n", t, if (solve()) "YES" else "NO")
    }
  }

  def solve(): Boolean = {
    val N, M = sc.nextInt()
    val field = Array.fill(N, M)(sc.nextInt());
    for (i <- 1 to 100) {
      if (!test(field, i)) return false
    }
    return true
  }

  def test(field: Array[Array[Int]], h: Int): Boolean = {
    for (i <- 0 until field.size) {
      val line = for (j <- 0 until field(0).size) yield field(i)(j)
      if (line.forall(_ <= h)) {
        for (j <- 0 until field(0).size) field(i)(j) = 0
      }
    }
    for (i <- 0 until field(0).size) {
      val line = for (j <- 0 until field.size) yield field(j)(i)
      if (line.forall(_ <= h)) {
        for (j <- 0 until field.size) field(j)(i) = 0
      }
    }
    for (line <- field) if (line.exists(_ == h)) return false
    return true
  }

}

  • C small・large1

10^7までの回文数を列挙して、二乗回文数になってるかチェック

object C {

  val sc = new java.util.Scanner(System.in)
  val sqpal = generate()

  def main(args: Array[String]) {
    val T = sc.nextInt()
    for (t <- 1 to T) {
      printf("Case #%d: %d\n", t, solve())
    }
  }

  def solve(): Long = {
    val A, B = sc.nextInt()
    return count(B) - count(A - 1)
  }

  def count(N: Long): Long = {
    return sqpal.count(_ <= N)
  }

  def generate(): Seq[Long] = {
    val ret = for (digits <- 1 to 8) yield generate(Array.ofDim[Int](digits), 0)
    return ret.flatten
  }

  def generate(ar: Array[Int], pos: Int): List[Long] = {
    if (pos * 2 >= ar.size) {
      val num: Long = ar.reduceLeft(10 * _ + _)
      if (isPalindrome(num * num)) {
        return List(num * num)
      } else {
        return List()
      }
    } else {
      var ret = List[Long]()
      for (i <- (if (pos == 0) 1 else 0) to 9) {
        ar(pos) = i
        ar(ar.size - 1 - pos) = i
        ret = ret ::: generate(ar, pos + 1)
      }
      return ret
    }
  }

  def isPalindrome(num: Long): Boolean = {
    val str = num + "";
    for (i <- 0 until str.size / 2) {
      if (str(i) != str(str.size - 1 - i)) return false
    }
    return true;
  }

}

  • C large2

二乗したときに繰り上がりがない回文数を枝刈りDFSで列挙

各桁の数値を要素に持つ配列で扱ってるので多倍長整数は使ってない

実行時間は3秒くらい

object CL {

  val sc = new java.util.Scanner(System.in)
  val sqpal = generate()

  def main(args: Array[String]) {
//    println(sqpal.mkString("\n"))
//    println(sqpal.size)
    val T = sc.nextInt()
    for (t <- 1 to T) {
      printf("Case #%d: %d\n", t, solve())
    }
  }

  def solve(): Long = {
    val A, B = sc.next()
    return sqpal.count(x => compare(A, x) && compare(x, B))
  }

  def compare(l: String, r: String): Boolean = {
    if (l.size < r.size) return true;
    if (l.size > r.size) return false;
    return l <= r
  }

  def generate(): Seq[String] = {
    val ret = for (digits <- 1 to 50) yield generate(Array.ofDim[Int](digits), Array.ofDim[Int](digits * 2 - 1), 0)
    return ret.flatten
  }

  def generate(base: Array[Int], sq: Array[Int], pos: Int): List[String] = {
    if (pos * 2 >= base.size) {
      return List(sq.reverse.map(_.toString).mkString(""))
    } else {
      var ret = List[String]()
      for (i <- (if (pos == 0) 1 else 0) to 3) {
        base(pos) = i
        base(base.size - 1 - pos) = i
        for (j <- 0 until pos) {
          sq(pos + j) += 2 * i * base(j)
          sq(pos + base.size - 1 - j) += 2 * i * base(base.size - 1 - j)
          if (pos != base.size - 1 - pos) {
            sq(base.size - 1 - pos + j) += 2 * i * base(j)
            sq(base.size - 1 - pos + base.size - 1 - j) += 2 * i * base(base.size - 1 - j)
          }
        }
        sq(pos * 2) += i * i
        if (pos * 2 + 1 < base.size) {
          sq((base.size - 1 - pos) * 2) += i * i
          sq((base.size - 1 - pos) + pos) += 2 * i * i
        }
        if (sq.forall(_ < 10)) ret = ret ::: generate(base, sq, pos + 1)
        for (j <- 0 until pos) {
          sq(pos + j) -= 2 * i * base(j)
          sq(pos + base.size - 1 - j) -= 2 * i * base(base.size - 1 - j)
          if (pos != base.size - 1 - pos) {
            sq(base.size - 1 - pos + j) -= 2 * i * base(j)
            sq(base.size - 1 - pos + base.size - 1 - j) -= 2 * i * base(base.size - 1 - j)
          }
        }
        sq(pos * 2) -= i * i
        if (pos * 2 + 1 < base.size) {
          sq((base.size - 1 - pos) * 2) -= i * i
          sq((base.size - 1 - pos) + pos) -= 2 * i * i
        }
      }
      base(pos) = 0
      base(base.size - 1 - pos) = 0
      return ret
    }
  }

}

  • D small

メモ化DFS

object D {

  val sc = new java.util.Scanner(System.in)

  def main(args: Array[String]) {
    val T = sc.nextInt()
    for (t <- 1 to T) {
      printf("Case #%d: %s\n", t, new Solver(sc).solve())
    }
  }

  class Solver(sc: java.util.Scanner) {
    val keys = Array.ofDim[Int](201)
    val K, N = sc.nextInt()
    for (i <- 1 to K) {
      keys(sc.nextInt()) += 1
    }
    val chest = Array.fill(N)(new Chest(sc))
    val visited = Array.ofDim[Boolean](1 << N)

    def solve(): String = {
      val result = rec(0)
      result match {
        case Some(path) =>
          return path.mkString(" ")
        case None =>
          return "IMPOSSIBLE"
      }
    }

    def rec(st: Int): Option[List[Int]] = {
      if (visited(st)) return None
      visited(st) = true
      if (st == (1 << N) - 1) return Some(List())
      for (i <- 0 until N) {
        if ((st & (1 << i)) == 0 && keys(chest(i).T) > 0) {
          keys(chest(i).T) -= 1
          for (k <- chest(i).key) keys(k) += 1
          val result = rec(st + (1 << i))
          if (!result.isEmpty) {
            return Some(i + 1 :: result.get)
          }
          for (k <- chest(i).key) keys(k) -= 1
          keys(chest(i).T) += 1
        }
      }
      return None
    }

  }

  class Chest(sc: java.util.Scanner) {
    val T, K = sc.nextInt()
    val key = Array.fill(K)(sc.nextInt())
  }

}
 |