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

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

HackerRank

HackerRank Happy Query Contest 2019 Array Restoring

形式的冪級数 (FPS) を用いた「多項式としての除算」の練習に 問題へのリンク 問題概要 長さ の数列 と、長さ の数列 がある。 は初期状態ではすべて 0 である。 に以下の一連の 回の操作を行った。 各操作は区間 で表される ( を満たす) 数列 の該当する区…

フォルシアゆるふわ競プロオンサイト #3 G - Digit Sum Multiple locked

12 が 4 の倍数で、112 が 8 の倍数だから、1112 が 16 の倍数なんじゃないの...と迷走したりしていた。 問題へのリンク 問題概要 以下の条件を満たす整数 を 1 つ求めよ (というクエリに 回答えよ) 桁の整数である どの位の値も 0 ではない 各桁の話を とし…

フォルシアゆるふわ競プロオンサイト #3 F - Yet Another Cake Division locked

面白かった 問題へのリンク 問題概要 の盤面の各マスを T, M, N, P の四色に塗る方法のうち、以下の条件を満たすものが何通りあるか、1000000007 で割ったあまりを求めよ。 どの T マスと M マスについても、M マスは T マスから見て strict に右にあるか、s…

フォルシアゆるふわ競プロオンサイト #3 E - Sweets Distribution(Hard)

面白かった。セグ木にこういうの乗っけるの楽しい! 問題へのリンク 問題概要 の盤面の各マスに整数値が書かれている。このマスに対して、適切に を決めて、 盤面の 0 行目の区間 の総和 盤面の 1 行目の区間 の総和 盤面の 2 行目の区間 の総和 盤面の 3 行…

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

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

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

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

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

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