RUPC2018 day1 F: ごちうさ数

問題ページ
Aizu Online Judge Arena

解法

桁DPをする。dpテーブルを dp[i桁目][j,下3桁][k,N未満確定か][l,ごちうさ数か] とする。次の桁の数をnxtとしたとき下3桁は j%100*10 + nxt となる。N未満かは k || nxt < lim とする桁DPのよくあるやつで確認できる。下3桁とnxtを元にごちうさ数かどうかを確認できる。これらを用いて桁DPを更新していく。

ソースコード

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
#define int ll

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)

int dp[20][1005][2][2];
signed main(void)
{
  cin.tie(0);
  ios::sync_with_stdio(false);

  string s;
  cin >> s;
  int n = s.size();

  dp[0][0][0][0] = 1;
  REP(i, n) REP(j, 1000) REP(k, 2) REP(l, 2) {
    int lim = k ? 9 : s[i]-'0';
    REP(nxt, lim+1) {
      int cond = l || (j/100 == 5 && j%100/10 == 1 && nxt == 3);
      dp[i+1][j%100*10 + nxt][k || nxt < lim][cond] += dp[i][j][k][l];
    }
  }

  int ans = 0;
  REP(i, 1000) REP(j, 2) ans += dp[n][i][j][1];
  cout << ans << endl;

  return 0;
}