D - パンライン問題

この問題は数学的に抽象化することで簡単に解くことができます。

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

int main() {
  ll t;
  cin >> t;
  while (t--) {
    ll n, sum = 0;
    cin >> n;
    vector<ll> arr(n);
    for (auto &x : arr) {
      cin >> x;
      sum += x;
    }
    for (ll i = 1; i < n; i++) {
      arr[i] = min(arr[i], arr[i - 1] + 1);
    }
    for (ll i = n - 2; i >= 0; i--) {
      arr[i] = min(arr[i], arr[i + 1] + 1);
    }
    for (auto &x : arr) {
      sum -= x;
    }
    cout << sum << "\n";
  }
  return 0;
}

E - 登攀シルバー

この問題は、シミュレーションによって直接解くことができます。

#include <bits/stdc++.h>

using namespace std;

const int N = 5050;
int n, m, c;
string grid[N];
bool visited[N][N];
int sam[N][N];

void solve() {
    cin >> n >> c;
    for (int i = 1; i <= n; ++i) {
        cin >> grid[i];
        grid[i] = " " + grid[i];
    }
    m = grid[1].size() - 1;

    for (int i = 1; i <= m; ++i) {
        sam[n][i] = (grid[n][i] == '#');
    }

    visited[n][c] = true;
    for (int i = n - 1; i >= 1; --i) {
        for (int j = 1; j <= m; ++j) {
            if (grid[i][j] == '.') {
                if (visited[i + 1][j - 1] || visited[i + 1][j] || visited[i + 1][j + 1]) {
                    visited[i][j] = true;
                }
                sam[i][j] = sam[i + 1][j];
            } else {
                if ((visited[i + 1][j - 1] || visited[i + 1][j] || visited[i + 1][j + 1]) && sam[i + 1][j] == 0) {
                    visited[i][j] = true;
                    sam[i][j] = sam[i + 1][j];
                } else {
                    sam[i][j] = sam[i + 1][j] + 1;
                }
            }
        }
    }

    for (int i = 1; i <= m; ++i) {
        cout << visited[1][i];
    }
    cout << "\n";
}

F - 非増加数

この問題はBFSと適切な最適化を組み合わせて解くことができます。

#include <bits/stdc++.h>

using namespace std;

int n;
bool visited[100005][10];
map<int, pair<int, int>> parent;
queue<pair<int, int>> q;

void printPath(int x, int y) {
    vector<int> path;
    for (int u = x, v = y; v != -1;) {
        path.push_back(v);
        auto p = parent[u];
        u = p.first;
        v = p.second;
    }
    reverse(path.begin(), path.end());
    for (auto num : path) cout << num;
}

void bfs() {
    for (int i = 1; i <= 9; ++i) {
        if (i % n == 0) {
            cout << i;
            return;
        }
        q.push({i % n, i});
        visited[i % n][i] = true;
        parent[i] = {0, -1};
    }

    while (!q.empty()) {
        auto u = q.front(); q.pop();
        for (int j = u.second; j <= 9; ++j) {
            int next_mod = (u.first * 10 + j) % n;
            if (!visited[next_mod][j]) {
                visited[next_mod][j] = true;
                parent[next_mod] = {u.first, j};
                q.push({next_mod, j});
            }
            if (visited[0][j]) {
                printPath(0, j);
                return;
            }
        }
    }
    cout << -1;
}

void solve() {
    cin >> n;
    bfs();
}