CodeChef July Challenge 2019: Maximum and Minimum
CodeChef July Challenge 2019 の問題: Maximum and Minimum (Code: MXMN)
問題ページ: Contest Page | CodeChef
問題概要
無向グラフに対して関数 を定義する。
- = 頂点から頂点までの全てのパスの内での、パスの重みの最小値
- パスの重みは、パスに含まれる辺の重みの内の最大値と定義
頂点数が、辺の数がの2つの無向グラフ、が与えられる。
以下の値を modulo 998244353 で計算せよ
CodeChef July Challenge 2019: LOVEMUFFIN
CodeChef July Challenge 2019 の問題: LOVEMUFFIN (Code: LVMFFN)
問題ページ: Contest Page | CodeChef
問題概要
1からまで番号が付いた人のメンバーがいる。
このメンバーでドルを分配する。
この分配の方法の決め方は から以下のように行う。
- 番号の人が現在いる各メンバーに何ドル分配するか提案する
- この提案に(自分含めて) 人が賛成すればその分配方法に決まり、終了する
- は現在いるメンバーの数()とする
- 賛成数が足りず、分配方法が決まらなかった場合、番号iの人は屋上から放り出され、その場からいなくなる
- つまり、メンバーの数が1人減る
- 番号の人が提案するところから(1)に戻る
各提案について各メンバーは、その提案に決まった場合に自身が得られる分配金に比べ、この案に決まらずその後の案で自分が確実に得られる分配金が同じもしくはそれ以上の場合、その提案に反対する。また、メンバー全員は自分が最大限の分配金を得られるように最適に動くとする。
また、提案に失敗し、屋上から放り出された人は を得るのと同じと考える。
今から番号1の人がメンバーに対し分配方法を提案しようとしている。
同じについて、が異なりうる個のシナリオについて、自分が最大いくら得られるか、もしくは確実に屋上から放り出されるかを求めよ。
CodeChef July Challenge 2019: Snake and Apple Tree
CodeChef July Challenge 2019 の問題: Snake and Apple Tree (Code: CNKAPT)
問題ページ: Contest Page | CodeChef
問題概要
の二次元盤面があり、各マスは空もしくは壁で構成される。
この盤面には 匹のヘビが存在する。
各ヘビは秒間の間、各秒ごとに以下のいずれかの行動ができる。
- 上下左右のマスに移動
- 何もしない
- りんごの木の実を1個食べる (複数の木がマスに存在しても高々1個のみ食べられる)
各秒ごとに1つのマスには高々1匹しか存在できない。
この盤面には 本のりんごの木が生えて枯れる。
番目の木は 秒目に 座標に生えて、 秒目に枯れる。
番目の木の実をヘビが1個食べた時、 のhapinessが得られる。
(木が生えている間は、各秒ごとに1個ずつ食べられる)
秒間の行動で、各ヘビが得られるhapinessの総和の最大値を求めよ。
CodeChef July Challenge 2019: Hit the Coconuts
CodeChef July Challenge 2019 の問題: Hit the Coconuts (Code: CCC)
問題ページ: Contest Page | CodeChef
問題概要
個のココナッツがあり、番目のココナッツは回叩くと割れる。
しかし、個のココナッツはシャッフルされ、どのココナッツが何回叩けば割れるか分からない。
今回、個のココナッツを割る必要がある。
少なくとも何回叩けば個のココナッツを割ることができるか求めよ。
Segment Tree Beatsの実装メモ (Historic Informationまわり)
Segment Tree Beats(SGT Beats)のHistoric Informationまわりについて自分が理解した範囲のメモ
この記事は以下の続き。これらの説明を前提に書いてある。
Segment Tree Beatsの実装メモ (応用的な例題まわり)
前回の記事の続き
smijake3.hatenablog.com
コドフォのSegment Tree Beatsの説明の例題として挙がっているTask 3,4を実装したので、そのあたりの考え方含めて書いておく
続きを読む