University Codesprint 5

AからFの6完で144位でした。

AからBの難易度の跳ね方がすごすぎて焦りました。 D問題は既出のようですね。

SPOJ.com - Problem SUBXOR

B - Array Triplets

全探索をうまくやります。最初これでTLEすると思っていて別解法を模索してたのですが、１時間経っても思いつかず、 部分点狙いで全探索書いたら通りました、、、

ちなみに最大の答えは、入力がすべて0のときで128746950通りあります。これ通るんだ、、、

それぞれの部分集合の部分和を予め全列挙しておき、１つ目の部分集合を全探索します。 部分和がsum/3になるものが見つかったら、その部分集合の補集合の部分集合で、和がsum/3になるものを全探索します。

この際、ビットによる部分集合の列挙 - SRM diary(Sigmar) - TopCoder部で解説されているように

for (int i = subset; i >= 0; i = (i - 1) & subset) {
  // subsetの部分集合iを列挙
}

で、効率よく部分集合を列挙できます。

i64 sub_sum[1 << 17];
i64 as[17];
i64 sum = 0;

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> as[i];
        sum += as[i];
    }
    
    for (int i = 0; i < (1 << n); i++) {
        for (int j = 0; j < n; j++) {
            if ((i >> j) & 1) {
                sub_sum[i] += as[j];
            }
        }
    }
    
    if (sum % 3) {
        cout << 0 << endl;
        return 0;
    }
    
    i64 ans = 0;
    for (int i = 1; i < (1 << n); i++) {
        for (int j = i ^ ((1 << 17) - 1); j > 0; j = (j - 1) & (i ^ ((1 << 17) - 1)))  {
            if ((i | j) == (1 << 17) - 1) continue;
            if ((i & j) == 0 && sub_sum[i] == sum / 3 && sub_sum[j] == sum / 3) {
                ans++;
            }
        }
    }
    cout << ans << endl;
}

C - a,b Special Points

テクニックを知らなくても解ける問題なのでBよりも簡単だと思います。

連結成分内はもちろん行き来することができるので、uとして連結成分内で次数最小の頂点、u'として連結成分内で次数最大の頂点をとって、連結成分内で全探索すればいいです。

D - Limit XOR

調べたら既出でした。ちゃんと理解したら解説を書こうと思います。

E - Cube-loving Numbers

素数の3乗の個数だけカウントすればいいのでは？

→(2 * 3)の3乗とか重複して数えてしまうなー

→(2 * 3)の3乗はカウントから引いて、(2 * 3 * 5)の3乗とかは足せばよさそう

→各素数をたかだか1回まで使った積で表される数を列挙し、奇数回使ったものはカウントに足して、偶数回使ったものを引くと良さそう（包除原理！）

以下のコードでは最初にエラトステネスの篩を実装しており、その後似たようなアルゴリズムで、各整数が"各素数をたかだか1回まで使った積で表される数"かどうかを判定し、そうだった場合は何種類の素数の積か、そうではない場合は-1をcntという配列に記録しています。

これもかなりTLEすれすれだと思うのですが、投げたら通りました、、、

int p[1000001];
int cnt[1000001];

int main() {
    for (i64 i = 2; i < 1000001; i++) {
        p[i] = 1;
    }
    for (i64 i = 2; i < 1000001; i++) {
        if (p[i] == 0) continue;
        for (int j = 2; i * j < 1000001; j++) {
            p[i * j] = 0;
        }
    }
    for (i64 i = 2; i < 1000001; i++) {
        if (p[i]) {
            for (i64 j = 1; i * j < 1000001; j++) {
                if (cnt[i * j] != -1) {
                    cnt[i * j]++;
                }
            }
            cnt[i] = 1;
            for (i64 j = 1; i * i * j < 1000001; j++) {
                cnt[i * i * j] = -1;
            }
        }
    }
    int t;
    cin >> t;
    for (int i = 0; i < t; i++) {
        i64 n, ans = 0;
        cin >> n;
        
        for (i64 a = 2; a * a * a <= n; a++) {
            if (cnt[a] == -1) continue;
            if (cnt[a] % 2) {
                ans += n / (a * a * a);
            } else {
                ans -= n / (a * a * a);
            }
        }
        cout << ans << endl;
    }
}

F - Interesting Trip

各頂点に英小文字1文字のラベルが付いた非巡回な有向グラフが与えられる。スタートからゴールへ向かうパスに対して、通過した頂点のラベルを順につないでできる文字列のうち辞書順最小のものは何か、という問題。

スタートから各頂点に対して辞書順最小の文字列を記録するのは空間的に不可能なので、スタートから貪欲にできるだけ小さいラベルを辿ってゴールまで行くことを考えます。

グラフが非巡回であることからスタートからゴールに到達できる場合、解の存在が保証されます。答えとなる文字列の長さはたかだか頂点数ですが、幅優先時にqueueに入る頂点の数は、同じ頂点が複数回入ることもありえるので非常に大きくなってしまいます。

しかし、ある頂点がqueueに入っているとき、その頂点から次に進みうる頂点というのは「ゴールに到達可能なもののうち、ラベルが最小のもの」であり、これを事前計算することによってかなりの高速化ができます。

めちゃくちゃ試行錯誤した結果、以下のコードでACしました。

char name[202020];
vi adj[202020];
vi invadj[202020];
int can_finish[202020];
char min_reachable_name[202020];
vi min_reachable_adj[202020];

void dfs(int v) {
    if (can_finish[v]) return;
    can_finish[v] = 1;
    for (int i: invadj[v]) {
        dfs(i);
    }
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(0);
    
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        cin >> name[i];
    }
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        a--;
        b--;
        adj[a].push_back(b);
    }
    
    for (int i = 0; i < n; i++) {
        sort(adj[i].begin(), adj[i].end());
        adj[i].erase(unique(adj[i].begin(), adj[i].end()), adj[i].end());
    }
    
    for (int i = 0; i < n; i++) {
        for (int a: adj[i]) {
            invadj[a].push_back(i);
        }
    }
    
    int s, f;
    cin >> s >> f;
    s--;
    f--;
    
    dfs(f);
    
    if (!can_finish[s]) {
        cout << "No way" << endl;
        return 0;
    }
    
    for (int i = 0; i < n; i++) {
        min_reachable_name[i] = '{';
        for (int a: adj[i]) {
            if (can_finish[a]) {
                min_reachable_name[i] = min(min_reachable_name[i], name[a]);
            }
        }
        for (int a: adj[i]) {
            if (can_finish[a] && name[a] == min_reachable_name[i]) {
                min_reachable_adj[i].push_back(a);
            }
        }
    }
    
    string ans = "";
    ans.reserve(202020);
    set<int> q1;
    q1.insert(s);
    ans += name[s];
    while (1) {
        char nxtch = '{';
        for (auto t: q1) {
            nxtch = min(nxtch, min_reachable_name[t]);
        }
        assert(nxtch != '{');
        ans += nxtch;
        set<int> q2;
        for (auto t: q1) {
            if (min_reachable_name[t] == nxtch) {
                for (int a: min_reachable_adj[t]) {
                    q2.insert(a);
                    if (a == f) {
                        cout << ans << endl;
                        return 0;
                    }
                }
            }
        }
        swap(q1, q2);
    }
}