ABC196 E 解答

E - Filters (1650)

問題文

整数列 A = (a_1, a_2, … ,a_N), T = (t_1, t_2, … , t_N), X = (x_1, x_2, … , x_Q)が与えられます。N 個の関数 f_1(x), f_2(x),…, f_N(x)を、
f_i (x) =
x+a_i (t_i = 1)
max(x, a_i) (t_i = 2)
min(x, a_i) (t_i = 3)
と定義します。i = 1,2, … ,Qのそれぞれについて、f_N(…f_2(f_1(x_i))…)
を求めてください。

制約

入力は全て整数
1 ≤ N ≤ 2×10^5
1 ≤ Q ≤ 2×10^5
|a_i| ≤ 10^9
1 ≤ t_i ≤3
|x_i| ≤10^9

考察

問題を考える前に、まずは「関数」について私のイメージを説明します。「関数ぐらいもう知ってるよ」という方は飛ばしてください。

私はこの言葉を中学の数学で初めて聞きました。一次関数とか二次関数とか、高校だと三角関数など、数学を学ぶ時にとってもよく聞く言葉です。

簡単な関数の例を見てみます。

y = x + 2
(x,y)
(0,2)
(1,3)
(10,12)

この場合、x の値に +2 したものが答えです。

y = 3x
(x,y)
(0,0)
(1,3)
(10,30)

こちらは、x の値に *3 したものが答えです。これを絵にしてみます。

y = x + 2 という関数は「入力した値を+2して出力する箱」、y = 3x は「入力を*3して出力する箱」です。「あたりまえじゃん」と思うかもしれませんが、この考えが大切です。三角関数やなんか難しい数学の記号が並んでる関数も数多くありますが、やつらも全部箱です。内部で難しい処理をしてくれる箱なのです。

結局、関数とは

「なんかの数字を入れると、なんかの数字が出てくる不思議な箱」

です。こう考えておくと本問題が理解しやすいと思います。

ここから問題を考えていきます。本問題はいくつかの関数をまとめた（合成した）関数の出力を Q 個の数字分求めます。

愚直に全通り試したいのですが、制約から最大ケースで4*10^10 の計算回数になりますので、間に合いません。

そのため、いくつかの関数をまとめた関数はどんな関数になるのかについて考えます。上記の箱の説明を借りるのであれば

N 個の関数をまとめた箱に値を入力するとどんな値が出てくるのか？
その箱の中身考えていこう！

という箱の仕組みを考える問題になります。この箱さえ用意できれば、あとはQ 個の数字を入力するだけなので、計算時間は間に合いそうですね。

箱を構成する3つの関数の挙動を見ていきます。

まず、特別な処理を施さない（f_iが何もない）箱の挙動は y = xですね。グラフで書くとこうです。

次に3つの関数を施した場合は次のようになります。

です。この3つを組み合わせると、

こんな感じの形になります。これを見ると

１. aの合計値だけ上下に動いている。
２.ある値 r 以上は一定
３.ある値 l 以下は一定

ということがわかります。あとは、このある値 r と l を求めてあげれば良さそうです。これは、確実にある値より大きい、小さい数字を実際に関数に入れて計算してあげれば、その結果はその値になることから求まりそうです。

ということで、-INFと+INFから計算してあげましょう。そうすれば、ある値 r と l になります。

以上で箱の仕組みがわかりました。繰り返しとなりますが箱の特性をまとめます。

１. 入力は a の合計(S)だけ上下に動く（x+S）
２. x+Sがある値 r より大きければ r で一定
３. x+Sがある値 l より小さければ l で一定
４. l ≦ x+S ≦ rだったら x+Sとなる

です。これを実装してあげましょう。

実装

#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
#define reps(i,s,n) for(int i=s;i<n;++i)
using namespace std;
using ll = long long;
using P = pair<int, int>;

int main()
{
   int n,q;
   cin >> n;
   const ll INF = ll(1)<<60;
   ll l = -INF, r = INF;
   ll s = 0;
   rep(i,n)
   {
       ll a,t;
       cin >> a >> t;
       if(t == 1)
       {
           l += a;
           r += a;
           s += a;
       }
       else if(t ==2)
       {
           l = max(l,a);
           r = max(r,a);
       }
       else
       {
           l = min(l,a);
           r = min(r,a);
       }
   }
   cin >> q;
   rep(i,q)
   {
       ll x;
       cin >> x;
       x += s;
       ll ans = x;
       if(x <= l) ans = l;
       else if(r <= x) ans = r;
       printf("%ld\n",ans);
   }

   return 0;
}

あとがき

先に「やつらも全部箱」と書きましたが、「関数」と「方程式」は違ったりするので、なんでもかんでも箱というわけではないです。でも、箱のイメージを持っておけば何かと役に立つことが多いです。たとえば、ディープラーニングとかニューラルネットワークなどの難しそうな理論を理解するのにとても役に立ちます。と私は思ってます。やつらは、内部ですごく複雑な処理をしてくれる魔法の箱です。

こういう合成関数も慣れが必要な問題だな、と感じています。どんな箱になるのかを特定する練習を重ねていきたいです。