Educational Codeforces Round 98 D - Radio Towers - 輪郭をなぞるだけのブログ

こういう問題を素早く解けるようになりたい。

リンク

問題概要

$[0, n+1]$ の $n+2$ 個の街がある。街 $[1,n]$ には $\frac{1}{2}$ の確率で電波塔が設置される。電波塔のパワー $p$ は自由に設定でき、距離が $p$ 未満の街に電波が供給される。街 $0$ と街 $n+1$ には電波が供給されず、 $[1, n]$ に重複なしで電波が供給されるように電波塔が設置される確率を $mod\ 998244353$ で求める。

制約

$1 \leq n \leq 2 \times 10^5$

考察

設置する個数を固定するなどが浮かぶが、今回は素直な DP で解くことができる。

$dp[i] :=$ 電波が到達していない連続する区間の長さが $i$ のときの条件を満たす電波塔の設置方法の総数
と定義する。

これがどこから遷移されたかを考えるために、最初の行動で場合分けをする。
この問題の場合、左から見て一番最初に置かれる電波塔がどこであるかで場合分けする。

例えば、 $i=5$ の場合は以下のようになる。
f:id:OutLine:20201120223821j:plain
真ん中の、左から $2$ つ目の街に電波塔を設置する場合を考えてみる。
街 $1$ に電波を供給する必要があるため、パワーは $p=2$ にしなければいけない。( 街 $0$ には電波を供給しない。)
すると、街 $3$ まで電波は供給される。
残りは街 $4$ と街 $5$ に電波を供給するように電波塔を設置しなければいけないが、これは $dp[2$ ] に等しい。

一般に、
$dp[i] = dp[i - 1] + dp[i - 3] + ...$
である。
愚直にやると更新に $O(n)$ かかってしまうが、累積和を取っておくことで更新が $O(1)$ でできる。
累積和は $mod\ 2$ 上で取っていく。

求めるものは確率であるので、
$dp[n] \ /\ 2^n$
を出力すればよい。

コード

#include <iostream>
#include <vector>
using namespace std;

constexpr int mod = 998244353;
struct mint { /* mod 上での演算を定義 */ };

int main(){
    int n;
    cin >> n;
    
    vector<mint> dp(n + 1), sum(n + 1);
    dp[0] = dp[1] = 1;
    sum[0] = sum[1] = 1;
    
    for(int i = 2; i <= n; ++i){
        // dp[i] = dp[i - 1] + dp[i - 3] + ...
        //       = sum[i - 1]
        dp[i] = sum[i - 1];
        
        // mod2 における累積和を取る
        sum[i] = sum[i - 2] + dp[i];
    }
    
    cout << dp[n] / mint(2).pow(n) << '\n';
}