No.2974 関数の芽
タグ : / 解いたユーザー数 8
作問者 : 👑
p-adic
/ テスター :
hiro1729
👑 
binap
問題文
まずは用語を導入します。$f(x)$ と $g(x)$ を実数全体を定義域に持つ実数値関数とし、$x_0$ を実数とします。$f(x)$ と $g(x)$ が $x = x_0$ の近傍で一致するとは、次の条件を満たす正実数 $\delta$ が存在するということです：
- $|x - x_0| < \delta$ を満たす任意の実数 $x$ に対し、$f(x) = g(x)$ である。
つまり大雑把に言うと、$x_0$ の十分小さい近傍に制限すれば $f(x)$ と $g(x)$ の値が一致するということです。
入力の最初に正整数 $Q$ が与えられます。
実数全体を定義域に持つ $2$ つの実数値関数 $F(x)$ と $G(x)$ が共に恒等的に $0$ の値を取る定数関数として与えられています。
以下で説明される $Q$ 個のクエリを与えられた順に処理してください。
各クエリは $5$ 個の整数 $K, L, M, N, X$ の組 $(K,L,M,N,X)$です。
クエリ $(K,L,M,N,X)$ は以下のように処理します：
- まず関数 $F(x)$ を、自身に $\max \{0,Kx+L\}$ を足して得られる関数に置き換えることで更新します。
- 次に関数 $G(x)$ を、自身に $\max \{0,Mx+N\}$ を足して得られる関数に置き換えることで更新します。
- 最後に更新後の $F(x)$ と $G(x)$ に対し「$F(x)$ と $G(x)$ が $x = X$ の近傍で一致する」という命題の真偽を判定してください。（以下この真偽を、このクエリに対する回答と呼ぶ）
背景
芽の理論を知っている人向けに背景を説明します。$f(x)$ と $g(x)$ を実数全体を定義域に持つ実数値関数とし、$x_0$ を実数とします。$f(x)$ と $g(x)$ が $x = x_0$ の近傍で一致することは、$f(x)$ と $g(x)$ の $x = x_0$ における芽が一致するということに他なりません。つまりこの問題は関数の芽が一致するか否かを判定する問題と等価です。
芽という概念自体は関数だけでなく層の切断というより一般の概念に対しても定義されます。関数の芽は主に解析学や複素幾何などで用いられますが、層の切断の芽は代数幾何学や圏論などにおいて非常に重要な役割を持ちます。
入力
$Q$ 以下の各正整数 $q$ に対し、$q$ 個目のクエリを $(K_q,L_q,M_q,N_q,X_q)$ と書き表します。
この時、入力は以下の形式で標準入力から $1 + Q$ 行で与えられます：
- $1$ 行目に $Q$ が与えられます。
- $Q$ 以下の各正整数 $q$ に対し、$1+q$ 行目に $q$ 個目のクエリ $(K_q,L_q,M_q,N_q,X_q)$ の各成分が半角空白区切りで与えられます。
$Q$ $K_1$ $L_1$ $M_1$ $N_1$ $X_1$ $\vdots$ $K_Q$ $L_Q$ $M_Q$ $N_Q$ $X_Q$
制約
入力は以下の制約を満たします：
- $Q$ は $1 \leq Q \leq 10^5$ を満たす整数
- $Q$ 以下の任意の正整数 $q$ に対し、
- $K_q$ は $-10^9 \leq K_q \leq 10^9$ を満たす整数
- $L_q$ は $-10^9 \leq L_q \leq 10^9$ を満たす整数
- $M_q$ は $-10^9 \leq M_q \leq 10^9$ を満たす整数
- $N_q$ は $-10^9 \leq N_q \leq 10^9$ を満たす整数
- $X_q$ は $-10^9 \leq X_q \leq 10^9$ を満たす整数
出力
$Q$ 以下の各正整数 $q$ に対し、$q$ 個目のクエリに対する回答が真である場合はYesと、偽である場合はNoと $q$ 行目に出力してください。
最後に改行してください。
サンプル
サンプル1
入力
1 0 1 1 0 0
出力
No
最初は $F(x)$ と $G(x)$ が $0$ のみを値に持つ定数関数として与えられています。
クエリ $(K_1,L_1,M_1,N_1,X_1) = (0,1,1,0,0)$ により、$F(x)$ と $G(x)$ は
$\displaystyle \begin{array}{rclclcl} \displaystyle F(x) &\displaystyle = &\displaystyle 0 + \max \{0,K_1 x+L_1\} &\displaystyle = &\displaystyle 0 + \max \{0,1\} &\displaystyle = &\displaystyle 1 \\ \displaystyle G(x) &\displaystyle = &\displaystyle 0 + \max \{0,M_1x+N_1\} &\displaystyle = &\displaystyle 0 + \max \{0,x\} &\displaystyle = &\displaystyle \max \{0,x\} \end{array} $
に置き換わります。更新後の $F(x)$ と $G(x)$ について、
$\displaystyle \begin{array}{rclcl} \displaystyle F(X_1) &\displaystyle = &\displaystyle F(0) &\displaystyle = &\displaystyle 1 \\ \displaystyle G(X_1) &\displaystyle = &\displaystyle G(0) &\displaystyle = &\displaystyle 0 \end{array} $
が成り立ち $F(X_1) \neq G(X_1)$ であるので、特に $X_1$ の近傍をどのように小さく取っても $F(x)$ と $G(x)$ の制限は一致しません。今回は $Q = 1$ なので、これで全てのクエリが処理できました。
サンプル2
入力
1 0 1 1 0 1
出力
No
サンプル1との違いはクエリの $X_1$ 部分のみです。従って更新後の $F(x)$ と $G(x)$ は
$\displaystyle \begin{array}{rcl} \displaystyle F(x) &\displaystyle = &\displaystyle 1 \\ \displaystyle G(x) &\displaystyle = &\displaystyle \max \{0,x\} \end{array} $
となります。今回は
$\displaystyle \begin{array}{rclcl} \displaystyle F(X_1) &\displaystyle = &\displaystyle F(1) &\displaystyle = &\displaystyle 1 \\ \displaystyle G(X_1) &\displaystyle = &\displaystyle G(1) &\displaystyle = &\displaystyle 1 \end{array} $
が成り立つので $F(X_1) = G(X_1)$ となりますが、正の実数 $\delta$ をどのように小さく取っても $x = X_1 + 2^{-1} \delta$ において $|x - X_1| = 2^{-1} \delta < \delta$ かつ
$\displaystyle \begin{array}{rclcl} \displaystyle F(x) &\displaystyle = &\displaystyle F(1 + 2^{-1} \delta) &\displaystyle = &\displaystyle 1 \\ \displaystyle G(x) &\displaystyle = &\displaystyle G(1 + 2^{-1} \delta) &\displaystyle = &\displaystyle 1 + 2^{-1} \delta \end{array} $
であり $F(x) \neq G(x)$ となります。すなわち $X_1$ の近傍をどのように小さく取っても $F(x)$ と $G(x)$ の制限は一致しません。今回は $Q = 1$ なので、これで全てのクエリが処理できました。
サンプル3
入力
2 2 0 2 -1 -2 -1 -1 0 1 1
出力
Yes Yes
最初は $F(x)$ と $G(x)$ が $0$ のみを値に持つ定数関数として与えられています。
$1$ 個目のクエリ $(K_1,L_1,M_1,N_1,X_1) = (2,0,2,-1,-2)$ により、$F(x)$ と $G(x)$ は
$\displaystyle \begin{array}{rclclcl} \displaystyle F(x) &\displaystyle = &\displaystyle 0 + \max \{0,K_1x+L_1\} &\displaystyle = &\displaystyle 0 + \max \{0,2x\} &\displaystyle = &\displaystyle \max \{0,2x\} \\ \displaystyle G(x) &\displaystyle = &\displaystyle 0 + \max \{0,M_1x+N_1\} &\displaystyle = &\displaystyle 0 + \max \{0,2x-1\} &\displaystyle = &\displaystyle \max \{0,2x-1\} \end{array} $
に置き換わります。更新後の $F(x)$ と $G(x)$ はいずれも $x < 0$ ならば $0$ の値を取ることに注意すると、例えば $\delta = 2$ と定めれば $|x - X_1| < \delta$ を満たす任意の実数 $x$ に対し $x < X_1 + \delta = 0$ より $F(x) = G(x)$ となります。
$2$ 個目のクエリ $(K_2,L_2,M_2,N_2,X_2) = (-1,-1,0,1,1)$ により、$F(x)$ と $G(x)$ は
$\displaystyle \begin{array}{rclclcl} \displaystyle F(x) &\displaystyle = &\displaystyle \max \{0,2x\} + \max \{0,K_2x+L_2\} &\displaystyle = &\displaystyle \max \{0,2x\} + \max \{0,-x-1\} &\displaystyle = &\displaystyle \max \{0,2x,-x-1,x-1\} \\ \displaystyle G(x) &\displaystyle = &\displaystyle \max \{0,2x-1\} + \max \{0,M_2x+N_2\} &\displaystyle = &\displaystyle \max \{0,2x-1\} + \max \{0,1\} &\displaystyle = &\displaystyle \max \{1,2x\} \end{array} $
に置き換わります。$\delta = \frac{1}{2}$ と定めると、$|x - X_2| < \delta$ を満たす任意の実数 $x$ に対し $\frac{1}{2} < x < \frac{3}{2}$ より
$\displaystyle \begin{array}{lclcl} \displaystyle 2x - 0 &\displaystyle = &\displaystyle 2x &\displaystyle > &\displaystyle 0 \\ \displaystyle 2x - (-x-1) &\displaystyle = &\displaystyle 3x+1 &\displaystyle > &\displaystyle 0 \\ \displaystyle 2x - (x-1) &\displaystyle = &\displaystyle x+1 &\displaystyle > &\displaystyle 0 \\ \displaystyle 2x - 1 &\displaystyle &\displaystyle &\displaystyle > &\displaystyle 0 \end{array} $
となるので $F(x) = 2x$ かつ $G(x) = 2x$ すなわち $F(x) = G(x)$ となります。今回は $Q = 2$ なので、これで全てのクエリが処理できました。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。