AtCoder ABC310 解法(A ~ E) Ruby & Kotlin

解法

A - Order Something Else

公式解説

Difficulty	Solve Prob	Solve Time
23	> 99 %	4 mins

Ruby

abc310_a.rb

N, P, Q = gets.split.map(&:to_i)
D = gets.split.map(&:to_i)
puts [D.min + Q, P].min

Kotlin

abc310_a.kt

fun main() {
  val (N, P, Q) = readLine()!!.split(" ").map(String::toInt)
  val D = readLine()!!.split(" ").map(String::toInt)
  println(Math.min(P, D.min()!! + Q))
}

B - Strictly Superior

公式解説

Difficulty	Solve Prob	Solve Time
226	96 %	19 mins

Ruby

abc310_b.rb

N, M = gets.split.map(&:to_i)
# あらかじめjの候補を昇順で並び替えて置く
# Pi >= Pj && Ci <= Cj となる順
PCF = Array.new(N) { gets.split.map(&:to_i) }.sort_by { [_1[0], -_1[1]] }

N.times do |j|
  (j + 1).upto(N - 1) do |i|
    pj, cj, *fj = PCF[j]
    pi, ci, *fi = PCF[i]
    # fiとfjの和集合の数がfjの数を超える場合、上位互換になり得ない
    next if (fi | fj).size > cj
    if pi > pj || ci < cj
      puts "Yes"
      exit
    end
  end
end
puts "No"

Kotlin

abc310_b.kt

fun main() {
  val (N, M) = readLine()!!.split(" ").map(String::toInt)
  val PCF = MutableList(N) { readLine()!!.split(" ").map(String::toInt) }

  // あらかじめjの候補を昇順で並び替えて置く
  // Pi >= Pj && Ci <= Cj となる順
  PCF.sortWith(compareBy({ it[0] }, { - it[1] }))

  for (j in 0 .. N - 2) {
    for (i in j + 1 .. N - 1) {
      val pj = PCF[j][0]
      val cj = PCF[j][1]
      val fj = PCF[j].subList(2, PCF[j].size).toSet()
      val pi = PCF[i][0]
      val ci = PCF[i][1]
      val fi = PCF[i].subList(2, PCF[i].size).toSet()

      // fiとfjの和集合の数がfjの数を超える場合、上位互換になり得ない
      if (fj.union(fi).size > cj) continue
      if (pi > pj || ci < cj) {
        println("Yes")
        return
      }
    }
  }
  println("No")
}

C - Reversible

公式解説

Difficulty	Solve Prob	Solve Time
272	95 %	11 mins

Ruby

abc310_c.rb

require "set"
N = gets.to_i

set = Set.new
N.times do |i|
  s = gets.chomp
  # 前後反転した文字列と元の文字列を配列で並べ、
  # ソートした後に文字列にする。
  # これにより、"abc"と"cba"を同一とみなせる。
  set << [s, s.reverse].sort.join
end

puts set.size

Kotlin

abc310_c.kt

fun main() {
  val N = readLine()!!.toInt()
  val S = mutableSetOf<String>()

  repeat(N) {
    val s = readLine()!!
    // 前後反転した文字列と元の文字列を配列で並べ、
    // ソートした後に文字列にする。
    // これにより、"abc"と"cba"を同一とみなせる。
    S.add(listOf(s, s.reversed()).sorted().joinToString(""))
  }
  println(S.size)
}

D - Peaceful Teams

公式解説

深さ優先探索（DFS)

Difficulty	Solve Prob	Solve Time
1368	11 %	38 mins

Ruby

abc310_d.rb

N, T, M = gets.split.map(&:to_i)
HATE = Array.new(N + 1) { [] }

M.times do
  a, b = gets.split.map(&:to_i).map(&:pred)
  HATE[a] << b
  HATE[b] << a
end

# i 番目の選手(0 <= i < N)
# teamsは各チームの配列の配列
def dfs(i, teams)
  if i == N
    # チーム数がTとなっていた場合条件を満たすためカウント
    return teams.size == T ? 1 : 0
  end
  cnt = 0

  # 既存チームにi番目の選手を追加する場合
  teams.each_with_index do |t, j|
    # tの選手の中にi番目の選手と相性が悪い選手がいた場合は除外
    next if (t & HATE[i]).size > 0
    teams_copy = teams.map { _1.clone }
    teams_copy[j] << i
    cnt += dfs(i + 1, teams_copy)
  end

  # 新たなチームを作りi番目の選手を追加する場合
  cnt += dfs(i + 1, teams + [[i]]) if teams.size < T
  cnt
end

puts dfs(1, [[0]])

Kotlin

abc310_d.kt

fun main() {
  // kotlinでは再帰DFSはすぐにスタックオーバーフローするので記述
  // この問題ではこの方法を使用しなくてもACできる
  Thread(null, ::solve, "solve", 1.shl(26)).start()
}

fun solve() {
  val (N, T, M) = readLine()!!.split(" ").map(String::toInt)
  val HATE = MutableList(N) { mutableListOf<Int>() }
  repeat(M) {
    val (a, b) = readLine()!!.split(" ").map(String::toInt)
    HATE[a - 1].add(b - 1)
    HATE[b - 1].add(a - 1)
  }

  /**
   * i 選手の番号(0 <= i < N)
   * teams チームの配列の配列
   * 場合の数
   */
  fun dfs(i: Int, teams: MutableList<MutableList<Int>>): Int {
    if (i == N) {
      // チーム数がTとなっていた場合条件を満たすためカウント
      return if (teams.size == T) 1 else 0
    }
    var cnt = 0

    // 既存チームにi番目の選手を追加する場合
    teams.forEachIndexed { j, team ->
      // teamの選手の中にi番目の選手と相性が悪い選手がいた場合は早期リターン
      if ((team.intersect(HATE[i])).size > 0) return@forEachIndexed
      val teamsCopy = teams.map { it.toMutableList() }.toMutableList()
      teamsCopy[j].add(i)
      cnt += dfs(i + 1, teamsCopy)
    }

    // 新たなチームを作りi番目の選手を追加する場合
    if (teams.size < T) cnt += dfs(i + 1, teams + mutableListOf(mutableListOf(i)))

    return cnt
  }

  println(dfs(1, mutableListOf(mutableListOf(0))))
}

E - NAND repeatedly

公式解説

Difficulty	Solve Prob	Solve Time
1261	16 %	37 mins

Ruby

abc310_e.rb

N = gets.to_i
S = gets.chomp.chars.map(&:to_i)

# f(0, j) ... f(j - 1, j)の中で、
# zero = fが0である場合の数
# one = fが1である場合の数 = f(0, j) + ... + f(j - 1, j)
ans = zero = one = 0

S.each do |i|
  if i.zero?
    # zeroとなるのは、f(i, i) = 0 ⊼ 0 の場合
    # oneとなるのは、0 ⊼ 0 と 1 ⊼ 0 の場合
    zero, one = 1, zero + one
  else
    # zeroとなるのは、1 ⊼ 1 の場合
    # oneとなるのは、0 ⊼ 1 と f(i, i) の場合
    zero, one = one, zero + 1
  end
  ans += one
end

puts ans

Kotlin

答えは$10^9$を超えるためLong型

abc310_e.kt

fun main() {
  val N = readLine()!!.toInt()
  val S = readLine()!!.toList()

  var ans = 0L
  // f(0, j) ... f(j - 1, j)の中で、
  // zero = fが0である場合の数
  // one = fが1である場合の数 = f(0, j) + ... + f(j - 1, j)
  var zeroOne = Pair(0L, 0L)

  S.forEach {
    if (it == '0') {
      // zeroとなるのは、f(i, i) = 0 ⊼ 0 の場合
      // oneとなるのは、0 ⊼ 0 と 1 ⊼ 0 の場合
      zeroOne = Pair(1L, zeroOne.first + zeroOne.second)
    } else {
      // zeroとなるのは、1 ⊼ 1 の場合
      // oneとなるのは、0 ⊼ 1 と f(i, i) の場合
      zeroOne = Pair(zeroOne.second, zeroOne.first + 1L)
    }
    ans += zeroOne.second
  }
  println(ans)
}

その他のAtCoder関連の解法コード

参考