問題
枚の板について長さと設置できる上下限位置が与えられる。また個のボールが各座標に落とされる。板に一つもボールが落ちないような板の配置方法が何通りあるか求めよ。
解法
ボールが落ちる位置について累積和を取って、各板が設置可能な範囲を二分探索で求める。
反省
問題の把握にいくらか時間がかかったのと、端の関係とか二分探索の含める含めない、範囲指定などでかなり混乱した。
コード
#include"bits/stdc++.h" using namespace std; using ll = int64_t; class YetAnotherIncredibleMachine { public: int countWays(vector<int> platformMount, vector<int> platformLength, vector<int> balls) { constexpr int MAX = 2e5; vector<int> num(2 * MAX + 2, 0); int* p = &num[MAX + 1]; for (int b : balls) { p[b]++; } for (int i = -MAX; i < MAX; i++) { p[i + 1] += p[i]; } constexpr ll MOD = 1e9 + 9; ll ans = 1; for (int i = 0; i < platformMount.size(); i++) { ll curr_pattern = 0; //可能な左端についてループする for (int l = platformMount[i] - platformLength[i]; l <= platformMount[i]; ) { if (p[l] == p[l - 1] + 1) { l++; continue; } int n = p[l]; int r = upper_bound(&p[l], &p[platformMount[i] + platformLength[i] + 1], n) - &p[0]; curr_pattern += max(r - l - platformLength[i], 0); curr_pattern %= MOD; l = r; } ans *= curr_pattern; ans %= MOD; } return ans; } };