日々drdrする人のメモ

今日も明日もdrdr

LCAをベースに構築するAuxiliary Treeのメモ

(2019/09/15 20:50頃追記) ただAuxiliary Treeと書くと(一般的すぎて)齟齬を生む可能性が高いので、タイトル及び一部文章を変更しました。申し訳ないです。今回はLCAをベースに構築するAuxiliary Treeについて取り上げてます。

最近、LCAを元に構築する Auxiliary Tree を使う問題に出会ったので書いた。

CodeChef July Challenge 2019 で以下の問題があった。

smijake3.hatenablog.com

自分は Auxiliary Tree を使わず解いたが、想定解法が Binarization of a tree + Centroid Decomposition on Edge + Auxiliary Tree だったらしい。

discuss.codechef.com

以下を参考にしている。

続きを読む

グラフのchain decompositionで橋と関節点を求める

グラフのchain decompositionと、それを使って橋と関節点を求める手法のメモ

橋と関節点を求める手法といえばlowlinkを用いた手法が存在するが、他の手法としてchain decompositionを用いた手法が存在する。(WikipediaBridge (graph theory)Biconnected componentに載っている)

以下を参考にしている
[1] Schmidt, Jens M. "A simple test on 2-vertex-and 2-edge-connectivity." Information Processing Letters 113.7 (2013): 241-244.

続きを読む

CodeChef July Challenge 2019: Maximum and Minimum

CodeChef July Challenge 2019 の問題: Maximum and Minimum (Code: MXMN)
問題ページ: Contest Page | CodeChef

問題概要

無向グラフ Gに対して関数  f(G, x, y) を定義する。

  •  f(G, x, y) = 頂点 xから頂点 yまでの全てのパスの内での、パスの重みの最小値
    • パスの重みは、パスに含まれる辺の重みの内の最大値と定義

頂点数が N、辺の数が Mの2つの無向グラフ G_1 G_2が与えられる。

以下の値を modulo 998244353 で計算せよ

 \displaystyle S = \sum_{i=1}^{N-1} \sum_{j=i+1}^N f(G_1, i, j) \cdot f(G_2, i, j)

続きを読む

CodeChef July Challenge 2019: LOVEMUFFIN

CodeChef July Challenge 2019 の問題: LOVEMUFFIN (Code: LVMFFN)
問題ページ: Contest Page | CodeChef

問題概要

1から Nまで番号が付いた N人のメンバーがいる。
このメンバーで Mドルを分配する。

この分配の方法の決め方は  i=1 から以下のように行う。

  1. 番号 iの人が現在いる各メンバーに何ドル分配するか提案する
  2. この提案に(自分含めて)  \lfloor \frac{x}{K} \rfloor + 1 人が賛成すればその分配方法に決まり、終了する
    •  x は現在いるメンバーの数( 1 \le x \le N)とする
  3. 賛成数が足りず、分配方法が決まらなかった場合、番号iの人は屋上から放り出され、その場からいなくなる
    • つまり、メンバーの数が1人減る
  4. 番号 i+1の人が提案するところから(1)に戻る


各提案について各メンバーは、その提案に決まった場合に自身が得られる分配金に比べ、この案に決まらずその後の案で自分が確実に得られる分配金が同じもしくはそれ以上の場合、その提案に反対する。また、メンバー全員は自分が最大限の分配金を得られるように最適に動くとする。

また、提案に失敗し、屋上から放り出された人は  -10^{100} を得るのと同じと考える。

今から番号1の人がメンバーに対し分配方法を提案しようとしている。
同じ Kについて、 N, Mが異なりうる Q個のシナリオについて、自分が最大いくら得られるか、もしくは確実に屋上から放り出されるかを求めよ。

続きを読む

CodeChef July Challenge 2019: Snake and Apple Tree

CodeChef July Challenge 2019 の問題: Snake and Apple Tree (Code: CNKAPT)
問題ページ: Contest Page | CodeChef

問題概要

 N \times M の二次元盤面があり、各マスは空もしくは壁で構成される。
この盤面には  S 匹のヘビが存在する。

各ヘビは T秒間の間、各秒ごとに以下のいずれかの行動ができる。

  • 上下左右のマスに移動
  • 何もしない
  • りんごの木の実を1個食べる (複数の木がマスに存在しても高々1個のみ食べられる)

各秒ごとに1つのマスには高々1匹しか存在できない。

この盤面には  Z 本のりんごの木が生えて枯れる。
 i 番目の木は  P_i秒目に 座標 (X_i, Y_i)に生えて、  Q_i秒目に枯れる。

 i番目の木の実をヘビが1個食べた時、 H_i のhapinessが得られる。
(木が生えている間は、各秒ごとに1個ずつ食べられる)

 T秒間の行動で、各ヘビが得られるhapinessの総和の最大値を求めよ。

続きを読む

CodeChef July Challenge 2019: Hit the Coconuts

CodeChef July Challenge 2019 の問題: Hit the Coconuts (Code: CCC)
問題ページ: Contest Page | CodeChef

問題概要

 N個のココナッツがあり、 i番目のココナッツは A_i回叩くと割れる。
しかし、 N個のココナッツはシャッフルされ、どのココナッツが何回叩けば割れるか分からない。

今回、 Z個のココナッツを割る必要がある。
少なくとも何回叩けば Z個のココナッツを割ることができるか求めよ。

続きを読む

Segment Tree Beatsの実装メモ (Historic Informationまわり)

Segment Tree Beats(SGT Beats)のHistoric Informationまわりについて自分が理解した範囲のメモ

この記事は以下の続き。これらの説明を前提に書いてある。

続きを読む