CODEFORCES 1139 A. Even Substrings

問題概要

$N$桁の数字だけで構成された文字列$s$が与えられる。

$s$の部分文字列$s[l...r]$が偶数になるような$[l, r]$の組み合わせの総数を求めよ。

制約

$1\ \leq \ N\ \leq 65000$
time limit per test 0.5sec

問題へのリンクはこちら

考察

$N$の最大値が$65000$なので、$l,\ r$を全探索して部分文字列を一つずつ検証する方法をとることはできない。

そのため、次のような１次元DPを考えた。

DPの定義

$$ dp[i]: i桁目までの偶数の個数の総和 $$

このように定義すると、$0$桁目には文字が存在しないので、$dp[0] = 0$となる。

DPの遷移

上で定義したDPの遷移を考える。この際、偶奇に場合わけして考える。

1. 奇数の場合

$i+1$桁目が奇数の場合は、$i$桁目までの総数のままである。

2. 偶数の場合

例として、1234と言う文字列が与えられた場合を考えてみる。この場合、2桁目に初めて偶数が現れる。２が現れた時、$[1, 2]$, $[2, 2]$の２組が偶数になる。同様に、4桁目も考えると、$[1, 4]$, $[2, 4]$, $[3, 4]$, $[4, 4]$の4組が偶数になる。

つまり、i桁目が偶数ならば、i組の偶数ができると言い変えることができる。

3. まとめ

上記の1. 2. を踏まえると、次のように遷移することが言える

$$ i桁目が奇数の時: dp[i+1] = dp[i]\ \ \ \ \ \ \\ i桁目が偶数の時: dp[i+1] = dp[i] + i $$

実装

実装は以下の通りになる。0-indexedに注意して実装することを忘れないようにしたい。

#include <iostream>
#include <string>
using namespace std;
const int MAXN = 65010;
int dp[MAXN];

int main() {
  int N; cin >> N;
  string s; cin >> s;
  for(int i = 0; i < N; ++i) {
    dp[i+1] = dp[i] + (int(s[i]) % 2 == 0 ? i+1 : 0);
  }
  cout << dp[N] << endl;
  return 0;
}