ABC 349

ABC 349

ABC 349 に参加しました。

A 問題

未知の数 + 既知の数の和 = 0 の等式変形で 未知の数 = -既知の数の和 が分かります。

main=interact$show.(0-).sum.map read.tail.words

B 問題

いかにも accumArray な問題ですが、確かに map length . group . sort を使って解くことができます。

頭が手続き型なので B から C++ にしたけど，やろうと思えばワンライナーでききるにゃんね……
null . filter ( /= 2 ) . map length . group . sort . map length . group . sort

— とーらす🌸📦🌕✨🌂🎧 (@torus711) April 13, 2024

import Data.List
main=interact$(\b->if b then"Yes"else"No").all((==2).length).group.sort.map length.group.sort.init

interact は改行文字を含むため、 init で切り落とします。

C 問題

確かに isSubsequenceOf を使うのが良さそうです。

完全に頭から抜けてたけど Haskell に isSubsequenceOf あるので C はこっちの方が楽だったっぽ

— とーらす🌸📦🌕✨🌂🎧 (@torus711) April 13, 2024

import Data.Char
import Data.List
main=interact$g.f.map (map toLower.reverse).words
f[s,('x':t)]=isSubsequenceOf t s
f[s,t]=isSubsequenceOf t s
g True="Yes"
g _="No"

D 問題

とにかく右へ伸ばす貪欲で解けるようですが、 l = 0 の処理を間違えていました。また \(2^n\) は ^ 演算子で計算して良いとのことで、写経しました。

D はリファクタリングするとこれで OK か
L = 0 の場合を特別扱いしたのが敗因だったな
教訓: 慌ててそういう横着してはいけない pic.twitter.com/fW2zGECcS5

— naoya (@naoya_ito) April 13, 2024

main=interact$(\x->unwords.map show$(length x-1:).concat$zipWith(\a b->[a,b])x(tail x)).h.map read.words
n j r 0=(2^).last$takeWhile((<=r).(2^))j
n j r l=(\x->if x==[]then r+1 else l+2^last x)$takeWhile(\i->l+2^i<=r&&l`mod`2^i==0)j
h[l,r]=takeWhile(<=r)$iterate(n[0..]r)l

E 問題

ゲームの問題です。ゲーム DP の基本を思い出して解きます。

枝刈りしなくても通る成約なので、愚直に解くことができます。逆に、不要な処理を追加しないことが重要な問題でした。