ABC 365, Segment Tree Beats!

ABC 365

ABC 365 に参加しました。 2 完灰パフォの悪夢が夢で良かったです。

今夜の ARC に出るか迷っています。レーティングって下がるのは一瞬ですが、上げるのは数ヶ月かかりますものね。

A 問題

cojna さんが流石で、 Data.Time.Calendar に isLeapYear (閏年の判定関数) がありました。

import Data.Time.Calendar;main=print.f=<<readLn;f x|isLeapYear x=366|0<1=365

B 問題

ソートして 2 番目に大きい数を抜き出すのが良さそうですね。

import Data.List;main=interact$show.snd.last.init.sort.(`zip`[1..]).tail.map (read @Int).words

タプル同士は左端のキーから順に比較されるため、 zip[1..] ではなく (`zip`[1..]) としました。

C 問題

2 分探索の問題でした。判定問題を決めて \(O(N \log N)\) で解けました。灰 diff だと……？！

D 問題

直前の手 (R, P, S) 毎に最大の勝利回数を持って畳み込みします。畳み込みで解ける DP は茶 diff 典型ですね。

貪欲法では解けない考察 が抜けていました。競プロ以外では、意図せず嘘貪欲を使ってしまうケースの方が多そうです。

E 問題

初め、 xor ではなく or だと思って架空の問題を解いてしまいました。取り返せて良かった。

F 問題

合成できないやつだと思って飛ばしました。 PAST にも似た問題があって解けなかった記憶があります。 やはり PAST か……！

G 問題

別解のマージテク (?) で解いてみたいです。長い区間の処理が大変そうです (座標圧縮と累積和で一括計算する？) 。

以上

手抜きですが ABC 振り返りでした。提出が汚いので、あまり振り返りたくないです ()

Segment Tree Beats!

maspy さんのライブラリを読み解き、区間 chmin/chmax が扱える特殊なセグメント木を実装しました。命名の元ネタは Angle Beats! らしい です。

主なメモは Zeen スクラップ に置いています。以下ではアルゴリズム以外の部分をメモします。

コードの重複

遅延セグメント木と Beats でコードが重複しています。実装の共通化のため、 セグメント木のための型クラスを特別に用意 した方が良い気がしてきました。

多相なフィールドは {-# UNPACK #-} できない

Haskell の多相は特殊化されず、動的な実装になることが多いです。関数もそうですが、レコードでも起こります。

多相化されたフィールドは {-# UNPACK #-} できません:

data AddChminChmax a = AddChminChmax
  { addACC :: !a,
    chminACC :: !a,
    chmaxACC :: !a
  }
  deriving (Show, Eq)

これを特殊化すると box 化が消えて高速になるようです:

data AddChminChmaxInt = AddChminChmaxInt
  { addACCInt :: {-# UNPACK #-} !Int,
    chminACCInt :: {-# UNPACK #-} !Int,
    chmaxACCInt :: {-# UNPACK #-} !Int
  }
  deriving (Show, Eq)

これは C++ の方が速いのも仕方ありません。パフォーマンスは諦め気味です。

Misc

Fortran

yum さんこと MrTired が 新しいランダムキャラ (ギャンブラー猿) を追加してくれました。

!> This file was processed by `fypp`.
!> Today's fortune: "Lucky WA", really OK?
!> ランダムウォーク猿「'半分全列挙' で はっぴー.」
!> ギャンブラー猿「AtCoder はゲームだ.」

僕は みんなの Fortran を読んでいます。僕の中の難解言語ランキングは Prolog > Batch Script > Emacs Lisp > Haskell だったわけですが、 Fortran は 2 位になるかもです。

Emacs

SNS で共有のあった org-sliced-images が良かったです。 (org-mode に限り) 画像を visual 行単位でカーソル移動・スクロールできます。