CS Academy Beta Round 7

https://csacademy.com/contest/beta-round-7/
なんかtopcoder部のカレンダーに載っていたので出てみました。
A: One Letter
https://csacademy.com/contest/archive/#task/one_letter/
各文字列をから一番小さいのをとってつなげてソートするだけです。

#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
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)
int main() {
    cin.tie(0); ios::sync_with_stdio(false);
    int N; cin >> N;
    string ans = "";
    rep(i, N) {
        string s; cin >> s;
        char p = '~';
        for(char c : s)
          p = min(p, c);
        ans += p;
    }
    sort(ans.begin(), ans.end());
    cout << ans << endl;
    return 0;
}

B: Subarray Removal
https://csacademy.com/contest/archive/#task/subarray_removal/
　これ解けませんでした。
　ある数列の部分列の和が最大となるようにN - 1以下の部分列を除去し、その最大値を求めろ、という問題。
　しゃくとり法の内側でしゃくとり法とかいういかにもバグりそうなことをしたら解けず。解説を見るとhttps://en.wikipedia.org/wiki/Maximum_subarray_problemという有名問題の応用で解けるらしいです。そんなの知らん、という感じですが……。

int main() {
    cin.tie(0); ios::sync_with_stdio(false);
    int N; cin >> N;
    vector<ll> a(N);
    ll mi = INF, ma = -INF, sum = 0LL;
    rep(i, N) {
        cin >> a[i];
        mi = min(mi, a[i]);
        ma = max(ma, a[i]);
        sum += a[i];
    }
    if(ma < 0) {
        cout << ma << endl;
        return 0;
    }else if(mi >= 0) {
        cout << sum - mi << endl;
        return 0;
    }
    vector<ll> st(N + 1, 0), ed(N + 1, 0);
    ll cur = 0LL;
    rep(i, N) {
        cur = max(0LL, cur + a[i]);
        st[i + 1] = max(st[i], cur);
    }
    cur = 0LL;
    for(int i = N - 1; i >= 0; --i) {
        cur = max(0LL, cur + a[i]);
        ed[i] = max(ed[i + 1], cur);
    }
    ll ans = -INF;
    rep(i, N + 1) ans = max(ans, st[i] + ed[i]);
    cout << ans << endl;
    return 0;
}

　簡便のためコードでは添字をずらしていますが、まずi以降でのMaximum subarray st[i]と、i以下でのMaximum subarray　ed[i]を別々に求めます。そしたら各iについて、合計st[i - 1] + ed[i + 1]のものが絶対に作れるので、…という感じですが普通に難しいと思います……。あとこれ、最大値がマイナスだとか最小値がプラスは先にはじくということをしているのでこれでも通るんですが、エディトリアルだと空のsubarrayを認めないタイプのMaximum subarrayを使うことが想定されているっぽい感じですかね。
C: Partial Ladder Graph
https://csacademy.com/contest/archive/#task/partial_ladder_graph/
　これも地味に難しい問題。
　はしご状の無向グラフから何本か弾いても連結になるようにしたい。何通りの構成方法があるか、という問題。
　a[i] := ノードi * 2個のはしごグラフで、すべて連結なものの数
b[i] := （同）２つの連結成分から構成されていて、ノードiとノードi*2が連結でないものの数
とすると、a[i + 1] = a[i] + 2 * b[i]
b[i + 1] = a[i] + 4 * b[i]
が成り立つので、あとは行列累乗。b[i]の設定ができるかがポイントかな？

typedef vector<ll> vec; typedef vector<vec> mat;
const int MOD = 1000000007;
//A * B
mat mul(const mat& A, const mat& B) {
    mat C(A.size(), vec(B.size()));
    rep(i, A.size()) rep(k, B.size()) rep(j, B[0].size())
      C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % MOD;
    return C;
}
//A ^ n
mat pow(mat A, ll n) {
    mat B(A.size(), vec(A.size()));
    rep(i, A.size()) B[i][i] = 1;
    while(n > 0) {
        if(n & 1) B = mul(B, A);
        A = mul(A, A);
        n >>= 1LL;
    }
    return B;
}

int main() {
    cin.tie(0); ios::sync_with_stdio(false);
    ll N; cin >> N;
    mat A = {{1, 2}, {1, 4}};
    A = pow(A, N);
    cout << A[1][0] << endl;
    return 0;
}

　残りの問題は見てないのでここまで。CS Academyサイトも金かかってる感じで使いやすいし問題も面白いですね。web arenaとは何だったのか……。