ABC 363

ABC 363

ABC 363 に参加しました。回分回でした。爆死された方が多かったようです。

A 問題

$A$ を 100 の倍数に切り上げたとき、元の数よりどれだけ大きくなるか。 $100 - a\%100$ で解けます。

main=print.((100-).(`mod`100))=<<readLn

B 問題

愚直テストを 2 分探索しました。

今考えると、降順ソートして前から P 番目の人に注目するのが良さそうです。

import Data.List;main=interact$show.f.map read.words;f(n:t:p:l)=max 0$t-sort l!!(n-p)

よくあるソートは $O(N \log N)$ ですが、 selectBy を使えば $O(N)$ で解けるそうです？　CS をやった人ならピンと来るかもしれません。

そういえば　Data.Vector.Algorithms.Intro.selectBy を使うとABC363-BはO(N) で解けますね

— 符号/gksato (@Fine_sugar_hill) July 20, 2024

C 問題

$O(N \cdot N!)$ が通るため、すべての (ユニークな) 順列を全探索します。 vector の nextPermutation で解けそうですね。

実際は TLE します。 2014 年の TODO が原因だったので、 vector に PR を投げました 。

ちなみにstrictness analysisでうまくいかないのは一般のPrimMonad だからっぽいので、そこにbang patternを突っ込む代わりに 処理開始時に stToPrim を噛ませても解決します:https://t.co/trLQ7ZvTX2

— 符号/gksato (@Fine_sugar_hill) July 21, 2024

stToPrim でさらに速くなります。型クラスを使うと遅くなる (*) ので、モナドのインスタンスを ST に確定させた方が速いんですね。勉強になりました。

(*): 正確性解析や辞書渡しが原因

辞書順列を列強する lexPerm で upsolve しました。本来は軽い問題ですね。

  -- p の定義は省略
  printBSB $ V.length $ V.filter p $ lexPerms xs

D 問題

難しくないですか？　考察中です。

E 問題

ヒープで解きます。 cojna さんの BinaryHeap は最高だぜの問題でした。

Misc

ビルド環境の改善

自作ライブラリを Main.hs に埋め込むのを止め、外部ライブラリとして参照する形に変更しました。例: 直近の Main.hs, 提出 (埋め込み) 。

プロジェクトファイルはこんな感じです:

packages:
  ./abc363.cabal
  -- 絶対パス (仮)
  ~/dev/hs/toy-lib/toy-lib.cabal

constraints: (
  -- debug ログ ON
  toy-lib +debug

common deps
  build-depends:
    , adjunctions                    ^>=4.4.2
    -- ~~
    , toy-lib
    -- ~~

提出直前にライブラリを埋め込んで .submit.hs を作成します。提出ファイルも変更しました:

{
    "task": {
        "program": [
            "Main.hs"
        ],
        "submit": ".submit.hs"
    }
}

初回ビルドが遅いので、 Nix か何かでビルドキャッシュを共有したいところです。

コンテスト用コードの短縮

全ライブラリの埋め込みを止め、指定モジュールのみ埋め込むことにしました。 Haskell longest コードゴルフ王者、引退です。

-- {{{ toy-lib import
import ToyLib.Contest.Prelude
-- import ToyLib.Contest.Bisect
-- import ToyLib.Contest.Graph
-- import ToyLib.Contest.Grid
-- import ToyLib.Contest.Tree
import ToyLib.DP
-- }}} toy-lib import

いずれ使用モジュールのみ自動的に埋め込むようにしたいです。