pekempeyのブログ

競技プログラミングに関する話題を書いていきます。

Codeforces Round #368 (Div. 2)

Haskell の練習です。D は C++ のコードも載せておきます。

http://codeforces.com/contest/707

Brain's Photos

問題概要

n×m の写真があるのでモノクロ写真かどうかを判定せよ。モノクロであるというのは B(black), G(grey), W(white) のみで構成される写真のことである。

解法

G の存在に気をつけよう。char 型の読み込みはスペースの扱いに注意。いっそ string で読み込んだ方が無難かも。

Bakery

問題概要

n 頂点 m 辺の重み付き無向グラフが与えられる。指定された k 個の頂点を dark grey、それ以外の頂点を light grey としたとき、dark grey と light grey に接続している辺のコストの最小値を求めよ。ただし存在しない場合は -1 を出力すること。

解法

言語によっては k==0 のときに無を読み込もうとして RE するので注意。

Pythagorean Triples

$n^2+a^2=b^2$ としてみよう。すると $n^2=(b-a)(b+a)$ であるから、$b-a$ は $n^2$ の約数である。

なので $n^2=pq$ として $b-a=p,\; b+a=q$ と表せる。これを $a$,$b$ について解くと $a=(q-p)/2,\; b=(q+p)/2$ になる。

つまり偶奇が同じ $p, q$ があれば、それを使って解を構成できる。このような $p, q$ は $n \le 2$ のときは存在しないが $n \ge 3$ のときは必ず存在する。

$n$ が奇数のときは $(p,q)=(1,n^2)$、n が偶数のときは $(p,q)=(2,n^2/2)$ が条件を満たす($n$ が偶数のとき $n^2$ は 4 の倍数になる)。

Persistent Bookcase

異なるバージョン同士のマージがないので変更履歴は木の形になる。クエリを先読みして変更履歴の木を作っておく。

後は DFS するだけでいい。DFS ならノード毎に状態分のメモリを保つ必要がなくなる。

persistent は明らかにフェイクだが、永続を使っても普通に解ける。bitset を値とする永続配列を使えばいい。1024/64=16 なので 1 クエリあたりの負荷は軽い log と大差ない。こっちの方が本質的な処理がシンプルになるので楽。

Haskell でも通った。Haskell でビット並列を書く方法がわからないので Data.Set をノードに持たせた。ゴリゴリデータ構造を定義したが、デフォルトで永続配列ってあるのかな(Data.Map を使えばできるけど)。

よくあるデータ構造は大抵永続化できる。ほとんど自前で verify してるので若干信用ならない。『Purely Functional Data Structures』という本に色々書いてある。

データ構造 実装方法 自分の実装
array 二分木を使えば簡単。セグメント木と大差ないのでライブラリ化はしていない。 作ってない
list 片方向リストなら簡単。SchemeHaskell だとリストが片方向リストになっている。双方向は木の実装しか知らない。 作ってない
stack 片方向リストをそのまま使えばいい。 Persistent Stack · GitHub
queue 2 つの stack を使う方法がある。よくある片方のスタックが空になったら全部移す方法だと amortized O(n) にならないのだけど、工夫すると amortized O(n) にできる。 作ってない
deque Haskell の Data.Seq に使われてる finger tree というのを使うと O(1) らしいけど、詳しいことは知らない。木を使えば自明に O(log n)。 作ってない
heap 配列を使った二分ヒープはダメだけど、leftist heap なら O(log n) でいける。skew heap は永続するとダメなタイプの amortized だと思う。 Persistent Heap · GitHub
binary tree (map/set) RBST が楽なんだけど偶に木の高さが爆発する(実際に死ぬ問題が ECR で出た)。赤黒木なら原理的に安全。以前問題に使ったコードをそのままライブラリにしているので汎用的な作りにはなってない。 Persistent Red Black Tree · GitHub
segment tree 簡単。動的なやつと大差ない。一点更新だけはモノイドで一般化したものをライブラリにしてるけど一から書いてることが多い。 Persistent Segment Tree · GitHub
union find tree 永続配列を使えば簡単だけど、オーダーを増やさない方法は知らない。メモリ消費大。 Persistent Union Find · GitHub
BIT できるけど配列を使った実装のようなシンプルさはない。セグ木より速いのかも分からない。 Persistent BIT · GitHub
久々に英語を読んだら B が読めなくて辛かった。