ABC 341 / ACL contest

ABC 341

ABC 341 に参加しました。早解き回にて 6 完青パフォ！　同時期に入水した人たちと同程度のレーティングになりました。嬉ピクミンの宴です。

A - Print 341

1010 .. 1 のような文字列を生成します。 kotatsugame さん情報によると、 341 = 101010101 (2) のようでした。すご……

-- 上手い方法
take (2 * n + 1) $ cycle "10"

-- 思いつきやすかった方法
init . concat $ replicate (n + 1) "10"

B 問題

畳み込みの問題です。焦って手続き的にやってしまいました。いつものことですが、 gksato さんの提出が上手かったです。

kotatsugame さん情報によると \(T_i \le S_i\) のため通貨が指数関数的に膨れ上がることはありません。重要な考察ですね (抜けていました) 。

C 問題

全探索の問題です。すべてのセルを起点にシミュレーションすれば解けます。

制限時間がシビアなため、 Haskell ではサンクを溜めると TLE になるようです。僕は即 break できるように再帰関数を使っていました。

Listing 1: シミュレーション (再帰関数で break)

let solve (!y, !x) !bs = case BS.uncons bs of
      Nothing -> True
      Just (!dir, !bs') ->
        if not (inRange (boundsIV gr) yx') || gr @! yx'
          then False
          else solve yx' bs'
        where
          !yx' = add2 (y, x) (toD dir)

Listing 2: 全セルの座標の生成 (vector)

U.generate (h * w) (`divMod` w)

kotatsugame さん情報によると、終点の位置を数える問題だったようです。僕は始点の位置を数えてしまいました。単射で助かりました。

D 問題

算数を考えていましたがサンプル 3 で TLE. 2 分法で効率化できました。なるほど……！

めぐる式 2 分探索はフォルシアの記事の図解が一番分かりやすかったです。

E 問題

前回の E 問題で遅延セグメント木が出題されたこともあり、躊躇なく使用しました。が、勇み足だったようです。セグメント木 1 本で通ります。

前回の E は緑 diff で、今回の E は水 diff でした。教えはどうなってんだ教えは！

F 問題

高い所から低い所まで水が降りていくような問題でした。低いところから順番に解を求めます。部分問題はナップサック問題です。

青 diff にしては実装が軽かったですが、 F - Robot Rotation などは青 diff 中盤だったので、その辺りに壁があるようです。

競技プログラミング

動的計画法

EDPC の D - Knapsack 1 を Max モノイドで解いてみました。半環の気持ちで Num と Monoid を使うのは手に馴染みます。

型クラス Semiring を作るのはやり過ぎかも……？

ライブラリ

`KnownNat`

型レベルリテラル？を GHC の KnownNat に移行しました。 Integer を返すため、若干遅くなった気もしますが、 type として定数を書けるのが格好良くて気に入っています。

{-# LANGUAGE DataKinds #-}
import Data.Proxy
import GHC.TypeLits

type MyModulo = (998244353 :: Nat)

-- | 998244353 :: Integer
example :: Integer
example = natVal (Proxy @MyModulo)

AtCoder Library Practice Contest

この常設コンをやっていました。 PAST と範囲が被ります。やはり PAST でも ac-library で解ける問題が出されるわけで、難問の準備に良さそうでした。

D - MaxFlow
Dinic 法を実装しました。 cojna/iota を写経したため高速になりました。やはり compressed sparse row 形式でグラフを持つのが効くようです。
E - MinCostFlow
最小費用流を実装し、最大費用流と実装を共通化しました。モノイド (Max or Min) の指定で切り替えできます。 API は整理中……
Two SAT
2-satisfiability problem は SCC で解ける！　証明はともかく、解き方を理解しました。
K - Range Affine Range Sum
ゲーム開発でお馴染みの変換行列で AC しました。この方法は斉次座標系／同次座標系 (homogeneous coordinate system), 射影座標系 (projected coordinate system) などで検索すればヒットします。

遅延セグメント木を修正し、演算子の適用順序を変更しました。たとえば \((B <> A) x\) を計算したつもりで \((A <> B) x\) の計算になっており、デバッグが大変でした。

Library Checker

Library Checker も難問揃いで憧れます。

library-checker-problems にてテストケースを生成できる他、 verification-helper の oj-verify run にてテストケースのダウンロードと実行を自動化できるようです。便利！

NixOS だと sandbox からの脱獄に失敗しました。便利じゃない！

Misc

朝起きれない時は、俺自身がソラールとなることだ。

キーボード

MiniAxe の在庫補充があり、即注文しました。楽しみです。

Cyberpunk 2077

ファン作品が面白かったので買いました。他のことが気になって中々プレイできませんが、初めて GPU (RTX 3070) を活用している気がします。

Web 開発

Emmet 道場と AtCoder diff が欲しいです。

進捗は無ですが、やります！　本当なんです！！