けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

2020-02-29から1日間の記事一覧

フォルシアゆるふわ競プロオンサイト #3 D - Banana Game locked

すごく面白かった! 問題へのリンク 問題概要 個の袋があって、それぞれには 激辛バナナが 本 美味しいバナナが 本 がある。先手と後手が以下のことを交互に行う。 激辛バナナを 0 本または 1 本取り出す 美味しいバナナを好きな本数だけ取り出す ただし、激…

フォルシアゆるふわ競プロオンサイト #3 C - Bananas Multiplier (Hard) locked

ツリー上のパスクエリについての教育的典型題だった 問題へのリンク 問題概要 (意訳) 頂点の重み付きツリーが与えられる。以下の 個のクエリに答えよ。 各クエリは 2 頂点 , と値 が指定され、ツリー上の と とを結ぶパス上の辺の重みの積を求め、それと を…

フォルシアゆるふわ競プロオンサイト #3 B - Median Permutation locked

後ろから見たらわかった 問題へのリンク 問題概要 の順列 であって、以下の条件を満たすものの個数を 1000000007 で割ったあまりを求めよ。 任意の 以下の奇数 に対して、 のメディアンは である 制約 考えたこと 簡単のため、 を奇数として考えてみる。この…

CODE FESTIVAL 2017 qual C D - Yet Another Palindrome Partitioning (黄色, 700 点)

遷移先を絞れる系の DP 問題へのリンク 問題概要 長さ の文字列 が与えられる。これを以下の条件を満たすように最小個数の区間に分割したい。最小個数を求めよ。 どの区間についても、区間内の文字を適切に並び替えると回文になる 制約 考えたこと まず「文…

第5回 ドワンゴからの挑戦状 本選 2019 B - XOR Spread (800 点)

操作を言い換えるところは楽しいけど、BinaryTrie が必要ということで、必死に整備した。 問題へのリンク 問題概要 要素の非負整数列 が与えられる。以下の操作を好きな回数だけ行える。行なった結果得られる数列のうち、辞書順最小のものを求めよ。 index …

AtCoder ARC 033 C - データ構造 (試験管青色)

BinaryTrie を確認した!!! 問題へのリンク 問題概要 数の集合 S に対する以下のクエリ ( 個) を処理してください。 S に数 X を追加する S に含まれる数のうち X 番目に小さい数を答え、その数を S から削除する 制約 考えたこと BIT や priority_queue、…