This article is not translated into English yet. Below is the Japanese original.

ABC 391, 関数の特殊化

ABC 391

ABC 391 に参加しました。

問題A 問題B 問題C 問題D 問題E 問題F 問題
提出ACACACACACTLE
予想 diff101004001,3001,0001,800
実際 diff101102099241,1651,534
Table 1: Diff 予想

A 問題

八方位が N, NE, E, .. の形式で与えられる。反対方向を出力せよ。

八方位を配列に入れれば、添字 ii を i+4(mod8)i + 4 \pmod 8 すれば良いです:

dirs :: [String]
dirs = ["N", "NE", "E", "SE", "S", "SW", "W", "NW"]

solve :: StateT BS.ByteString IO ()
solve = do
  !s <- BS.unpack <$> line'
  let i = fromJust $ elemIndex s dirs
  printBSB $ dirs !! ((i + 4) `mod` 8)

天才解法は文字列置換です:

tr NESW SWNE # bash

B 問題

2 つの長方形が与えられたとき、模様がマッチする部分を答えよ。例によって 2 次元配列のテンプレートを使います:

solve :: StateT BS.ByteString IO ()
solve = do
  (!n, !m) <- ints2'
  !s <- getGrid' n n
  !t <- getGrid' m m

  -- s 上の (i, j) に t を置いたとき、模様が一致するか判定する
  let test i j = and [s @!? (i + dy, j + dx) == Just (t @! (dy, dx)) | dy <- [0 .. m - 1], dx <- [0 .. m - 1]]
  -- すべての (i, j) を試す
  let (!y, !x) = head [(y, x) | y <- [0 .. n - 1], x <- [0 .. n - 1], test y x]
  printBSB (y + 1, x + 1)

C 問題

配列の上を要素が移動するとき、要素のダブりがあるスロットの数を追跡せよ。

可変配列が要求されて辛い問題でした。クエリは mapMaybeM で処理しました。

D 問題

テトリスのシミュレーション時に、 tit_i 秒後に 1x1 サイズの正方形 AiA_i が消滅していないか答えよ。 xx 座標毎に ii 番目のブロックの位置を求め、 ii 番目の位置のブロックの max を計算します。 naoya さんの tranpose による実装 が綺麗でした。

E 問題

3 分木を再帰的に畳み込め。と読解できればボトムアップで解けました。

まず Vector を 3 要素ずつに分解します:

chunks3 :: (U.Unbox a) => U.Vector a -> V.Vector (U.Vector a)
chunks3 xs = V.unfoldrExactN (G.length xs `div` 3) (G.splitAt 3) xs

ノードには (多数決の結果, 結果反転の最小コスト) を載せます:

reduce :: U.Vector (Int, Int) -> U.Vector (Int, Int)
reduce = V.convert . V.map eval . chunks3
  where
    eval xs = {- .. -}

n 回 reduce して解答します。

F 問題

ヒープで TLE, 検討中です。ヒープの実装が遅いってことも無いと思うのですが。

Misc

INLINE 以外の信じられるもの

Haskell は 1 行の差で 10 倍遅くなることで有名な言語です。特にモジュールを跨ぐ場合には、 pragma 無しだと低速になること必至! しかし link/cut tree の関数は巨大で、すべてを INLINE 化するとコンパイルに失敗しました。 INLINE 無しだと C++ の 10 倍遅いので、対策が必須です。

この件を toyboot4e/lct-bench で質問したところ、 INLINABLE を付けて 10 倍高速化して頂きました。モジュールをまたぐ場合は、 INLINABLE を付けなければ関数の特殊化が行われず PrimMonad が辞書渡しになり、非常に低速となる模様です。

(おそらく) これを機に HaskellのPrimMonadとうまく付き合う その1 が執筆されました。自分でも色々試した感じ、 INLINE の方が INLINEABLE よりも高速な傾向にあります。

NoモナドpragmastToPrimST/IOモナドスタック判定
1PrimMonad--遅い遅い絶対ダメ!
2PrimMonadINLINE-速いやや遅い良し
3PrimMonadINLINEstToPrimやや遅い速い良し
4PrimMonadINLINEABLE-やや遅い遅い絶対ダメ!
5PrimMonadINLINEABLEstToPrimやや遅いやや遅い良し

業務ならコンパイルの速い No 5 が良さそうです。 PrimMonad (型クラス) を特殊化しつつ、コンパイル時間も肥大しません。速度優先なら INLINE 指定の No 2 か No 3 が良さそうです。

vector-algorithms 高速化

vector-algorithms の nub, sort 等が低速な件で PR を出しました。 ベンチマーク を取りましたし、 Core もチラ見しています。要は INLINE の方が速いというだけの内容です。

Magit が動かない?

magit-file-icons に Issue を立てました。 git bisect が便利で、 git bisect run 'rg' 'magit-insert-files-1' が全てやってくれました。修正はオーナーにお願いしたいです。たぶんフック先を変えるだけだと思うのですが。

競プロ用の flake.nix

atcoder-cli と oj-verify を Nix 経由で入れられるようになりました。 Source は nvfetcher で取ったほうが更新が楽かも。

flake.nix
{
  description = "A basic flake with a shell";

  inputs = {
    nixpkgs.url = "github:NixOS/nixpkgs/nixpkgs-unstable";
    flake-utils.url = "github:numtide/flake-utils";
  };

  outputs =
    { nixpkgs, flake-utils, ... }:
    flake-utils.lib.eachDefaultSystem (
      system:
      let
        pkgs = import nixpkgs { inherit system; };
        # https://github.com/lmdexpr/contest/blob/d7d7e84034cf1ce6e54a59ffb0435e5edafa873e/flake.nix#L83C1-L95C11
        atcoder-cli = pkgs.buildNpmPackage {
          pname = "atcoder-cli";
          version = "2.2.0";
          src = pkgs.fetchFromGitHub {
            owner = "Tatamo";
            repo = "atcoder-cli";
            rev = "f385e71ba270716f5a94e3ed9bd23a24f78799d0";
            sha256 = "sha256-7pbCTgWt+khKVyMV03HanvuOX2uAC0PL9OLmqly7IWE=";
          };
          npmDepsHash = "sha256-ufG7Fq5D2SOzUp8KYRYUB5tYJYoADuhK+2zDfG0a3ks=";
          npmPackFlags = [ "--ignore-scripts" ];
          NODE_OPTIONS = "--openssl-legacy-provider";
        };
        oj-verify =
          with pkgs.python3Packages;
          pkgs.python3Packages.buildPythonApplication {
            name = "verification-helper";
            version = "5.6.0";
            pyproject = true;
            src = pkgs.fetchFromGitHub {
              owner = "online-judge-tools";
              repo = "verification-helper";
              rev = "adbff121b1f96de5f34e9f1483eb47d661c54075";
              fetchSubmodules = false;
              sha256 = "sha256-f7Ge8kLRQv9uxdNGtgNsypGVY0XAnKPCg8HYQ5nT6mI=";
            };
            build-system = [ setuptools ];
            dependencies = [
              colorlog
              importlab
              online-judge-tools
              pyyaml
              setuptools
              toml
            ];
            propagatedBuildInputs = [ setuptools ];
          };
      in
      {
        devShells.default =
          with pkgs;
          mkShell {
            packages = [
              atcoder-cli
              online-judge-tools
              oj-verify
            ];
          };
        shellHook = ''
          acc config oj-path $(which oj)
        '';
      }
    );
}

参考:

キーボード

Dilemma キーボードが格好いい。自分でパーツを集めなくても Kit の販売があるので、発注してみました。発送待ちです。

音楽

Behemoth の新盤が 5 月に出ます。やった!

メロディック・ブラックメタル・ガイドブック をぺらぺらと見ています。 Sworn が載っていて嬉しい。 Bliss of Flesh も一瞬出てきましたが、本当に一言しかコメントが無くて無常を感じます。もう少し予算があれば紙面を割けそうです。

音楽は消化が難しく、 1 月あたり 1 バンド未満のペースで聴いています。最近は INANNA が良い感じです。