CODE FESTIVAL 2016 qual C C - 二人のアルピニスト を解きました
🦁
これを解きました：CODE FESTIVAL 2016 qual C C - 二人のアルピニスト
山が左から右へ1からNまであって、左端から山iまでの最大値がT_i、右橋から山iまでの最小値がA_iのときに、山の高さのあり得る場合の数を答える問題。山の高さは正の整数。T_iとA_iは矛盾してることもある。
左から見ていった場合、値が変わる瞬間が大事で、T_(i-1)=1でT_i=2なら、山iは2で確定する。このとき、Aの方は、A_iが2以上なら矛盾しないが、2未満だったら明らかに矛盾。
右から見ていった場合も、値が変わるポイントを同じように見る。
T_(i-1)=T_iで、A_i=A_(i+1)のときは、山iの高さは1つには確定しない。最大値を更新しない値なら何でもよくて、具体的には、T_iかA_iのmin以下の正の整数だったらなんでもいい。
以上のことを踏まえて実装する。
実装するときは、TもAも1からNまでに格納して、T[N+1]=T[N]、A{0]=A[1]とすると、端っこで場合分けをせずに、値が変わる瞬間を調べられるので便利。
解説を見ても、同じ感じで考えてた。