yukicoder No.6 使いものにならないハッシュ

No.6 使いものにならないハッシュ - yukicoder

問題概要

で素数の連続部分列のうち、桁和ハッシュ( 桁になるまで行う)が衝突しない最大のものを求めよ。

解法

しゃくとり実装面倒だったのでズルをした。素数の個数が対数オーダー、かつハッシュがたかだか 種類だったので全探索で余裕で通る。

vector<ll> prime(ll n) {
    vector<ll> Prime(n + 1);
    rep(i, n + 1) Prime[i] = 1;
    Prime[0] = Prime[1] = 0;
    rep(i, n + 1) {
        if (Prime[i]) {
            rep(j, n / i - 1) Prime[i * (j + 2)] = 0;
        }
    }
    return Prime;
}

ll Hash(ll n) {
    if (n < 10) return n;
    ll S = 0;
    while (n) S += n % 10, n /= 10;
    return Hash(S);
}

int main() {
    ll N, K;
    cin >> K >> N;
    vector<ll> P = prime(N), Q;
    inc(i, K, N) if (P[i]) Q.pb(i);
    ll res, max = 0;
    rep(i, Q.size()) {
        map<ll, ll> M;
        rep(j, Q.size() - i) {
            if (M[Hash(Q[i + j])]++) {
                if (max <= j) {
                    max = j;
                    res = Q[i];
                }
                goto end;
            }
        }
        if (max <= Q.size() - i) {
            max = Q.size() - i;
            res = Q[i];
        }
    end:;
    }
    cout << res << endl;
}

yukicoder No.2 素因数ゲーム

No.2 素因数ゲーム - yukicoder

問題概要

からはじめて、二人交互に、素因数を一つ決めて任意回数ずつ割っていく。先に にした人の勝ち。

解法

典型。素因数分解した後、NimのXOR判定条件を用いる。

struct Factor {
    inline vector<ll> factorize(ll N) {
        vector<ll> A;
        while (N != 1) {
            inc(i, 2, sqrt(N)) {
                if (N % i == 0) {
                    A.push_back(i);
                    N /= i;
                    goto next;
                }
            }
            A.push_back(N);
            break;
        next:;
        }
        sort(all(A));
        return A;
    }
}

int main() {
    ll N, res = 0;
    cin >> N;
    Factor F;
    vector<ll> A = F.factorize(N);
    map<ll, ll> M;
    rep(i, A.size()) M[A[i]]++;
    each(i, M) res ^= i.se;
    cout << (res ? "Alice" : "Bob") << endl;
}

yukicoder No.1 道のショートカット

今日から、yukicoderの星 〜 を全埋めしていこうと思います。

No.1 道のショートカット - yukicoder

問題概要

辺のコストが費用、距離の つあるDAGにおいて、費用が 以下になるように頂点 から頂点 へ移動する(距離の)最短経路を求める。

解法

典型。状態 (頂点, 費用) を持ってダイクストラ。

int main() {
    ll N, M, K;
    cin >> N >> K >> M;
    ll A[M], B[M], C[M], D[M];
    ll DP[N][K + 1], used[N][K + 1];
    vector<pair<ll, pair<ll, ll>>> V[N];
    rep(i, M) cin >> A[i];
    rep(i, M) cin >> B[i];
    rep(i, M) cin >> C[i];
    rep(i, M) cin >> D[i];
    rep(i, M) V[A[i] - 1].pb({B[i] - 1, {C[i], D[i]}});
    rep(i, N) rep(j, K + 1) DP[i][j] = INF, used[i][j] = 0;
    rpriority_queue<pair<ll, pair<ll, ll>>> P;
    P.push({0, {0, 0}});
    while (P.size()) {
        ll t, c, d;
        t = P.top().fi, tie(c, d) = P.top().se, P.pop();
        chmin(DP[t][c], d);
        if (used[t][c]) continue;
        used[t][c] = 1;
        each(i, V[t]) {
            if (DP[i.fi][c + i.se.fi] > d + i.se.se && c + i.se.fi <= K)
                P.push({i.fi, {c + i.se.fi, d + i.se.se}});
        }
    }
    ll res = *min_element(DP[N - 1], DP[N - 1] + K + 1);
    cout << (res == INF ? -1 : res) << endl;
}