日々drdrする人のメモ

今日も明日もdrdr

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まわりについて自分が理解した範囲のメモ

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

続きを読む

UOJ - #164: V

Historic Informationまわりの勉強で解いた。解法メモ

uoj.ac

問題概要

 1, 2, ..., Nの番号がついたタンクがある。

 i番目のタンクには最初 a_imの高さの水が入っている。以下のクエリを合計 M回処理せよ。

  1.  i \in [l, r] の各タンクの水の高さを xm上昇させる
  2.  i \in [l, r] の各タンクの水の高さを xm減少させる (高さは負にならない)
  3.  i \in [l, r] の各タンクの水の高さを xmにする
  4. タンク y の現在の水の高さ(m)を出力
  5. タンク y の過去最大の水の高さ(m)を出力
続きを読む

Segment Tree Beatsの実装メモ (応用的な例題まわり)

前回の記事の続き
smijake3.hatenablog.com

コドフォのSegment Tree Beatsの説明の例題として挙がっているTask 3,4を実装したので、そのあたりの考え方含めて書いておく

続きを読む