ABC 357

ABC 357 に参加しました。 Diff 予想は全然当たりません。

Table 1: Diff 予想
問題 A 問題 B 問題 C 問題 D 問題 E 問題 F 問題
予想 200 50 600 600 1,100 1,600
実際 19 26 371 970 1295 1793

A 問題

1 問目から飛ばし気味です。累積和を考えると良いですね。

main=interact$show.f.map read.words;f(_:m:r)=length.takeWhile(<=m)$scanl1(+)r

B 問題

Data.Char に isUpper, toUpper, isLower, toLower があります。 ord :: Char -> Int もよく使います。

import Data.Char
main=interact$flip map<*>f.sum.map(g.isUpper).init
g b|b=1|0<1=(-1)
f n|n>0=toUpper|1>0=toLower

interact には改行文字が付いてくるので init で切り落としました。

C 問題

手続き的にごり押ししました。皆さんの解答が美しくて良かったです。グリッドと戦う時は、いつもグシャグシャになってしまう……

D 問題

入力値を \(x\) とすると、 \(\sum\limits_{i \in [0, \mathcal{x})} p^i x (p := 10^{\mathcal{len}})\) を計算します。

\(S := \sum\limits_{i \in [0, x)} p^i\) の計算方法は、数列でしこたまやったやつですね。

\begin{aligned} S &= p^0 + p^1 + \dots + p^{x - 1} \\ p S &= 0 + p^1 + \dots + p^{x - 1} + p^{x} \\ S &= \frac {p^{x} - p^0} {p - 1} \end{aligned}

\(p^x\) の部分は 【電子版単体】Haskellで戦う競技プログラミング 第2版 でおなじみの Fermet の小定理およびダブリング (binary lifting) で計算しました。オーバーフローには要注意です。パワー！

E 問題

Functional graph の問題です。閉路の部分をサイズ K の頂点 1 つに置き換えるようなイメージで解きました。グラフと戦う時は、いつもグシャグシャになってしまう……

F 問題

課題を感じさせる問題でした。

区間を set で管理するテクニック

概要

IntervalMap はある種の区間クエリを捌くシンプルなデータ型です。

例

初期状態:
    [---------]       [---------]  [-------]
         x                 y           z

値 a の区間を挿入する:
                             ********
    [---------]       [-----][------][-----]
         x               y      a       z

区間を削除する:
          ***************
    [----]               [--][------][-----]
       x                 y      a      z

償却計算量について (お気持ち解説)

区間の数は 1 度の挿入で高だが 2 つしか増えません。また多数の区間を上書き／削除した場合、区間の数はごっそりと減ります。よって insert/delete の償却計算量は区間数に比例しません。

命名について

区間 [l, r] の訳は interval [l, r] であり、 range map よりも interval map と呼ぶのが適切なようです。

と言いつつ Haskell には inRange 関数があるため、 Haskell においては RangeMap と呼ぶのも問題無い気がします。

リファレンス実装

PAST 06 M - 等しい数 は、上記のテクを持っていると「やるだけ」な問題です。解説 区間を管理する構造体 - のいみのいみのいみのいみ を写経して IntervalMap を実装しました。

C++ の std::set は upper_bound が左から右へのイテレータを返す点などが良さそうでした。実際、 noimi さんの提出 が 328 ms で 僕の提出 が 1055 ~ 1304 ms です。速い木が欲しい……！

Quickcheck

Insert/delete のクエリを生成し、 IntervalMap の計算結果を愚直解と比較する quickcheck を作成しました。あまり個々の property をチェックする必要性を感じません。

感想

素直な方法でした。アルゴリズムとしては Union-Find よりも簡単な気がしますが、なぜか『高度典型』に含まれるようです。

Misc

デバッグ

未だに runtime error の発生箇所が分からない問題……悲しいです。至るところに HasCallStack があれば良いのに……。

vector に関しては U.(!) に HasCallStack が付いていない問題を理解し、 issue を立てました 。 U.(!) の実行時エラーは発生箇所が分かりませんが、 G.(!) の方はフルでスタックトレースが出ます。 G.(!) を好んで使うべきでしょう。

実行時エラーの際に、常にスタックトレースを表示するようなデバッグビルドを探しています。たとえば stack で --trace 引数を使うと……何も起きません。気長に調べます。

Quickcheck の書き方の調べ方

ChatGPT にタプルのジェネレータの書き方を教えてもらいました。

valueSpanGen :: Int -> Int -> Int -> Int -> Gen (Bool, (Int, Int, Int))
valueSpanGen l0 r0 xl xr = do
  l <- QC.chooseInt (l0, r0)
  r <- QC.chooseInt (l, r0)
  x <- QC.chooseInt (xl, xr)
  return (True, (l, r, x))

Property を作る際には、それぞれの Gen を QC.forAll にかける必要があります。 forAll のネストを減らしたければ、 Gen の方をタプルにまとめてしまえば良いようです。

ガチ言語 Haskell

99 likes まで言っていました。ありがとう……読みづらくてごめんなさい……

入門とはトラブルシューティングのことだと思っていたので、そうした事例の寄せ集めになっているかと思います。 読み通すだけでレベルアップできるような構成 を目指すべきだと反省しています。書き直したい……！

やる夫

やる夫を書いてみたかったのですが、厳しい状況でした。

Haskeller やる夫、 brainf*ck 霊夢、 Nibbles の妖精などを見てみたかったです。