https://atcoder.jp/contests/abc433/tasks

A - Happy Birthday! 4

問題概要

整数 $X,Y,Z$ が与えられる。$X+A = Z(Y+A)$ を満たす $A \in \mathbb N$ が存在するかどうか判定しろ。

制約

$1 \le X,Y \le 100 \\ 2 \le Z \le 10$

解法

1. 愚直に $A$ を全探索する。
2. 式変形

$$ X+A = Z(Y+A) \\ X+A = ZY + ZA \\ A-ZA = ZY-X \\ A(1-Z) = ZY-X \\ A = \frac{ZY-X}{1-Z}

$$

B - Nearest Taller

問題

数列 $A$ が与えられる。$1 \le i \le N$ に対して $A_j > A_i (j<i)$ を満たすような $j$ が存在するかどうか判定し、存在するならば一番 $i$ に近い $j$ を出力しろ。

制約

$1 \le N \le 100 \\ 1 \le A_i \le 100$

解法

1. 愚直
2. Stack

空の Stack を用意して数列を前から見ていく。Stack は数列の要素と添字の２つをもたせる。

Stack の top が $A_i$ よりも大きいなら、その要素が答えになる。違うならば pop して $A_i$ よりも大きい要素が出てくるか空になるまで pop し続ける。