猫でもわかるWebプログラミングと副業

本業エンジニアリングマネージャー。副業Webエンジニア。Web開発のヒントや、副業、日常生活のことを書きます。

AtCoder Beginner Contest #024

今回は可能な限りScalaで参加しました。

A - 動物園

import java.util.Scanner
 
object Main {
  def main(args: Array[String]): Unit = {
    val sc = new Scanner(System.in)
    val a = sc.nextInt()
    val b = sc.nextInt()
    val c = sc.nextInt()
    val k = sc.nextInt()
    val s = sc.nextInt()
    val t = sc.nextInt()
    if(s + t >= k){
      println((a-c) * s + (b-c) * t)
    }else{
      println(a * s + b * t)
    }
  }
}

B - 自動ドア

object Main {
  def main(args: Array[String]): Unit = {
    val sc = new Scanner(System.in)
    val n = sc.nextInt()
    val t = sc.nextInt()
    var close_time = 0;
    var ans = 0;
    for(i <- 1 to n){
      val a = sc.nextInt()
      ans = ans + Math.min(t, a + t - close_time)
      close_time = a + t
    }
    println(ans)
  }
}

var を使わない場合

Scala関数型言語なので、varを使わずにvalだけを使い、関数の末尾再帰で解こうとしたら、REになったのでスタックオーバーフロー…?

import java.util.Scanner
 
object Main {
  val sc = new Scanner(System.in)

  def main(args: Array[String]): Unit = {
    val n = sc.nextInt()
    val t = sc.nextInt()
    println(solve(n, t, 0))
  }
  
  def solve(n: Int, t: Int, close_time: Int): Int = {
    if(n == 0){
      0
    }else{
      val a = sc.nextInt()
      Math.min(t, a + t - close_time) + solve(n-1, t, a + t)
    }
  }
}

C - 民族大移動

int main(int argc, const char * argv[]){
    int n, d, k, l[10000], r[10000], s[100], t[100];
    cin >> n >> d >> k;
    REP(i,d) cin >> l[i] >> r[i];
    REP(i,k) cin >> s[i] >> t[i];
    
    int ans[100];
    REP(i,k) ans[i] = d;
    
    REP(i,d){
        REP(j,k){
            if(ans[j] != d) continue;
            if(l[i] <= s[j] && s[j] <= r[i]){
                if(l[i] <= t[j] && t[j] <= r[i]){
                    ans[j] = min(ans[j], i+1);
                }else if(s[j] < t[j]){
                    s[j] = r[i];
                }else if(t[j] < s[j]){
                    s[j] = l[i];
                }
            }
        }
    }
    
    REP(i,k) cout << ans[i] << endl;
}

D - 動的計画法 *1

  • 数式をこねこねする問題
  • modの扱いにだけ気をつける
  • 109 + 7 は素数である

結果

  • 飲み会が9時に終わり、そこから帰宅しながら&帰宅してから解いたので順位はひどかった
  • A, B は電車の中で解き、C は家に帰ってから解いた
  • D は数式をいじってる間に終わった

f:id:yoshiki_utakata:20150523233942p:plain

*1:動的計画法の問題かと思ったら違った