Hop Step Jump

2 secs 1024 MB

一回の操作では $10 k$ マス進むので，操作後に高橋君が居るマスは $10$ の倍数の番号が付いたマスに限られます．そのようなマスのみに注目して時間計算量 $O(N^2)$ の素朴な DP を書けば，定数倍が非常に軽いため実行時間制限に間に合います．下記の実装例も参考にしてください．

想定解（C++）

xxxxxxxxxx
 
#include <bits/stdc++.h>
using namespace std;
​
constexpr long long MOD = 998244353;
​
int main() {
  int n; string s;
  cin >> n >> s;
​
  if (n % 10 != 0) {
    cout << 0 << endl;
    return 0;
  }
  
  vector<long long> dp(n / 10 + 1);
  dp[0] = 1;
​
  for (int i = 0; i < n / 10; i++) {
    for (int k = 1; k <= n / 10 - i; k++) {
      bool ok = true;
      if (s[i * 10 + 2 * k] == 'x') ok = false;
      if (s[i * 10 + (2 + 3) * k] == 'x') ok = false;
      if (s[i * 10 + (2 + 3 + 5) * k] == 'x') ok = false;
​
      if (ok) {
        dp[i + k] += dp[i];
        dp[i + k] %= MOD;
      }
    }
  }
​
  cout << dp[n / 10] << endl;
}
​

想定解（pypy3）

xxxxxxxxxx
 
n = int(input())
s = input()
​
MOD = 998244353
​
if n % 10 != 0:
    print(0)
    exit(0)
​
n2 = n // 10
​
dp = [0] * (n2 + 1)
dp[0] = 1
​
for i in range(n2):
    if dp[i] == 0:
        continue
​
    dp[i] %= MOD
​
    i10 = i * 10
    
    for k in range(1, n2 - i + 1):
        if s[i10 + 2 * k] == 'o' and s[i10 + 5 * k] == 'o' and s[i10 + 10 * k] == 'o':
            dp[i + k] += dp[i]
​
print(dp[n2] % MOD)
​

Hop Step Jump

解説

想定解（C++）

想定解（pypy3）