■ [GCJ] Google Code Jam 2013 Qualification Round 
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
各桁の数値を要素に持つ配列で扱ってるので多倍長整数は使ってない
実行時間は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()) } }
