ABC 329

競技プログラミング

Keyball 44 で寿司打をやっていた。僕は何を‥‥

ミスせずタイピングを継続すると、追加でボーナス時間が与えられる。このためタイプミスを大幅に減らす訓練になった。現在のスコアは 30 皿 12,000 円を安定して超える程度。あまり速くないみたい。

ABC 329 に参加した。寿司打をやった意味があるほどタイピングしなかった。

A 問題ではお手本のような手続き型プログラミングを行った。酷いよ。

main :: IO ()
main = do
  !s <- BS.getLine
  forM_ (BS.unpack (BS.init s)) $ \ch -> do
    putChar ch
    putChar ' '
  putChar (BS.last s)

B 問題では降順ソートして uniq を取ったら 2 番目の要素が答えとなる。

C 問題は U.accumulate で解いた。 U.accumulate の引数は U.accumulate op initialVec commands という形で accumArray とやや異なる。

D 問題ではヒープを使ってしまったが、最大値を持って mapAccumL すれば良かった。セグメント木に Max (Int, Down Int) を載せると、区間クエリの問題であっても対応できるとのこと。なるほど。

E 問題では時系列を遡ると貪欲に解ける。すなわち元の文字列に対して # を塗っていくと、 # で覆った部分は上書きされるようになるため、 # になった箇所はワイルドカードであると見做せる。

後は一度塗った箇所の近辺を再度見直すために、キューやスタックを使用する。この辺のディテールも実装力ということか。

タイムラインでは、左右に 1 回ずつ走査すれば良いのではないかという解法が流れてきた。実に ARC 的な解答だ。

gksato 氏の提出においては可変配列が出現せず、 DP で解いている。ビット列を持って scanl した後に tail と last を見ているが……？　まだ基本的なアイデアを読み取れていない。

F 問題では ABC 279 F からの連想で union-find を使ってしまい失敗した。 Set を使うと指示通りシミュレーションするだけとなった。

F 問題でよく聞くマージテクとは、 union-find における union by rank とか union by size と同じ話で、極端にバランスの崩れた木を作らないように工夫することが、最悪計算量を均すことに繋がる。

なお Set においてはマージテクが自動適用される (たぶん) ほか、 IntSet は深さ 64 の完全二分木を圧縮した形であるため、あまり Haskell では使わないテクニックかもしれない。

茶色コーダーを目指すための tips からはかけ離れてきた。すべて載せるスタイルに方向展開したい。

カンファレンスをやっていたみたい。楽しそうでいいな。