ARC060

AtCoder Regular Contest 060 - AtCoder Regular Contest 060 | AtCoder
微妙な結果。
C:合計と枚数を持ってDP。
　すぐ解けたのにオーバーフローに気づかず部分点しか取れませんでした。非常に悲しい。
　ご丁寧に32ビットには収まらないって書いてあるのにvector> dpって……。
　疲れてるのかなあ。

#include <bits/stdc++.h>
using namespace std;
const int INF = 1000000000;
#define REP(i,s,n) for(int i=(int)(s);i<(int)(n);++i)
#define rep(i,n) REP(i, 0, n)
typedef long long int i64;
typedef pair<int, int> pint;

int main() {
    int N, A; cin >> N >> A;
    vector<int> X(N);
    rep(i, N) cin >> X[i];
    vector<vector<i64>> dp(N + 1, vector<i64>(2510, 0));
    dp[0][0] = 1LL;
    rep(i, N) {
        auto dp_ = dp;
        int x = X[i];
        rep(j, N) REP(k, x, 2510) {
            dp_[j + 1][k] += dp[j][k - x];
        }
        dp = dp_;
    }
    i64 ans = 0LL;
    REP(i, 1, N + 1)
      ans += dp[i][i * A];
    cout << ans << endl;
    return 0;
}

D: 解説を見てもイマイチ理解できず。こういうのめっちゃ苦手。

E:　部分点

#include <bits/stdc++.h>
using namespace std;
const int INF = 1000000000;
#define REP(i,s,n) for(int i=(int)(s);i<(int)(n);++i)
#define rep(i,n) REP(i, 0, n)
typedef long long int i64;
typedef pair<int, int> pint;

vector<int> X; int L;
int memo[1000][1000];
int dfs(int from, int to) {
    if(from >= to) return 0;
    int& res = memo[from][to];
    if(res != -1) return res;
    int now = X[from];
    int nxt = upper_bound(X.begin(), X.end(), now + L) - X.begin() - 1;
    return res = dfs(nxt, to) + 1;
}
int main() {
    cin.tie(0); ios::sync_with_stdio(false);
    int N; cin >> N;
    assert(N <= 1000);
    X.resize(N);
    rep(i, N) cin >> X[i];
    int Q; cin >> L >> Q;
    assert(Q <= 1000);
    memset(memo, -1, sizeof(memo));
    rep(i, Q) {
        int a, b; cin >> a >> b;
        --a; --b;
        if(a > b) swap(a, b);
        cout << dfs(a, b) << '\n';
    }
    return 0;
}

　ダブリング（繰り返し二乗法の一般化みたいなやつ）を使えば解けるらしいんですが。

F：　無理っぽい。

(◞‸◟)

追記

D問題

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

#define REP(i,s,n) for(int i=(int)(s);i<(int)(n);++i)
#define rep(i,n) REP(i, 0, n)
typedef long long int i64;
typedef pair<int, int> pint;

const i64 INF = 1.0e18;
constexpr i64 f(i64 b, i64 n) {
    return n < b ? n : f(b, n / b) + n % b;
}
int main() {
    i64 N, S; cin >> N >> S;
    if(S == N) {
        cout << N + 1 << endl;
        return 0;
    }
    i64 rootN = static_cast<i64>(sqrt(N - 0.0));
    i64 ans = INF;
    for(i64 b = 2LL; b <= rootN; ++b)
      if(f(b, N) == S)
        ans = min(ans, b);
    if(N < S) goto skip;
    for(i64 p = 1; p <= rootN; ++p) {
        i64 b = (N - S) / p + 1;
        if(b != 1LL && f(b, N) == S)
          ans = min(ans, b);
    }
  skip:
    cout << (ans == INF ? -1 : ans) << endl;
    return 0;
}

ルートNで場合分けするというの、言われてみればそれはそうという感じで非常に悔しいですね……。むう……。

それはそうとMSYS2にgcc5.3が気がついたら入ってたんですけどエラーとか見やすくていい感じですね。
WSLも入ったし（全然使ってないけど）Windowsでもまだまだやれそう……？