まずは高橋君だけの場合を考えます。
山$i$の高さを$h_i$とおきます。定義より、$i = 1$のときは$h_i = T_i$です。それ以外の場合、ひとつ前の地点の最大値と今の地点の最大値を比べ、異なれば高さは$T_i$となり、同じであれば高さは$T_i$以下となります。この文章を数学的に表現すると、次のようになります。
同様に、青木君だけの場合を考えると、次のようになります。
独立した2つの命題を合わせて、真偽値表を作ります。
| $P(i)$ | $\lnot P(i)$ | |
|---|---|---|
| $Q(i)$ | $(h_i = T_i) \land (h_i = A_i)$ | $(h_i \le T_i) \land (h_i = A_i)$ |
| $\lnot Q(i)$ | $(h_i = T_i) \land (h_i \le A_i)$ | $(h_i \le T_i) \land (h_i \le A_i)$ |
この問題は、上の表を満たす$h_1, h_2, \ldots, h_N$が何通りあるかを求める問題と同じです。ということで、各命題について見ていきます。
$T_i = A_i$のとき、$h_i = T_i$とすることで条件を満たします。$h_i$の取る値はこれ以外に存在しないため、1通りです。
$T_i \not= A_i$のとき、条件を満たす$h_i$は存在しないため、0通りです。
$T_i \ge A_i$のとき、$h_i = A_i$とすることで条件を満たすため、1通りです。
$T_i \lt A_i$のとき、条件を満たす$h_i$は存在しないため、0通りです。
$T_i \le A_i$のとき、$h_i = T_i$とすることで条件を満たすため、1通りです。
$T_i \gt A_i$のとき、条件を満たす$h_i$は存在しないため、0通りです。
各山の高さは正の整数であることを考慮すると、$h_i$の取りうる値の範囲は$1 \le h_i \le \min(T_i, A_i)$だとわかります。したがって、$\min(T_i, A_i)$通りです。
このようにして各$i$について通り数を求め、すべてを掛け合わせたものが答えです。
ソースコードはこちらです。考察がそのまま実装に反映されていることがわかります。
数学の力を借りることで考察が捗る問題でした。もし数学の力を借りずに解こうとすると、WAが取れずに困る可能性が高いと思います。僕の場合、最初は感覚で解こうとしてWAを出しました。その後の修正も感覚による修正でACを出しました（反省すべき点です）。
数学の力を借りることに対して億劫になりがちですが、きちんと問題を解こうとすると避けられないので、これからは、時間がかかってもいいので数学を使ってきちんと考察していこうと思います。