RubyでABC201(マイナビプログラミングコンテスト2021)のE問題までの解説

最初に

今週あたりは夜9時あたりに寝てたが、
頑張ってAtCoderのABC201ABC201(マイナビプログラミングコンテスト2021)に参加した。

コンテスト中はD問題まで解けて、E問題までACできたので、E問題まで簡単に参加記ないし解説を駆け足で書いていく。

A - Tiny Arithmetic Sequence

a = gets.to_s.split.map{ |e| e.to_i }.sort

puts (a[2] - a[1] == a[1] - a[0]) ? "Yes" : "No"

タブを開きすぎててコンテストに支障がありそうだったから、タブを削除。
ちょっと出遅れたけど、それでも2分ほどで解けたので悪くない。

Rubyにしては入力が冗長なのは、Crystalに移植しやすいようにしている。
そして、入力とともにソート。 昇順でも降順でもソートした数列の差が等しいかを見るだけ。

B - Do you know the second highest mountain?

A問題は数が3つだけで、数値だけのソートで良かった。
B問題は高さを指定して、ソートすると楽。
Rubyではこういうブロックを使うとき、sortではなく、sort_byを使う。
ちゃんと高さをto_iで数値変換した上でsort_byで比較しておかないと、文字列で比較してWAになってしまう。

n = gets.to_s.to_i
m = Array.new(n){ gets.to_s.split }.sort_by{ |name, h| h.to_i }

puts m[-2][0]

to_iを付け忘れる凡ミスで1WAとしてしまい、もったいない。

C - Secret Number

最初に場合分けを考えていたがすごく大変そうでミスしやすそうな解法で、ミスしない自信もなく書くのが大変そうで紙で数式を書いたりしながら考えいた。
考えていたところ、数が全体的に小さいから、全探索などで行けそうだとひらめいた。

s = gets.to_s.chomp

o = s.count("o")
q = s.count("?")

a = ((1..o).to_a + (-q..-1).to_a).repeated_permutation(4).to_a
p a.count{ |d| (1..o).all?{ |e| d.include?(e) } }

これはコンテスト後に、整理して通したコード。

xは使わないので除外して、o?だけに集中して考えると見通しが良い。

何の数字がoqになっているかは重要ではなく、o?の種類の数が重要。
まず、String#countで、数を数える。o?の種類数をoqという変数に置いた。
(1..o).to_a(-q..-1).to_aで、それぞれoを1からoまでの数、qを-qから-1までの数として適当に置き直した。
ここで、o?をそれぞれ正の数と負の数に置き換えたが、元が異なる数字なので、重複しないことが重要。

そのあと、Array#repeated_permutationで4を指定して、o?の数字を使った4文字の暗号を全探索するために全て列挙する。 配列aには、可能性のある全ての暗号が入っている。※最初から可能性のないxは除いている。 この可能性のある暗号の中で、条件に当てはまるものだけをcountで数えていく。 条件にあてはまるかどうかは、all?oの数字が全てつかわれているかを見る。

D - Game in Momotetsu World

こういう感じの必勝法を考えるときは、ゴールから逆算して後ろから考える。
2人で交互に1から3個の連続した数値をいっていって最初に21を言った方が負け、みたいなゲームの必勝法を考えるときも、後ろから考える。
「もしここからスタートしてたらいくつの点差になるか」をゴールから逆算して後ろから考える。

考えながらも雰囲気で解いた感じのところがあるので、嘘解法でない自信がちょっとないが、簡単に解説を書いていく。

右か下に動いていくので、必ず1番右の部分で終わる。ここがゴール。
そして、高橋君と青木君が交互に動かすが、どちらに影響するマスかは市松模様となることがわかる。
i + jの偶奇でわかれる市松模様で、プラスマイナスは逆の意味になる。 つまり、青木君にとっての+-は、高橋君にとっての-+になる。
i + jの偶奇で+-を反転させるとよさそう。 また、+-がポイントに与える影響を考えると、+1, -1となる。
Rubyでは、文字の配列を作ると重たくなることがあり、今回は要素数が多かったので、String#bytesですぐ数値の配列を作りにいっている。
また、^排他的論理和(xor)の演算子であり、これを使うと1-1の振り分けが容易になる。
なお、String#bytesは、バイトの数値(ここでは文字コードと同じ)に変換するメソッドで、'+'43, '-'45に変換される。

自分の実装だと、1行か1列のとき、つまりH == 1 || W == 1のときにコーナーケースとなるようなので、別で実装した。
サンプルにH == 1 && W == 1のケースを置いてくれてありがたい。 H == 1 && W == 1のときは、最初の高橋君が動かせずポイントが変わらないので、"Draw"を出力して即終了。
また、W == 1のときは、transposeで二重配列の縦横を入れ替える等して、H == 1としてまとめて処理するようにした。

先に、1番後ろの列と行から始めるケースだと、両者選択の余地がないので、単純に後ろから累積和を作る要領で、その地点から始めたときのポイント差を求めた。 そして、それ以外のケースでは、高橋君が動かすときは右と下でポイント差を最大化できる方に動くのでmaxメソッドで判定して大きい方を取り、反対に青木君だとポイント差が逆のマイナス方向に動くようにminメソッドで判定して小さい方を取る形で、累積和を求めるようなDPをした。

$debug = false

h, w = gets.to_s.split.map{ |e| e.to_i }

if h == 1 && w == 1
  puts "Draw"
  exit
end

m = Array.new(h){ |i|
  gets.to_s.chomp.bytes.map.with_index{ |e, j|
    ((i + j).even? ^ (e == 43)) ? 1 : -1
  }
}

if h == 1 || w == 1
  m = m.transpose if w == 1
  w = [w, h].max
  h = 1
end

(w - 1).downto(1){ |j| m[-1][j - 1] += m[-1][j] }
(h - 1).downto(1){ |i| m[i - 1][-1] += m[i][-1] }

if h == 1
  puts ["Draw", "Takahashi", "Aoki"][m[0][1] <=> 0]
  exit
end

puts m.map{ _1.join(" ") } if $debug

(h-2).downto(0) do |i|
  (w-2).downto(0) do |j|
    if (i + j).even?
      m[i][j] += [m[i + 1][j], m[i][j + 1]].max
    else
      m[i][j] += [m[i + 1][j], m[i][j + 1]].min
    end
  end
end

puts m.map{ _1.join(" ") } if $debug

mm = [m[0][1], m[1][0]].max
puts ["Draw", "Takahashi", "Aoki"][mm <=> 0]

puts ["Draw", "Takahashi", "Aoki"][m[0][1] <=> 0]
出力のこの部分は、普段はこのように自分は書かないけど、本質に関係ない部分を短くするため、書き直した。 <=>は大小判定で-1, 0, 1を返すメソッドで、配列に3要素のどれかを取る形になる。

実際は、サンプル1で、書きながら考えた。

0 1 2
T A
T A T
A T A

+1だと高橋君に有利なようにポイントが大きくなる。

0 1 2
-1 +1
+1 +1 +1
+1 -1 +1

0 1 2
2 3
-1 2 2
-1 0 1

右下から累積和をとっていく。この表が作れるように頑張る。
(考え方は正しいと思うが、ちょっとやっぱりミスってる気がしてる気が。コーナーケースができるのが変な気がする)

E - Xor Distances

木の問題に苦手意識があって飛ばしてF問題を最初に考えてたが、こっちを頑張った方が良さそうだった。
こっちは、典型問題や過去問の組み合わせで解けるような感じだった。

ある頂点から全ての頂点に対するxorのdistを求める。要素数Nのxorのdistという距離が入った配列を作る。
これは木のBFSやDFSといった典型のやり方で距離を求めるところを、+から^に変えて、xor距離なるものを求めるようにする。

そうすると、xorの二重和というABC147のD - Xor Sum 4という問題に帰着できる。ここ、論理が少し飛躍してるかも。

mod = 10**9 + 7

n = gets.to_s.to_i

g = Array.new(n){ [] }
(n - 1).times do
  s, t, w = gets.to_s.split.map{ |t| t.to_i }
  s -= 1
  t -= 1
  g[s] << [t, w]
  g[t] << [s, w]
end

d = [-1] * n
s = 0
d[s] = 0
q = [s]
while ( v = q.pop )
  t = d[v]
  g[v].each do |(u, c)|
    next if d[u] >= 0
    d[u] = t ^ c
    q << u
  end
end

# ここで、zero based originで0番目の頂点からのxor距離が d に入った。
 
# ABC147 D - Xor Sum 4
ans = (0..60).sum do |i|
  c = d.sum{ |k| k[i] }
  c * (n - c) << i
end

puts ans % mod

ABC147のD - Xor Sum 4に帰着できることは正しいので、最初にこの問題を解けるようになった方がいい。
ABC147のD - Xor Sum 4の解説は、けんちょんさんの解説がわかりやすかった。

最後に

駆け足で書きましたが、ABC201(マイナビプログラミングコンテスト2021)の解説でした。