新入生歓迎数列 - Easy [技術室奥プログラミングコンテスト #3 C]

https://beta.atcoder.jp/contests/tkppc3/tasks/tkppc3_c

考察過程

1. 区間積の中でPとなるものを探す問題と言えるが、積というのは数がどんどん大きくなる
2. 最小の2をかけていっても、30回くらいで10^9を超える
3. そのため、左側を固定しても右側は30個くらい見ればいい
4. 1があると数が大きくならないので30回以上必要になりそうだが、今回の問題の要件では1は必要ない
5. 1を取り除けば、左端を固定して右側を探索していっても間に合う

解法

https://beta.atcoder.jp/contests/tkppc3/submissions/2840790

前処理として配列Aから1を取り除いて配列Bを作っておこう。
あとは、配列Bについて左端について全探索しながら、それぞれについて右端を探す。
右端は左端から1つずつ伸ばしていってP未満なら伸ばすという操作をしていけばいい。
ひたすら伸ばしてしまいそうだが、30回ほど伸ばせば必ずP以上となるので、大丈夫。

int N, P, A[101010];
int M, B[101010];
//---------------------------------------------------------------------------------------------------
#define yes "Yay!"
#define no ":("
string solve() {
    rep(i, 0, M) {
        ll x = B[i];
        int j = i + 1;
        while (x < P and j < M) {
            x *= B[j];
            j++;
        }
        if (x == P) return yes;
    }
 
    return no;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> P;
    rep(i, 0, N) cin >> A[i];
 
    rep(i, 0, N) if (1 < A[i]) B[M] = A[i], M++;
 
    cout << solve() << endl;
}