sataniC++

C++、競プロ、数学などについて色々考えたりします。

競技プログラミングを始めて1年が経ちました

2015/11/22に競技プログラミングを始めてから丁度1年が経ったので、競技プログラミングをやるにあたって、何をしていたか等を記事としてまとめておきます。
(ためになる話は多分そこまでないです)


この記事の流れ

この記事は次のような構成になっております。

  • 始まり
  • 競プロを始めて変わったこと
  • この一年での競プロにおける変化
  • (以下「続きを読む」部分、競プロでの様々なこと)
  • 言語
  • 競プロ環境
  • 練習・勉強方法
  • 成績
  • 最後に

始まり

twitter.com
私が"競技プログラミング"というものに触れたのはyukicoderが一番最初でした。
何故yukicoderかはわかりませんが、yukicoder の"ゆるふわ"推しにつられたのでしょう(?)。
このときは、AtCoderTopCoderICPCなどは全く知りませんでした。


競プロを始めて変わったこと

twitter.com
簡単に言うと、競プロ依存になりました

競プロは、何かキッカケをもって始めた訳ではないため、
「まぁコーディングの練習として適当にやってみよう」
位の感じでした。


しかし、問題を解き、コンテストにも参加するようになると、だんだん次のようなところに惹かれていきました。

  • 問題を見たときに、「どのアルゴリズムを使うのがいいか?」と考えるのが楽しい
  • 実生活でありうるような、複雑な要素が絡み合う問題をプログラムに解かせることが出来るのが面白い
  • 単純に問題を解くのが楽しい
  • Twitterを通して他の人と競プロの話題で盛り上がることが出来るのが楽しい

などなどです。

こうして、競プロを主軸とした生活が始まるのでした…。



twitter.com
また、Twitterの利用法も大きく変わりました。
このツイートは競プロを始めて1週間くらいの時のものですが、当時まだフォロー/フォロワー数が100人前後しかいませんでした。
f:id:satanic0258:20161123215514p:plain
(競プロを始める前は何故かこんなアイコンだったんですが、覚えている人はいるんでしょうか)



twitter.com
f:id:satanic0258:20161123220040p:plain
ところが、競プロを始めて、競プロ/プログラミングをやっている人をフォローしていたら、気づくとフォロー/フォロワー数が400人前後まで増えていました。

Twitterで話す内容も、半分以上が競プロの内容ばかりとなっています。



twitter.com
また、いつの間にかプログラム実装力がついていました。

プログラミングのコンテストでは、問題を見てからそれをすぐにコードに起こすことが重要となってきます。
そのため、コンテストで経験を積んでいった結果、競技とは関係のないところで簡単なプログラムを作成する際に、素早く目標のプログラムを作成することが出来るようになっていました。
(このおかげで試験も難なくこなせたので、まさに競プロありがとう、と言った感じでした)


この一年での競プロにおける変化

ここでは、各コンテストサイトでのレートの変遷を見ていきます。

AtCoder

f:id:satanic0258:20161123225317p:plain
AtCoderのページが新しくなってからのレートはこのようになっています。
未だ何とか単調増加を続けてはいますが、正直結構厳しいですね…。
なるべく増加を続けられるように頑張りたいと思います。


Codeforces

f:id:satanic0258:20161123225558p:plain
Codeforcesのレートはこのようになっています。
正直こどふぉは問題文がの読解が難しい回が何回かあり、それ故のミスもよくしています…。
(最近Google翻訳の性能が向上したこともあってか、レートも少し上がっています)

また、こどふぉではちゃんとコーナーケースを処理しなければ落ちてしまうことも多々あるため、うっかりそれを忘れてレートが下がったりもしています。
素早く、かつ正しく問題を理解することが大切ですね…。


TopCoder SRM

f:id:satanic0258:20161123230126p:plain
SRMのレートはこのようになっています。
SRMは結構レート変動が激しく、参加した回の半分も色が変わってしまっています(苦笑)。

一応青から黄色になったりしてはいますが、まだdiv1の問題を時間内に解いたことがないため、それが今後の課題となっています。
何とか競プロ2周年までには、div1easyを安定して解けるようになりたいですね。


  • (以下「続きを読む」部分、競プロでの様々なこと)

この先は、過去1年分のツイートを適当に抜粋して、あったことなどのコメントを加えただけのものなので、時間に余裕のあるときどうぞ。

(Twitterのツイートを大量に貼り付けているため、記事のロードに時間がかかる可能性があります)

続きを読む

yukicoder No.409 ダイエット

問題

問題のURLはこちらです。
No.409 ダイエット - yukicoder

考えたこと

動的計画法を使います。

配列DPを次のように定義します。
DP[i] = i日目にドーナツを食べた時の体重の変化量の最小値

すると、その時の漸化式は、
\displaystyle \begin{eqnarray}
DP[0] &=& 0 \\
DP[i] &=& min_{0\leq t\leq i-1}\left(DP[t] -A(i-t-1)+\cfrac{(i-t-1)(i-t)}{2}B + D[i]\right) \\
&=& min_{0\leq t\leq i-1}\left(DP[t] + tA + \cfrac{-2it+t^2+t}{2}B\right) -A(i-1) + \cfrac{i^2-i}{2}B + D[i] \\
&=& min_{0\leq t\leq i-1}\left(DP[t] + tA + \cfrac{t^2+t}{2}B -itB \right) -A(i-1) + \cfrac{i^2-i}{2}B + D[i] \\
\end{eqnarray}

なお、最初の行を簡単に説明すると、
DP[i]
 = min\left(\right.(t日目にドーナツを食べた時の体重の変化量の最小値)
+ (t+1i-1日目に断食していた時の体重の変化量)
+ (i日目に食べたドーナツによる体重の変化量) \left.\right)
となっています。

ここで、上記漸化式のminの中をよく見てみると、
\displaystyle
DP[t] + tA + \cfrac{t^2+t}{2}B -itB \\
= \left(-tB\right) i + \left(DP[t] + tA + \cfrac{t^2+t}{2}B\right)
となり、これはi1次式となっていることが分かります。

従って、「直線(1次式)の中での最小値」を求めるため、Convex-Hull Trickを用いることが出来ます。

Convex-Hull Trickに関しては、こちらの記事を参照してください。
satanic0258.hatenablog.com

最後、求めるものは「i日目にドーナツを食べ、そこから断食した時の最小値」なので、先ほど求めた配列DPを使って、
W + min_{0\leq i\leq N}\left(DP[i] -(N - i)A + \cfrac{(N - i)(N - i + 1)}{2}B\right)
として求めることが出来ます。

コード(C++)

#111250 No.409 ダイエット - yukicoder
※ヘッダ等省略

ll dp[300005];

template<typename T>
class ConvecHullTrick {
private:
	// 直線群(配列)
	std::vector<std::pair<T, T>> lines;
	// 最小値(最大値)を求めるxが単調であるか
	bool isMonotonicX;
	// 最小/最大を判断する関数
	std::function<bool(T l, T r)> comp;

public:
	// コンストラクタ ( クエリが単調であった場合はflag = trueとする )
	ConvecHullTrick(bool flagX = false, std::function<bool(T l, T r)> compFunc = [](T l, T r) {return l >= r; })
		:isMonotonicX(flagX), comp(compFunc)  {
		lines.emplace_back(0, 0);
	};

	// 直線l1, l2, l3のうちl2が不必要であるかどうか
	bool check(std::pair<T, T> l1, std::pair<T, T> l2, std::pair<T, T> l3) {
		if (l1 < l3) std::swap(l1, l3);
		return (l3.second - l2.second) * (l2.first - l1.first) >= (l2.second - l1.second) * (l3.first - l2.first);
	}

	// 直線y=ax+bを追加する
	void add(T a, T b) {
		std::pair<T, T> line(a, b);
		while (lines.size() >= 2 && check(*(lines.end() - 2), lines.back(), line))
			lines.pop_back();
		lines.emplace_back(line);
	}

	// i番目の直線f_i(x)に対するxの時の値を返す
	T f(int i, T x) {
		return lines[i].first * x + lines[i].second;
	}

	// i番目の直線f_i(x)に対するxの時の値を返す
	T f(std::pair<T, T> line, T x) {
		return line.first * x + line.second;
	}

	// 直線群の中でxの時に最小(最大)となる値を返す
	T get(T x) {
		// 最小値(最大値)クエリにおけるxが単調
		if (isMonotonicX) {
			static int head = 0;
			while (lines.size() - head >= 2 && comp(f(head, x), f(head + 1, x)))
				++head;
			return f(head, x);
		}
		else {
			int low = -1, high = lines.size() - 1;
			while (high - low > 1) {
				int mid = (high + low) / 2;
				(comp(f(mid, x), f(mid + 1, x)) ? low : high) = mid;
			}
			return f(high, x);
		}
	}
};

signed main() {
	INIT;
	VAR(ll, n, a, b, w);
	VEC(int, d, n);
	ConvecHullTrick<ll> cht(true);

	dp[0] = 0;
	FOR(i, 1, n + 1) {
		dp[i] = cht.get(i - 1) - (i - 1)*a + ((ll)(i - 1) * i) / 2 * b + d[i - 1];
		cht.add(-i*b, dp[i] + i*a + (ll)(i - 1) * i / 2 * b);
	}
	/*
	REP(i, n + 1) {
		OUT(dp[i] + w)SP;
	}BR;
	*/
	ll ans = INFLL;
	REP(i, n + 1) {
		ans = std::min(ans, dp[i] + (-(n - i)*a + (n - i)*(n - i + 1) / 2 * b));
	}
	OUT(ans + w);
	return 0;
}

コードの説明など

コード前半部分は、Convex-Hull Trickのクラスを定義しています。

後半部分では、通常の動的計画法の実装を行い、併せて直線の追加などを行っています。

備考

追加する直線の傾き、最小値を求めるクエリにおける{\tt i}が、共に単調になっているため、計算量はO(N)に抑えられます。

感想など

始め、この問題を解いたときは、
DP[i][j] = i 日目に断食継続日数がj日となっているときの体重の変化量のい最小値
と考えて、計算するとj1415ほどしか必要ないと気づき、それで通してしまいました(そのソースはコチラ)。

しかし、学びのため、ということで想定解でもなんとかACしておきました。


この問題を解くまでConvex-Hull Trickという方法を知らなかったため、いい勉強になりました。これを活かして類題も解けるようにしたいですね。

Convex-Hull Trick

概要

直線集合L=\{f_i(x)=a_ix+b_i\}に対して、「Lへの直線f_k(x)=a_kx+b_kの追加」(以下、追加クエリ)と、「あるxに対し、Lの中で最小値(あるいは最大値)を取るような直線の値を求める」(以下、最小値クエリ)という2つのクエリを効率的に行うことが出来ます。


使える状況

DPの漸化式を整理したときなどにおいて、\displaystyle min_{1\leq i\leq n}(a_ix+b_i)といった式が出てきたときに、Convex-Hull Trickを用いることで効率的に値を求めることが出来ます。


説明

ここでは最小値を求めるときのみを説明します(最大値を求めるときは上⇔下、増加⇔減少など、文章を補って読んでください)。

クエリ

まず、それぞれのクエリを見ていきます。

直線集合Lに直線f_k(x)=a_kx+b_kを追加する

f:id:satanic0258:20160815045239p:plain
上図は、始め直線集合LL=\{y=2x+2, y=x+3, y=-x+10\}であった状態(左)から、そこに新たな直線y=-2x+15を追加した状態(右)へと遷移している様子を表しています。
(なお、グラフの描画にはGrapesというソフトを用いています。*1 )

あるxに対し、Lの中で最小値(あるいは最大値)を取るような直線の値を求める

上図左において、x=0のとき、3本の直線の中で最も小さい値を取るものはy=2x+2であり、その時の値は2となります。
同様にx=2では5x=6では4ということも分かります。

その後、赤色の直線を追加すると、x=0x=2のところでは変わらず2, 5となっていますが、x=6のところでは3と、直線を追加する前とは値が異なっていることが分かります。


このクエリを愚直に実装しようとすると、直線の本数をN本、最小値クエリの回数をQ回としたとき、最小値クエリを求める度に各直線における値を調べる必要があるので、計算量はO(NQ)となります。

しかし、より速くクエリをこなす方法があるため、それについて考えていきます。


性質

もう一度先ほどの図をよく見てみると、2つの性質が隠れていることが分かります。

1.最小値を取る直線は左から順に傾きが減少している

f:id:satanic0258:20160815052207p:plain

ちなみにこのことを簡単に証明すると、上図の状態で傾き2の直線の区間と傾き1の直線の区間の間に傾き0の直線の区間があるようなときに反例となりますが、

  • 直線y=3を追加したとき、傾きは2\to 0\to -2と遷移する
  • 直線y=5を追加したとき、傾きは2\to 1\to 0\to -2と遷移する

となります。よって、最小値を取る直線は左から順に傾きが減少している事がわかりました。

2.不必要な直線が無いとき、あるxでの直線の取る値は、その値を直線の傾き順に並べると下に凸となる

文章にすると少しわかりにくいですが、図にすると次のような感じです。
f:id:satanic0258:20160815163318p:plain
今、x=3のときについて考えています。このとき、直線の傾きを横軸、x=3のときの直線の取る値を縦軸とすると、次のようになります。
f:id:satanic0258:20160815163328p:plain


この性質についても簡単に証明すると、次の図左のような、直線集合\{y=-2x+3, y=-x+1, y=x+2, y=2x\}を考えたとき、x=0において直線の取る値をそのまま図にすると、図右のようになります。
f:id:satanic0258:20160815171620p:plain
しかし、図左に緑色で示した直線y=x+2は、xをどのようにとっても直線集合の中で最小値を取ることがありません。したがって、この緑色の直線を直線集合から取り除くことによって、図右の青色の折れ線のように下に凸となります。故に、不必要な直線を取り除いてしまえば、直線の取る値は傾き順に並べると下に凸となります。




これらの性質から、直線集合を、傾きをキーとしてソートしておくことにより、最小値クエリに二分探索を用いることが出来るため、N本の直線に対するQ回の最小値クエリの計算量はO(Q\log N)となります。


また、直線の追加クエリは、ソート済みの直線集合に追加する、ということから、先ほどと同様に直線の挿入位置を調べるのに二分探索を用いることが出来るため、全体の直線の数をN本とすると、全ての追加クエリの計算量はO(N\log N)となります。

不必要な直線を取り除く

他に、先ほどの性質を満たすためには「不必要な直線を取り除く」という動作も適宜行う必要があります。

それでは、どのようなとき、どうなっていれば「不必要」と判断することが出来るのか、それについて考えていきます。


まず、前提として直線集合がすでに不必要な直線を全て取り除いてあると仮定します。
このように仮定してしまえば、次に直線が不必要になるときは、直線を追加する際であると分かります。
よって、「直線の追加クエリ」を行うときに、「追加する事によって不必要になる直線を調べる」ようにすれば良いことが分かりました。

次に、どのような直線が不必要かについてですが、ここで次の図を考えます。
f:id:satanic0258:20160815190352p:plain
これは不必要な直線が無い状況です。なお、直線l_i:y = a_ix+b_iとすると傾きa_ia_1\geq a_2\geq a_3となっています。

このとき、直線l_1と直線l_2の交点を赤の点、直線l_2と直線l_3の交点を青の点、直線l_3と直線l_1の交点を緑の点とすると、これらの交点のx座標は、
赤の点\leq緑の点\leq青の点
となっていることが分かります。


一方、次の図を考えます。
f:id:satanic0258:20160815191214p:plain
これは不必要な直線がある状況です。直線の設定は先ほどと変わりません。

このとき、交点のx座標は、
青の点\leq緑の点\leq赤の点
となっていることが分かります。


このように、不必要な直線があるときとないときで、相異なる2直線の交点の位置関係が変わっています。

よって、3直線のうち相異なる2点を選んで、それらのx座標を比較することにより不必要かどうかを判断できることが分かりました。


ここでは、赤の点青の点を選んで考えます(どの2点を選んでも判断はできますが、蟻本*2と同じ選び方としておきます)。

まず、赤の点x座標を求めます。
赤の点は直線y=a_1x+b_1と直線y=a_2x+b_2の交点なので、次の連立方程式を解けば求めることが出来ます。

\displaystyle \begin{cases}y=a_1x+b_1\\ y=a_2x+b_2 \end{cases}

これを解くと(簡単のためにxについてのみ)、

\displaystyle \begin{eqnarray}
a_1x+b_1 &=& a_2x+b_2 \\
(a_1-a_2)x &=& b_2-b_1 \\
x &=& \cfrac{b_2-b_1}{a_1-a_2}
\end{eqnarray}

よって、赤の点x座標はx = \cfrac{b_2-b_1}{a_1-a_2}であることが分かりました。


同様に、青の点x座標を求めます。
青の点は直線y=a_2x+b_2と直線y=a_3x+b_3の交点なので、次の連立方程式を解けば求めることが出来ます。

\displaystyle \begin{cases}y=a_2x+b_2\\ y=a_3x+b_3 \end{cases}

これを解くと(簡単のためにxについてのみ)、

\displaystyle \begin{eqnarray}
a_2x+b_2 &=& a_3x+b_3 \\
(a_2-a_3)x &=& b_3-b_2 \\
x &=& \cfrac{b_3-b_2}{a_2-a_3}
\end{eqnarray}

よって、青の点x座標はx = \cfrac{b_3-b_2}{a_2-a_3}であることが分かりました。


あとはこれらの大小関係について調べればよいことになります。ここでは、「不必要であるかどうか」という不等式を作ります。
そのためには、先ほどの議論により、
青の点x座標\leq赤の点x座標
とすれば良いです。

今、a_1\geq a_2\geq a_3であることから、a_1-a_2\geq 0及びa_2-a_3\geq 0であるので、

\displaystyle \begin{eqnarray}
\cfrac{b_3-b_2}{a_2-a_3} &\leq & \cfrac{b_2-b_1}{a_1-a_2} \\
(b_3-b_2)(a_1-a_2) &\leq & (b_2-b_1)(a_2-a_3) \\
(b_3-b_2)(a_2-a_1) &\geq & (b_2-b_1)(a_3-a_2) 
\end{eqnarray}

よって、この式を満たしているとき、直線l_2:y=a_2x+b_2が不必要であることが分かりました。




以上をまとめると2つのクエリは、

  • 直線の追加するクエリ\cdots直線を追加する位置を二分探索で求める。その際、追加によって不必要となる直線は取り除く。
  • 最小値を求めるクエリ\cdots最小値を取る直線を二分探索で求める。

とすることで、直線N本、最小値クエリQ回とすると、全体の計算量はO((N+Q)\log N)となることが分かりました。

特殊な状況における更なる高速化

上記では、どのようなクエリ群であっても最小値を求められるものを説明しました。

ここでは、そのクエリ群がある条件を満たしているようなときに、より高速化が可能であるため、それについて解説していきます。

追加クエリにおける直線の傾きが単調であるとき

「追加クエリにおける直線の傾きが単調」とは、始め直線集合が空である状態から、直線l_i:y=a_ix+b_iを、i=1,2,3,\cdotsと追加していくときに、その傾きa_ia_1\geq a_2\geq a_3\geq \cdots(あるいはa_1\leq a_2\leq a_3\leq \cdots)であることを指します。


このとき、先ほど述べたように直線の挿入位置を二分探索で調べる必要はなく、常に先頭、あるいは末尾に追加していくことになるため、直線の本数N本とすると、追加クエリの計算量はO(N)となります。

最小値クエリにおけるxが単調であるとき

「最小値クエリにおけるxが単調」とは、最小値クエリにおいて与えられるx_ix_1\geq x_2\geq x_3\geq \cdots(あるいはx_1\leq x_2\leq x_3\leq \cdots)であることを指します。


このとき、最小値クエリにおけるxを進めると、直線集合の先頭の直線が最小値を取らなくなるときがあります。すると、xは後戻りしないため、もうこの直線は使わないことが分かります。よって、直線集合の先頭からも直線を取り除くようにすることで、最小値クエリを行うときは常に直線集合の先頭の直線が最小値を取ることになるため、最小値クエリ1回にかかる計算量はO(1)となります。
f:id:satanic0258:20160815211119p:plain
(図における色付きの直線は最小値を取らなくなったもの)

上記2パターンを両方満たしているとき

つまり、「追加クエリにおける直線の傾きも単調」であり「最小値クエリにおけるxも単調」であるようなときを指します。


このときは、直線の本数N本、最小値クエリの回数をQ回とすると、その計算量はO(N+Q)となるため、条件が無い時に比べて\log N分速くクエリをこなすことが出来ます。


コード(C++)

※注:このコードは追加クエリが単調であると仮定したものです。
(力不足で一般的な状況のものが出来ていません\cdots。書きかけのものを一応ここに残しておきます)

#include <algorithm>
#include <functional>
#include <utility>
#include <vector>

template<typename T>
class ConvecHullTrick {
private:
	// 直線群(配列)
	std::vector<std::pair<T, T>> lines;
	// 最小値(最大値)を求めるxが単調であるか
	bool isMonotonicX;
	// 最小/最大を判断する関数
	std::function<bool(T l, T r)> comp;

public:
	// コンストラクタ ( クエリが単調であった場合はflag = trueとする )
	ConvecHullTrick(bool flagX = false, std::function<bool(T l, T r)> compFunc = [](T l, T r) {return l >= r; })
		:isMonotonicX(flagX), comp(compFunc)  {
		lines.emplace_back(0, 0);
	};

	// 直線l1, l2, l3のうちl2が不必要であるかどうか
	bool check(std::pair<T, T> l1, std::pair<T, T> l2, std::pair<T, T> l3) {
		if (l1 < l3) std::swap(l1, l3);
		return (l3.second - l2.second) * (l2.first - l1.first) >= (l2.second - l1.second) * (l3.first - l2.first);
	}

	// 直線y=ax+bを追加する
	void add(T a, T b) {
		std::pair<T, T> line(a, b);
		while (lines.size() >= 2 && check(*(lines.end() - 2), lines.back(), line))
			lines.pop_back();
		lines.emplace_back(line);
	}

	// i番目の直線f_i(x)に対するxの時の値を返す
	T f(int i, T x) {
		return lines[i].first * x + lines[i].second;
	}

	// i番目の直線f_i(x)に対するxの時の値を返す
	T f(std::pair<T, T> line, T x) {
		return line.first * x + line.second;
	}

	// 直線群の中でxの時に最小(最大)となる値を返す
	T get(T x) {
		// 最小値(最大値)クエリにおけるxが単調
		if (isMonotonicX) {
			static int head = 0;
			while (lines.size() - head >= 2 && comp(f(head, x), f(head + 1, x)))
				++head;
			return f(head, x);
		}
		else {
			int low = -1, high = lines.size() - 1;
			while (high - low > 1) {
				int mid = (high + low) / 2;
				(comp(f(mid, x), f(mid + 1, x)) ? low : high) = mid;
			}
			return f(high, x);
		}
	}
};

コードの説明

ほぼ先ほどの議論をそのままコードに書いています。
なお、関数はそれぞれ、

  • {\tt check}関数\cdots直線の不必要性を判断する
  • {\tt add}関数\cdots直線集合に直線を追加する
  • {\tt f}関数\cdots直線l_iに対するf_i(x)を返す
  • {\tt get}関数\cdots直線集合内でxのときの最小値を返す

となっています。


また、使うときには

ConvexHullTrick<int> cht(true);

といった感じで宣言します。
このとき、第一引数を{\tt true}{\tt false}にすることでそれぞれ最小値(最大値)クエリが単調であるか否かを指定することが出来ます(省略可)。
また、第二引数に、

ConvexHullTrick<int> cht(true, std::less<int>());

としたり、

ConvexHullTrick<int> cht(true, [](T l, T r) {return l <= r; });

とすることで最大値クエリをこなすことが出来ます。


具体例

実際に直線を追加していって、その後の最小値クエリの違いを見ていきます。

ソースコード

※ヘッダ、{\tt ConvexHullTrick}クラスは省略

int main() {
	ConvecHullTrick<int> cht(false);
	cht.add(2, 0);
	std::cout << "Add y=2x" << std::endl;
	std::cout << "min(f(-2)) = " << cht.get(-2) << std::endl;
	std::cout << "min(f(2)) = " << cht.get(2) << std::endl << std::endl;

	cht.add(0, -1);
	std::cout << "Add y=-1" << std::endl;
	std::cout << "min(f(-2)) = " << cht.get(-2) << std::endl;
	std::cout << "min(f(2)) = " << cht.get(2) << std::endl << std::endl;

	cht.add(1, 1);
	std::cout << "Add y=x+1" << std::endl;
	std::cout << "min(f(-2)) = " << cht.get(-2) << std::endl;
	std::cout << "min(f(2)) = " << cht.get(2) << std::endl << std::endl;

	cht.add(-1, 0);
	std::cout << "Add y=-x" << std::endl;
	std::cout << "min(f(-2)) = " << cht.get(-2) << std::endl;
	std::cout << "min(f(2)) = " << cht.get(2) << std::endl << std::endl;
	return 0;
}
出力
Add y=2x
min(f(-2)) = -4
min(f(2)) = 4

Add y=-1
min(f(-2)) = -4
min(f(2)) = -1

Add y=x+1
min(f(-2)) = -4
min(f(2)) = -1

Add y=-x
min(f(-2)) = -4
min(f(2)) = -2

上記例で行ったクエリを図にしてみると、次のようになっています。
f:id:satanic0258:20160816170731p:plain
これで、確かに正しく出力出来ていることが分かりました。


備考

前述のように、上記コードは全ての状況に対応出来るものではないので注意してください。


あとがき

使える機会は式を見て割と分かりやすいですが、実装は慣れていないと難しそうです。

そのため、問題を色々調べてみました(まだ全て解いてないです)。
3709 -- K-Anonymous Sequence
No.409 ダイエット - yukicoder
I: Live Programming - Japan Alumni Group Summer Camp 2015 Day 4 | AtCoder
Contest Page | CodeChef
Contest Page | CodeChef
Problem - E - Codeforces


このConvex-Hull Trickを用いることにより、計算量をO(NQ)からO((N+Q)\log N)へと高速化出来るため、覚えておくとどこかで役に立つと思います。