せんべい問題を見た感想

.md

積の符号

ジャブみたいな問題だ

$0$ の個数と負の数の個数をそれぞれ数えて

• $0$ がある→ 0
• 負の数が奇数個→ -
• それ以外→+

N = gets.to_i
A = gets.split.map(&:to_i)

if A.any?(0)
  puts "0"
elsif A.count { _1 < 0 }.odd?
  puts "-"
else
  puts "+"
end

ABC の個数

これが 2 問目とはレベル高いな

2 つ前まで見る DP

ステートマシンをつくると見通しがよいかも

• 0: A -> 1, B -> 0, C -> 0
• 1: A -> 1, B -> 2, C -> 0
• 2: A -> 1, B -> 0, C -> 0 (+1)

S = gets.chomp
dp = [1.0, 0.0, 0.0]
ans = 0.0
inv3 = 1.0/3
S.each_char do |c|
  dp2 = [0.0] * 3
  case c
  when ?A
    dp2[1] += dp[0] + dp[1] + dp[2]
  when ?B
    dp2[0] += dp[0] + dp[2]
    dp2[2] += dp[1]
  when ?C
    dp2[0] += dp[0] + dp[1] + dp[2]
    ans += dp[2]
  when ??
    dp2[0] += (dp[0] * 2 + dp[1] + dp[2] * 2) * inv3
    dp2[1] += (dp[0] + dp[1] + dp[2]) * inv3
    dp2[2] += dp[1] * inv3
    ans += dp[2] * inv3
  end
  dp = dp2
end

puts ans

距離 K

UnionFind で距離が K の要素をつなぎあわせる→それぞれの連結成分ごとに並べ替えの個数を求める 並べ替えの個数は $\frac{要素数!}{\Pi_x (要素 x の個数)!}$

MOD = 119<<23|1

N, K = gets.split.map(&:to_i)
A = gets.split.map(&:to_i)

components = Array.new(N) { [_1] }
(0 ... N - K).each do |i|
  j = i + K
  next if i == j
  x, y = components[i], components[j]
  x, y = y, x if x.size < y.size
  y.each do |v|
    components[v] = x << v
  end
end

factorial = [1] * (N + 1)
(2 .. N).each do |i|
  factorial[i] = factorial[i - 1] * i % MOD
end

ans = 1
components.uniq(&:object_id).each do |component|
  div = 1
  component.map { A[_1] }.tally.each do |_, count|
    div = div * factorial[count] % MOD
  end
  ans = ans * factorial[component.size] % MOD * div.pow(MOD - 2, MOD) % MOD
end

puts ans

トリオ

各チーム（第１回）について、まだどのチーム（第２回）にも選ばれていない人数を考える。 そして、その数ごとにチーム数を集計し、 $(n_1, n_2, n_3)$ とする。（ $n_k$: 選ばれていない人が $k$ 人いるチームの個数）

これを状態として、遷移は第１回のチームを３つ、各チームから１人ずつ選んで第２回のチームを結成することを遷移とする。

遷移 ($a + b + c = 3$）

• $(i, j, k) \to (i - a + b, j - b + c, k - c) \times \binom{i}{a} \binom{j}{b} \binom{k}{c} 2^b 3^c$

N, M = gets.split.map(&:to_i)

# dp[i][j][k] = 1人チーム×i、2人チーム×j、3人チーム×kである場合の数
dp = Array.new(N + 1) { Array.new(N + 1) { [0] * (N + 1) } }
dp[0][0][N] = 1
binom = ->(n, k) {
  case k
  when 0
    1
  when 1
    n
  when 2
    n * (n - 1) / 2
  when 3
    n * (n - 1) * (n - 2) / 6
  end
}
trans = [[3, 0, 0], [2, 1, 0], [2, 0, 1], [1, 2, 0], [1, 1, 1], [1, 0, 2], [0, 3, 0], [0, 2, 1], [0, 1, 2], [0, 0, 3]]
trans.each do |a, b, c|
  (c .. N).reverse_each do |k|
    (b .. N - k).reverse_each do |j|
      (a .. N - j - k).reverse_each do |i|
        x = dp[i][j][k]
        next if x == 0
        y = x * binom[i, a] % M * binom[j, b] * 2**b % M * binom[k, c] * 3**c % M
        dp[i - a + b][j - b + c][k - c] += y
        dp[i - a + b][j - b + c][k - c] %= M
      end
   end
  end
end

puts dp[0][0][0] % M