noshi91のメモ

データ構造のある風景

区間を 2 次元平面にプロットする

概要

区間  \lbrack l , r ) l, r のそれぞれを軸とする  2 次元平面にプロットするという方法を紹介します。

f:id:noshi91:20210505141442j:plain:w500

まず、 1 つの区間を置いた図がこれです。 赤い点がプロットされた区間であり、斜めの対角線を  \lbrack 0 , n ) と思うと  \lbrace で示した部分がその区間に該当します。 点線によって領域が  6 つに分けられており、区間と他の区間との位置関係が  6 通りあることがすぐに分かります。 別の区間 (青) を置いてみると以下のようになります。

f:id:noshi91:20210505142051j:plain:w500

この場合、青の区間と赤の区間は overlap しており、青が左側にあります。 他の領域はそれぞれ包含や非交に対応しています。 この図示によって、例えば  2 つの区間の位置関係を判定したいときにどのような条件式を書けばよいかなどを素早く確実に導出することができます。 また、区間が関わる動的計画法などのイメージにも便利です。*1

*1:効果には個人差があります

Monge 性が関係する問題リスト

概要

Monge 性が関係している問題のリストを作ります。 noshi91 は過去問をあまり埋めていないので、貧弱なリストになると思います。 もし載っていないものがあったら教えてもらえると嬉しいです (noshi91 に対するネタバレを気にする必要はありません)。

リスト

ネタバレ防止のため、その問題の属性を部分的に確認できるようにしました。 クリックすると表示されます。 追加して欲しい属性がある場合も noshi91 に提案してください。

難易度は noshi91 の体感で、AtCoder の得点換算です。 Monge 性に関するアルゴリズムは知っているものとします。

出題場所 コンテスト名 難易度 問題名
0
IOI
IOI 2016 day2
700
Aliens
1
ICPC 2020 Yokohama
900
Solar Car
2
HUPC
HUPC 2020 Day2
600
Partition
3
ICPC 2020 Seoul
700
Two Buildings
4
yukicoder
yukicoder contest 228
800
913 木の燃やし方
5
yukicoder
yukicoder Advent Calender Contest 2019
600
952 危険な火薬庫
6
yukicoder
yukicoder contest 193
700
705 ゴミ拾い Hard
7
AtCoder (有志)
700
NPCの家
8
AtCoder COLOCON 2018
600
すぬけそだて――トレーニング――
9
JOI
JOI 2018/2019 春合宿 Day4
800
ケーキの貼り合わせ
10
USACO
USACO 2007 November Gold
600
Telephone Wire
11
KUPC
KUPC 2012
400
刺身
12
ICPC WF2014
700
Buffed Buffet
13
IOI
IOI 2013
800
Wombats
14
yukicoder
yukicoder contest 283
1100
ジグザグロボット
15
IOI
IOI 2014 day2
800
Holiday
16
JAG Summer Camp
JAG Summer Camp 2013 Day2
700
TiMe Table
17
JAG Winter Contest
JAG Winter Contest 2009
600
Tree Construction
18
JAG
JAG Practice Contest for ACM-ICPC Asia Regional 2015
700
Optimal Tournament

yukicoder 1467 Selling Cars Θ((M + N) M + N log (N))

概要

No.1467 Selling Cars - yukicoder の非常に雑な解説

解法

 k を固定して最小費用流にエンコードすると以下のようになります。 頂点の数値は湧き出しの量です。

f:id:noshi91:20210402231219j:plain

実際には適切に座標圧縮します。 これは series-parallel graph なので最小費用流が効率的に計算できます。

tokoharupage/advent2019.pdf at master · tokoharu/tokoharupage · GitHub

この時点で  \mathrm{O} (M (M + N) \log (M + N)) にはなりますが、log を落とすことができます。

区分線形凸関数に対して必要な操作をグラフに対する操作で雑に表現すると以下の 3 つです。

  •  c \lvert x \rvert の加算
  •  x 負の方向に 1 ずらす
  • 最小値から  x 正の方向に長さ  k x 軸に平行な線分を差し込む

最小値を取る  x が常に非正なので、関数を  \lbrack \mathrm{argmin}, 0 \rbrack \lbrack 0, \infty ) に分けて、線分の列として管理します。  \lbrack \mathrm{argmin}, 0 \rbrack の折れ線の本数をポテンシャルにすると償却できて、線形です。

競プロ C++ 部分集合走査ライブラリ

概要

for (auto t: subsets(s)) で s (の bit 列を集合と解釈したとき) の部分集合を走査できるようなライブラリを書きました。 単純には std::vector<int> を返せばいいのですが、速度が少し気になるので、それを解決します。 部分集合に限らず、多次元ループなども同様の方法で効率的に記述できると思います。

範囲 for ループの制限緩和 - cpprefjp C++日本語リファレンス

実装

#include <cstdint>
#include <variant>

struct subsets {
  using u64 = std::uint64_t;

  u64 s;

  subsets(u64 s_) : s(s_) {}

  struct itr {
    u64 s;
    u64 t;

    bool operator!=(std::monostate) { return t != -1; }
    void operator++() { t -= 1; }
    u64 operator*() { return t &= s; }
  };

  itr begin() { return {s, s}; }
  std::monostate end() { return {}; }
};

注意

  • s 自身や 0 も走査されます。dp で使いたいときはこれらを含まないようにした方が良いかもしれません。
  • s = -1 のとき壊れます。
  • u64 を返しているので、必要なら適宜 int などに変えてください。
  • std::monostate は何でもいい (int でも char でも) ので、変えても良いです。C++14 だと begin と end で同じ型が返る必要があるので、itr({0,0}) とかにすると良いと思います。

クエリが整数の Convex Hull Trick の 凸 判定

概要

Convex Hull Trick で最小値取得クエリの  x が整数の時、アルゴリズム内で直線が不要かどうかチェックする部分を簡単に記述することが出来る。 特に、傾きと切片を掛けることでオーバーフローする問題を発生させない。

本文

Convex Hull Trick で、最小値取得クエリの  x の値の全てが整数とします。 簡単な下処理により、直線の傾きは distinct と仮定してよいです。  3 本の直線  \lbrace \text{line}\ i = a _ i x + b _ i \ | \  i = 0, 1, 2 \rbrace があり、 a _ 0 > a _ 1 > a _ 2 とします。 ここで、 a _ 1 x + b _ 1 が不要かどうか判定することを考えます。  3 本の直線が下図のような位置関係にあるとしましょう。 座標軸の目盛りは整数の座標を表しています。

f:id:noshi91:20210323190912j:plain

Convex Hull の字面に従うならば、 \text{line} \ 1 は最小値を取り得る、すなわち必要な直線です。 しかし、クエリが整数しかないという仮定の下、 \text{line} 1 は最小値を取り得ません。 この条件を正確に記述します。

\begin{align} f(ax+b, cx+d) := \max \lbrace k \ | \ ak+b \leq ck+d \rbrace \end{align}

と定義すれば、

\begin{align} \text{line}\ 1 \text{が最小値を取り得る} \Leftrightarrow f(\text{line}\ 0, \text{line}\ 1) < f(\text{line}\ 1, \text{line}\ 2) \end{align}

です。 ただし、 2 直線が交わる  x 座標では傾きの大きい方が最小値を取るとしています。

ところで  a > c の仮定の下

\begin{align} f(ax+b, cx+d) :&= \max \lbrace k \ | \ ak+b \leq ck+d \rbrace \\ &= \left \lfloor \frac {d - b} {a - c} \right \rfloor \end{align}

であるため、 f は整数除算で計算することが出来ます。 これにより、分母を払って判定するアルゴリズムにおけるオーバーフローの問題が発生しなくなります。 また、この条件はクエリが実数の場合の条件より強い条件なので、残された直線群の 凸 性が保たれ、最小値取得クエリのアルゴリズムは普通の物を使うことが出来ます。

{x | b^x = a (mod m)} の構造

概要

 a, b, m が与えられて  \lbrace x \mid b^x \equiv a \pmod m \rbrace の構造を観察します。

結論

 S := \lbrace x \mid b^x \equiv a \pmod m \rbrace について、次のうちいずれかが成り立ちます。

  •  S = \emptyset
  •  \exists\ 0 \le c \lt \log_2(m),\ S = \lbrace c \rbrace
  •  \exists\ n \mid \lambda(m),\ \exists\ t,\ S = \lbrace x \mid x \equiv t \pmod n  \rbrace
  •  \exists\ 0 \le c \lt \log_2(m),\ \exists\ n \mid \lambda(m),\ \exists\ t,\ S = \lbrace x \mid x \gt c \land x \equiv t \pmod n  \rbrace

証明

 m = \prod_{i=1}^{k} p_i ^ {e_i} とすると、中国剰余定理から  \mathbb{Z} / m\mathbb{Z} \simeq \prod_{i=1}^{k} \mathbb{Z} / p_i ^ {e_i} \mathbb{Z} i を 1 つ固定して考えると、

  •  p \mid b, a \neq 0 \pmod {p^e} のとき、 x は存在しないか、一意に定まる。
  •  p \mid b, a = 0 \pmod {p^e} のとき、 x \gt c の形の条件が付く。
  •  p \nmid b のとき、 x は存在しないか、 x = t \pmod {n} の形の条件が付く (ただし  n \mid \lambda(p^e))。

これらすべての条件を合わせた条件が、挙げた 4 つのいずれかに該当することは確認できる。

 \lambda : Carmichael function - Wikipedia