はまやんはまやんはまやん

hamayanhamayan's blog

競技プログラミングにおける半環問題まとめ

半環

競技プログラミング的な解釈だと
https://www.slideshare.net/chokudai/abc009/86
が神がかって分かりやすい。
pekempeyさんの解説もお金取って良いんじゃないかレベルで神がかってる
http://pekempey.hatenablog.com/entry/2017/03/07/023127

半環一覧

(集合,+演算子,*演算子)
1. (整数,+,*)
2. (整数,xor,and)
3. (整数,max,+)
4. (行列,+,*)

考え方と注意

  • 漸化式を上手く作れればある線形写像が独立にマージできる (セグメントツリー)
  • 漸化式をとにかく上手く作る
  • 複数のパラメタを用いて順番に更新するような問題でパラメタが更新されるようなクエリがあっても、部分的に修正、高速に計算ができる
  • セグメントツリーで計算する時に順番に注意
  1. 交換則が成り立ってないかも
  2. 既存のセグメントツリーライブラリを使うのは良いが、順番通りに計算してくれていることを確認
  3. こんなバグわかんねぇよ(3時間は溶けた)

以下問題集

1. (整数,+,*)

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

http://arc008.contest.atcoder.jp/tasks/arc008_4

2. (整数,xor,and)

3. (整数,max,+)

4. (行列,+,*)

Good Bye 2016 E. New Year and Old Subsequence

http://codeforces.com/contest/750/problem/E

yukicode No.426 往復漸化式

http://yukicoder.me/problems/no/426











以下、短い解説

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

http://arc008.contest.atcoder.jp/tasks/arc008_4
半環 + セグメントツリー (+ 座圧)
解説
http://kagamiz.hatenablog.com/entry/2012/09/23/171835
https://kimiyuki.net/blog/2015/11/10/arc-008-d/

yukicode No.426 往復漸化式

http://yukicoder.me/problems/no/426
半環 + セグメントツリー