2021-04-06

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

概要

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

	出題場所	コンテスト名	難易度	問題名
0	IOI	IOI 2016 day2	700	Aliens
1	ICPC	ICPC 2020 Yokohama	900	Solar Car
2	HUPC	HUPC 2020 Day2	600	Partition
3	ICPC	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 (有志)	技術室奥プログラミングコンテスト#2	700	NPCの家
8	AtCoder	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	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

2021-04-02

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$ の折れ線の本数をポテンシャルにすると償却できて、線形です。

2021-04-01

競プロ 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}) とかにすると良いと思います。

2021-03-23

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

2021-02-08

{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

2021-01-10

整数と実数と不等号と切り上げと切り捨て

同じ列にある $8$ つの式は、 $n \in \mathbb{Z}, r \in \mathbb{R}$ の元で同値です。


$n \lt r$	$n \le r$	$n \gt r$	$n \ge r$
$n \lt \lceil r \rceil$	$n \le \lfloor r \rfloor$	$n \gt \lfloor r \rfloor$	$n \ge \lceil r \rceil$
$n \le \lceil r \rceil - 1$	$n \lt \lfloor r \rfloor + 1$	$n \ge \lfloor r \rfloor + 1$	$n \gt \lceil r \rceil - 1$
$n + 1 \le \lceil r \rceil$	$n - 1 \lt \lfloor r \rfloor$	$n - 1 \ge \lfloor r \rfloor$	$n + 1 \gt \lceil r \rceil$

$r \gt n$	$r \ge n$	$r \lt n$	$r \le n$
$\lceil r \rceil \gt n$	$\lfloor r \rfloor \ge n$	$\lfloor r \rfloor \lt n$	$\lceil r \rceil \le n$
$\lceil r \rceil - 1 \ge n$	$\lfloor r \rfloor + 1 \gt n$	$\lfloor r \rfloor + 1 \le n$	$\lceil r \rceil - 1 \lt n$
$\lceil r \rceil \ge n + 1$	$\lfloor r \rfloor \gt n - 1$	$\lfloor r \rfloor \le n - 1$	$\lceil r \rceil \lt n + 1$

次の $4$ つの式が成立します。

$\max \left \lbrace n \in \mathbb{Z} \mathrel{} \middle | \mathrel{} n \lt r \right \rbrace = \lceil r \rceil - 1$
$\max \left \lbrace n \in \mathbb{Z} \mathrel{} \middle | \mathrel{} n \le r \right \rbrace = \lfloor r \rfloor$
$\min \left \lbrace n \in \mathbb{Z} \mathrel{} \middle | \mathrel{} n \gt r \right \rbrace = \lfloor r \rfloor + 1$
$\min \left \lbrace n \in \mathbb{Z} \mathrel{} \middle | \mathrel{} n \ge r \right \rbrace = \lceil r \rceil$

2020-11-28

割れない時の行列式

アルゴリズム

概要

逆元が必ずしもない状況で行列式を計算する方法を紹介します

一般の可換環上の行列式

n91lib_rs/division_free_determinant.rs at master · noshi91/n91lib_rs · GitHub

除算を使わない $\Theta(n^4)$ のシンプルなアルゴリズムが知られています。除算無しでも $o(n^3)$ になるらしいのですが、詳しく勉強してないので詳細は分かりません。

${\rm mod}$ 合成数

掃き出し法のアルゴリズムを少し変えるだけで高速に計算できます。掃き出し法は「ある行を使って別の行の先頭要素を 0 にする」を繰り返すアルゴリズムなので、この部分を何とかできればいいです。そこで、0 にしたい列の要素を一旦 ( ${\rm mod}\ m$ ではなく) ただの数だと思って、ユークリッド互除法を行います。ユークリッド互除法は定数倍と加減算なので、 ${\rm mod}\ m$ でも問題なく計算できます。これを繰り返せば $O(n^3 \log(m))$ のアルゴリズムが得られます。 ${\rm gcd}$ を繰り返しとる操作は計算量が落ちるので、実際には $O(n^3 + n^2 \log(m))$ になっています。