AtCoder Regular Contest 058 (ARC058)

7/15 に virtual でやったぶんを書きます

C - こだわり者いろはちゃん / Iroha's Obsession
D - いろはちゃんとマス目 / Iroha and a Grid
E - 和風いろはちゃん / Iroha and Haiku
F - 文字列大好きいろはちゃん / Iroha Loves Strings

C - こだわり者いろはちゃん / Iroha's Obsession

問題概要

いろはちゃんは $N$ 円のものを買おうとしているが、支払う金額の中にいろはちゃんの嫌いな $K$ 個の数字が含まれてはいけない。
いろはちゃんが支払う金額の最小値を求めてください。

解法

使える数字を $N$ より一桁多く並べることで確実に支払うことができるので、解は高々 $100 \times N$ です。ほんとはもうちょっと小さい。
$1 \leq N < 10000$ なので、 $N$ 以上の数のうち条件を満たす最小の数を全探索しても間に合います。
$O(N log N)$

int main() {
  int N, K;
  cin >> N >> K;

  bool dis[10] = {};
  for (int i = 0; i < K; ++i) {
    int D;
    cin >> D;
    dis[D] = true;
  }

  int ans = N;
  while (true) {
    bool f = false;
    int s = ans;
    while (s) {
      f |= dis[s % 10];
      s /= 10;
    }

    if (!f) break;
    ans++;
  }

  cout << ans << endl;
}

D - いろはちゃんとマス目 / Iroha and a Grid

問題概要

縦 $H$ マス、横 $W$ マスのマス目があります。1つ下か1つ右のマスに移動する操作だけを用いて左上から右下へ移動するパターンは何通りかを $mod 10^9 + 7$ で求めてください。ただし下から $A$ 個、左から $B$ 個のマス目は移動できません。

解法

C - 経路をします。

#include <bits/stdc++.h>
using namespace std;

constexpr int mod = 1e9 + 7;

struct ModCombination {
  ModCombination(unsigned int n) : n(n), F(n + 1, 1), I(n + 1, 1) {
    for (int i = 1; i <= n; ++i) F[i] = 1ll * i * F[i - 1] % mod;
    for (int64_t i = mod - 2, j = F[n]; i; i >>= 1) {
      if (i & 1) I[n] = I[n] * j % mod;
      j = j * j % mod;
    }
    for (int i = n - 1; i; --i) I[i] = I[i + 1] * (i + 1ll) % mod;
  }

  unsigned int n;
  vector<int> F, I;

  int operator()(int p, int k) {
    if (k < 0 || k > p) return 0;
    return 1ll * F[p] * I[k] % mod * I[p - k] % mod;
  }
};

int main() {
  int H, W, A, B;
  cin >> H >> W >> A >> B;
  ModCombination mC(H + W);

  int ans = 0;
  for (int i = B + 1; i <= W; ++i) {
    (ans += (int64_t)mC(H - A + i - 2, i - 1) * mC(W - i + A - 1, A - 1) % mod) %= mod;
  }

  cout << ans << endl;
}

E - 和風いろはちゃん / Iroha and Haiku

問題概要

長さ $N$ 、各値が $1 \sim 10$ の数列 $a$ を考えます。
$a_x + a_{x + 1} + ... + a_{y - 1} = X$
$a_y + a_{y + 1} + ... + a_{z - 1} = Y$
$a_z + a_{z + 1} + ... + a_{w - 1} = Z$
を満たす $0 \leq x < y < x < w \leq N$ が存在するような $a$ の個数を求めてください。

解法

$X + Y + Z$ の最大値が 17 と小さいため、これを利用します。
条件を満たしているかどうかの判断には直近の要素のうち合計が $X + Y + Z$ 以下になるようなものだけで十分なので、これを状態としてDPを行います。
値をそのまま持つのは筋が悪いので $5(10) \to 10000(2)$ みたいな感じでbitとして管理すると楽にDPできます。
公式の解説では条件を満たさない数列の個数を数え上げているけど、実装の難易度はそこまで変わらないと思う。

#include <bits/stdc++.h>
using namespace std;

constexpr int mod = 1e9 + 7;

int N, X, Y, Z, d;
int dp[64][1 << 17];

int rec(int idx = N, int bit = 0) {
  int &res = dp[idx][bit];
  if (~res) return res;

  if ((bit & d) == d) {
    res = 1;
    while (idx--) res = 10ll * res % mod;
    return res;
  }

  res = 0;
  if (idx == 0) return res;
  for (int i = 1; i <= 10; ++i) {
    (res += rec(idx - 1, ((bit << i) + (1 << (i - 1))) & ((1 << 17) - 1))) %= mod;
  }

  return res;
}

signed main(int argc, char *argv[]) {
  cin >> N >> X >> Y >> Z;
  d = (1 << (Z - 1)) + (1 << (Z + Y - 1)) + (1 << (Z + Y + X - 1));
  memset(dp, -1, sizeof(dp));

  cout << rec() << endl;
}

F - 文字列大好きいろはちゃん / Iroha Loves Strings

問題概要

ぱ

解法

眠たいので具体的には明日書く
その文字列をつかっても答えにたどり着けるかのDPをしたあとに余計なものをもたないよう気をつけてさらにDPします
迷走して無限時間とけた　困難

コードも見直してないので無駄が多いかも

#include <bits/stdc++.h>
using namespace std;

vector<int> Zalgorithm(string s) {
  vector<int> res(s.size());
  res[0] = s.size();
  int i = 1, j = 0;
  while (i < s.size()) {
    while (i + j < s.size() && s[j] == s[i + j]) ++j;
    res[i] = j;
    if (j == 0) {
      ++i;
      continue;
    }
    int k = 1;
    while (i + k < s.size() && k + res[k] < j) res[i + k] = res[k], ++k;
    i += k;
    j -= k;
  }

  return res;
}

int main() {
  int N, K;
  cin >> N >> K;

  vector<string> s(N + 1);
  for (int i = 1; i <= N; ++i) {
    cin >> s[i];
  }

  vector<bitset<10101>> reach(N + 1);
  reach.back().set(K);
  for (int i = N; i >= 1; --i) {
    reach[i - 1] = reach[i] | (reach[i] >> s[i].size());
  }

  vector<vector<bool>> dp(N + 1, vector<bool>(K + 10000, false));
  dp[0][0] = true;

  string ans;
  for (int i = 1; i <= N; ++i) {
    dp[i] = dp[i - 1];

    vector<int> d = Zalgorithm(s[i] + ans);
    for (int j = 0; j <= ans.size() && j + s[i].size() <= K; ++j) {
      int t = (j == ans.size() ? 0 : d[s[i].size() + j]);

      if (dp[i][j] && reach[i][j + s[i].size()] && (j == ans.size() || (t < s[i].size()) && (ans[j + t] > s[i][t]))) {
        ans = ans.substr(0, j) + s[i];
        for (int l = j + t + 1; l <= K; ++l) dp[i][l] = false;
        dp[i][j + s[i].size()] = true;
        break;
      }
    }
  }

  cout << ans << endl;
}