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

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

非自明なモノイド

Codeforces CodeCraft-20 (Div. 2) F. Battalion Strength (R2800)

実装がエグエグのエグだけど、実はなんと、遅延評価セグ木すら必要なくて、普通のセグ木だけあれば解けてしまう! 問題へのリンク 問題概要 個の整数 に対して定まる量 を次のように定義する: の部分集合を選ぶ 通りの方法から一様ランダムに選んで、さらに…

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

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

AtCoder ARC 008 D - タコヤキオイシクナール

セグメントツリーの二項演算は、モノイドについて実現され、結合法則のみ満たしていれば交換法則が必要ないことをハッキリと映し出した問題を解きました。 セグメントツリーの二項演算に必要な要件について koba さんの記事がとても参考になります: データ構…