新人SEの学習記録

14年度入社SEの学習記録用に始めたブログです。気づけば社会人3年目に突入。

参加記録:AtCoder Beginner Contest 023

[参加記録] AtCoder Beginner Contest 023

コンテストURL

Welcome to AtCoder Beginner Contest 023 - AtCoder Beginner Contest 023 | AtCoder

結果

  • A, B問題の200点+C問題部分点30点の計230点
    • Scalaで書いてみた。ほとんどJavaと変わらない書き方だけど・・・

プログラム

A問題
  • 2桁の数字が与えられ、1の位と10の位の数字の和を求める
    • ScalaでもJavaのScannerが使えるのでそちらを使用
    • 文字列として読み込んで1の位と10の位をそれぞれIntに変換して足し合わせる
    • Scalaのライブラリわからねーと思ってたら解説見たら10で割った商と余りで良かったorz
object Main {
  def main(args: Array[String]): Unit = {
    val sc = new java.util.Scanner(System.in)
    val x = sc.next
    println(x.head.toString.toInt + x.tail.toInt)
  }
}
B問題
  • 文字bの前後にaとcを追加->cとaを追加->bとbを追加->...の順に文字を追加していく
    • 与えられた文字列sが上記の手順の何回目で作られるか出力(上記の手順で作れない場合-1を出力)
    • 再帰で書いてみた。
object Main {
  def main(args: Array[String]): Unit = {
    val sc = new java.util.Scanner(System.in)
    val n = sc.nextInt
    val s = sc.next
    def go(no: Int, cur: String): Int =
      if (cur.length >= s.length)
        if (cur == s) no-1
        else -1
      else if (no == 0)
        go(no+1, "b")
      else if (no % 3 == 1)
        go(no+1, "a" + cur + "c")
      else if (no % 3 == 2)
        go(no+1, "c" + cur + "a")
      else
        go(no+1, "b" + cur + "b")

    val ans = go(0, "")

    println(ans)
  }
}
C問題
  • R*Cマスの正方形にN個の飴が置かれており、ある地点に移動するとその地点の行/列にある全ての飴を取得できる
    • ちょうどK個の飴を獲得できる地点が何マスあるか求める
    • 自分の回答は以下。普通にやると全マス検索&&毎回N個の飴について検索しなければいけない
    • そこで、その行/列に何個飴が存在するかの配列を作り、そこから計算するようにした
    • 特に、飴が存在するマスに移動すると行と列で重複して数えてしまうので、うまいことやる必要がある
object Main {
  def main(args: Array[String]): Unit = {
    val sc = new java.util.Scanner(System.in)
    val R,C,K = sc.nextInt
    val N = sc.nextInt
    val r, c = new Array[Int](N)
    // tate(x): x行目に存在する飴の数                                                       
    val tate = new Array[Int](R)
    // yoko(y): y列目に存在する飴の数                                                       
    val yoko = new Array[Int](C)
 
    for (i <- 0 to N - 1) {
      r(i) = sc.nextInt - 1
      c(i) = sc.nextInt - 1
      tate(r(i)) += 1
      yoko(c(i)) += 1
    }
 
    var ans: Int = 0;

    // 飴がある地点の計算
    // 飴がある地点はtate+yokoが重複して計算されるので飴の数から1を引く
    // 後で飴がない地点の計算をする際に、
    // tate+yoko=Kとなる地点は、余計にカウントしてしまうのであらかじめansから1を引く
    for (i <- 0 to N - 1) {
      val sum = tate(r(i)) + yoko(c(i)) - 1
      if (sum == K) ans += 1
      else if (sum == K - 1) ans -= 1
    }

    // 全ての地点の計算
    for (x <- 0 to R - 1; y <- 0 to C - 1) {
      val sum = tate(x) + yoko(y)
      if (sum == K) ans += 1
    }
 
    println(ans)
  }
}
  • 上だとTLE。RもCも<=100000だもんね・・・
    • 最初はScalaが遅いんじゃないかと思ってJavaで書き直したりしてた。
    • 解説を見ると考え方は割といい線いっていて、後は飴がi個存在する行/列の数を格納する配列を作ると二重ループが消える
object Main {
  def main(args: Array[String]): Unit = {
    val sc = new java.util.Scanner(System.in)
    val R,C,K = sc.nextInt
    val N = sc.nextInt
    val r, c = new Array[Int](N)
    // tate(x): x行目に存在する飴の数                                                       
    val tate = new Array[Int](R)
    // yoko(y): y列目に存在する飴の数                                                       
    val yoko = new Array[Int](C)
    // tateAme(x): その行に飴がx個存在する行の数                                            
    val tateAme = new Array[Int](N+1)
    // yokoAme(x): その列に飴がy個存在する列の数                                            
    val yokoAme = new Array[Int](N+1)

    for (i <- 0 to N - 1) {
      r(i) = sc.nextInt - 1
      c(i) = sc.nextInt - 1
      tate(r(i)) += 1
      yoko(c(i)) += 1
    }

    for (i <- 0 to R - 1) {
      tateAme(tate(i)) += 1
    }

    for (i <- 0 to C - 1) {
      yokoAme(yoko(i)) += 1
    }

    // Longじゃないとダメでした...
    var ans: Long = 0;

    // 行に飴がi個、列に飴がK-i個存在する行と列の組み合わせを計算
    for (i <- 0 to K) {
      ans += tateAme(i) * yokoAme(K - i)
    }

    // 先の計算だと飴がある地点の計算がずれているので修正
    for (i <- 0 to N - 1) {
      val sum = tate(r(i)) + yoko(c(i))
      if (sum == K) ans -= 1
      else if (sum == K + 1) ans += 1
    }

    println(ans)
  }
}