KIC 003 解説

総評

antaさん全完おめでとうございます！(47:54)
tanakhさん全完おめでとうございます！(102:34)
全完が2人しか居ないのは正直予想外でした。が、問題ごとの正解者数についてはおおむね予想通りです。

A問題 (FA:kyuridenamidaさん 02:08)

CDに、曲を長さが短い順に入れていけばOKです
入出力例2はwac「音楽」で3はラブライブ！のベストアルバムです

B問題 (FA:yuustiさん 06:03)

想定解法は、トレーニングする体力があるなら出来る限りトレーニングするGreedyです
O(NH)のDPでも間に合います。
本当はDPに行った人に時間を掛けさせるためにDPも通る制約にしたのに、antaさんがDPで爆速で通していて想定外です。
体力をHより多くまで回復させてる人が多かったですね。

C問題 (FA:kyuridenamidaさん 12:09)

長さ4以上のサイクルみたいなのがあれば逃げ切れる…？みたいなのを考えるとハマると思います。
盤面の状態数は、aの位置bの位置共にN通りなのでN^2です、なので実はN^2ターン逃げたら逃げ切った判定でOKです。
それを用いるとO(N^5)のDPで答えが求まります。
dp[aの位置][bの位置][ターン数]ですね

D問題 (FA:Mi_sawaさん 21:07)

ax=bなる素数xが存在したらaとbに辺を張るグラフを作ります。
それのグラフで考えると、最大独立集合を求めれば良い事に気づきます。
aとbは素因数の個数の偶奇が違うので、二部グラフになっています。
二部グラフの最大独立集合は最大マッチングから出せます。
なお、集合の中に1がある場合には注意してください。{1,2,4}の答えは2です({1,4})。

コード

C++11で、includeは省いています。

A

using namespace std;

typedef long long ll;
typedef pair<int, int> P;
typedef tuple<int, int, int> T;

int main() {
    int n;
    cin >> n;
    vector<int> v;
    for (int i = 0; i < n; i++) {
        int x, y;
        cin >> x >> y;
        v.push_back(x*60+y+3);
    }
    sort(v.begin(), v.end());
    int sum = 0;
    int i;
    for (i = 0; i < n; i++) {
        if (sum + v[i] > 80*60+3) break;
        sum += v[i];
    }
    cout << i << endl;
    return 0;
}

B

using namespace std;

typedef long long ll;
typedef pair<int, int> P;
typedef tuple<int, int, int> T;

int main() {
    ll N;
    cin >> N;
    ll H;
    cin >> H;
    ll A, X, B, Y;
    cin >> A >> X;
    cin >> B >> Y;
    ll k = 0, t = H;
    for (int i = 0; i < N; i++) {
        if (t >= X) {
            t -= X;
            k += A;
        } else {
            t = min(H, t+Y);
            k -= B;
        }
    }
    cout << k << endl;
    return 0;
}

C

using namespace std;

typedef long long ll;
typedef pair<int, int> P;
typedef tuple<int, int, int> T;
const int MN = 40;
bool dp1[MN][MN][MN*MN];
bool dp2[MN][MN][MN*MN];
bool used1[MN][MN][MN*MN];
bool used2[MN][MN][MN*MN];

int n;
vector<int> g[MN];
bool solve1(int x, int y, int t); //turn A
bool solve2(int x, int y, int t); //turn B

//A win:true
bool solve1(int x, int y, int t) {
    if (x == y) return false;
    if (t < 0) return true;
    if (used1[x][y][t]) return dp1[x][y][t];
    bool f = !solve2(x, y, t);
    for (int d: g[x]) {
        if (!solve2(d, y, t)) {
            f = true;
            break;
        }
    }
    used1[x][y][t] = true;
    dp1[x][y][t] = f;
    return f;
}

//B win:true
bool solve2(int x, int y, int t) {
    if (x == y) return true;
    if (t < 0) assert(false);
    if (used2[x][y][t]) return dp2[x][y][t];
    bool f = !solve1(x, y, t-1);
    for (int d: g[y]) {
        if (!solve1(x, d, t-1)) {
            f = true;
            break;
        }
    }
    used2[x][y][t] = true;
    dp2[x][y][t] = f;
    return f;
}

int main() {
    int m;
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    int x, y;
    cin >> x >> y;
    if (solve1(x, y, n*n+10)) {
        cout << "YES" << endl;
    } else {
        cout << "NO" << endl;
    }
    return 0;
}

using namespace std;

typedef long long ll;
typedef pair<int, int> P;
typedef tuple<int, int, int> T;

template<int V>
struct BitMatching {
    vector<int> G[2*V];
    int match[2*V];
    bool used[2*V];
    
    void add_edge(int a, int b) {
        G[a].push_back(b+V);
        G[b+V].push_back(a);
    }

    bool dfs(int v) {
        used[v] = true;
        for (int i = 0; i < G[v].size(); i++) {
            int u = G[v][i], w = match[u];
            if (w < 0 || (!used[w] && dfs(w))) {
                match[v] = u;
                match[u] = v;
                return true;
            }
        }
        return false;
    }

    int bit_matching() {
        int res = 0;
        fill_n(match, 2*V, -1);
        for (int v = 0; v < V; v++) {
            if (match[v] < 0) {
                fill_n(used, 2*V, false);
                if (dfs(v)) {
                    res++;
                }
            }
        }
        return res;
    }
};

//prims.size -> N=100k:near10k
template <int N>
struct Primes {
    bool used[N] = {};
    std::vector<int> primes;
    Primes() {
        for (int i = 2; i < N; i++) {
            if (!used[i]) {
                primes.push_back(i);
            }
            for (int j = i; j < N; j += i) {
                used[j] = true;
            }
        }
    }
};
const int MN = 3100;
BitMatching<MN> b;
Primes<MN> p;
int add[MN];
int c[MN];
bool used[MN];
int main() {
    for (int i = 1; i < MN; i++) {
        int j = i;
        for (int d: p.primes) {
            while (!(j%d)) {
                j /= d;
                c[i]++;
            }
        }
        c[i] %= 2;
    }
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        int d;
        cin >> d;
        assert(d);
        used[d] = true;
    }
    for (int i = 1; i < MN; i++) {
        if (!used[i]) continue;
        for (int d: p.primes) {
            int j = i*d;
            if (j >= MN) break;
            if (!used[j]) continue;
            int ii = i, jj = j;
            if (c[i]) swap(ii, jj);
            b.add_edge(ii, jj);
        }
    }
    cout << n-b.bit_matching() << endl;
    return 0;
}