ぶていのログでぶログ

思い出したが吉日

AtCoder Beginner Contest 295(ABC295)に参加した

Ruby ABC AtCoder

先週にに引き続き今週も参加。

atcoder.jp

私の回答

atcoder.jp

C問題までACしたがD問題でTLEした。 以下感想。

A - Probably English

雑に puts gets.match(/and|not|that|the|you/) ? "Yes" : "No" みたいなコードを書いたら見事WAした 😂 単語を分割して規定の単語が含まれるかチェックするようにしてACしたが、よくよく考えたらregexのメタ文字 \b を使えばよいだけだった…

_n = gets
puts gets.match(/\b(and|not|that|the|you)\b/) ? "Yes" : "No"

B - Bombs

最初は高速化を狙って盤面をビット列に見たてて解こうとしたがうまく書けず…結局盤面の大きさもそこまで大きくないこともあって、二次元配列を作って解いた。作り直しに無駄な時間がかかってしまったので、最初から二次元配列でやればよかった。

D - Three Days Ago

嬉しい列の条件が同じ文字が偶数個出てくるというところまではすぐにひらめいた。しかし、どうやってそれをプログラムに落とし込むのがいいのか悩んだ。私が思いついた案では、2の倍数長で文字列を切り出してソートし、それを2個ずつに分割し同じであることをチェックしようとした。具体的には以下のような感じ。

s.length.times do |i|
  ((s.length - i)/ 2).times do |j|
    l = (j + 1) * 2
    count += 1 if s.slice(i, l).sort.each_slice(2).all? { |(a, b)| a == b }
  end
end

案の定というかTLEした。メモ用のハッシュを作ったり、特定のパターンをハッシュしたり、正規表現を使ったりもしたが、そもそもO(n2)になってそうでどれもダメだった。

解説を読んでZobrist hashingと累積和を知ったので次回から活用していきたい。

余談だが、解説を読んで解説のコードを読んだのだが突然でてくる res+=(x*(x-1))/2; が最初理解できなかった…。 どういう意味なのかものすごく考えたのだが、結論組み合わせだった。xC2をやっているのであった。