math314のブログ

主に競技プログラミング,CTFの結果を載せます

天下一プログラマーコンテスト 2014 本戦

先週ですが,id math で出ていました,17位で残念.

公式ページ : http://tenka1.klab.jp/2014/

コンテストページ : http://tenka1-2014-final-open.contest.atcoder.jp/

六本木ヒルズの建物はそれ自体で迷路として完成しており楽しかった.

Tシャツを貰ったので先週から今週にかけて開催されていた ICPC夏合宿 に着て行きました.結果,さわり心地が良く寝間着するとよいのではと感じた.

人の写真だけどこんなの

来年も開催されたら賞金getしたい.

以下のコードは冗長なのでincludeを消している.

A問題

0だけ場合分けして,combinationを計算,そこそこ難しいと思ったけど全員解いてた.

using namespace std;
typedef long long ll;
typedef pair<int, int> Pii;
typedef pair<ll, ll> Pll;
 
#define FOR(i,n) for(int i = 0; i < (n); i++)
#define sz(c) ((int)(c).size())
#define ten(x) ((int)1e##x)
#define tenll(x) ((ll)1e##x)
 
const int MOD = 1000000007;
 
ll fact_t[10000];
//n! % MOD を構築する
void build_fact_table() {
    fact_t[0] = 1;
    for (int i = 1; i < sizeof(fact_t) / sizeof(ll); i++) {
        fact_t[i] = (fact_t[i - 1] * i) % MOD;
    }
}
 
// ax+by=gcd(a,b)となるx,yを求める(|x| <= b , |y| <= a)
template<class T> T extgcd(T a, T b, T& x, T& y) {
    for (T u = y = 1, v = x = 0; a;) {
        T q = b / a;
        swap(x -= q * u, u);
        swap(y -= q * v, v);
        swap(b -= q * a, a);
    }
    return b;
}
 
// ay≡gcd(a,m)(mod m) ---> return y;
template<class T> T md_inverse(T a, T m) {
    //mod_powの方が速い場合がある
    T x, y;
    extgcd(a, m, x, y);
    return (m + x % m) % m;
}
 
ll memo[2050][2050];
 
// nCk % MODを求める(build_fact_table後)
template<class T> T combi(T n, T k) {
    if (n < 0 || k < 0 || n < k) return 0;
    if (memo[n][k] != -1) return memo[n][k];
    T a1 = fact_t[n], a2 = fact_t[k], a3 = fact_t[n - k];
    return memo[n][k] = (a1 * md_inverse<ll>(a2 * a3 % MOD, MOD)) % MOD;
}
 
ll dp[65][2050];
 
int main() {
    build_fact_table();
    memset(memo, -1, sizeof(memo));
    int h, n, w; cin >> h >> n >> w;
    dp[0][w] = 1;
    FOR(i, h) {
        FOR(j, w + 1) {
            if (dp[i][j] == 0) continue;
            for (int use = 0; use <= n; use++) {
                int rem = j;
                if (i == 0) rem--;
                if (rem < use) break;
                ll c = combi<ll>(rem, use) * dp[i][j];
                if (i == 0) rem++;
                (dp[i + 1][rem - use] += c) %= MOD;
            }
        }
    }
 
    cout << dp[h][0] << endl;
}

B問題

bitsetで星座の情報を圧縮して持つ.190bitあれば十分持てたけど自分のコードだと200バイト使っている. お陰でlong long 3つじゃなくて4つ分の容量が必要になりTLEギリギリになった様子?

using namespace std;
typedef long long ll;
typedef pair<int, int> Pii;
typedef pair<ll, ll> Pll;
 
#define FOR(i,n) for(int i = 0; i < (n); i++)
#define sz(c) ((int)(c).size())
#define ten(x) ((int)1e##x)
#define tenll(x) ((ll)1e##x)
 
typedef bitset<200> BS; 
BS bs[ten(5)];
 
int main() {
    ios_base::sync_with_stdio(false);
    int n, m; cin >> n >> m;
    vector<Pii> xys(n);
    FOR(i, n)  cin >> xys[i].first >> xys[i].second;
 
    set<Pii> st;
    FOR(i, n) st.insert(xys[i]);
 
    FOR(i,n){
        const Pii& p = xys[i];
        for (int dy = -9; dy <= 9; dy++) {
            FOR(dx, 10) {
                int id = dx * 20 + (dy + 9);
                int cur_x = p.first + dx, cur_y = p.second + dy;
                Pii q(cur_x, cur_y);
                if (st.count(q) != 0) {
                    bs[i].set(id);
                }
            }
        }
    }
    
    FOR(i, m) {
        int s; cin >> s;
        vector<Pii> qs(s);
        FOR(j, s) cin >> qs[j].first >> qs[j].second;
        sort(qs.begin(), qs.end());
        BS qbs;
        for (int j = 0; j < sz(qs); j++) {
            int dx = qs[j].first - qs[0].first;
            int dy = qs[j].second - qs[0].second + 9;
            int id = dx * 20 + dy;
            qbs.set(id);
        }
        int ans = 0;
        //puts("qbs");
        //FOR(k, 200) if (qbs[k]) printf("%d\n", k);
 
        FOR(j, n) {
            //puts("bs[j]");
            //FOR(k, 200) if (bs[j][k]) printf("%d\n", k);
            if ((qbs & bs[j]) == qbs) {
                ans++;
//              printf("%d ok.",j);
            }
        }
        cout << ans << endl;
    }
}

C問題

文字列比較を90分バグらせて,残念でした. 部分点にかかわらず,バグりやすいbitDPをすると解ける.

D問題

部分点は本当にやるだけ 満点は平方分割

\( T(n,k) = \sum_{i = 0}^{k} C(n,i) \) と置くと, \( T(n+1,k+1) = T(n,k) + T(n,k+1) \) が成り立つことを利用する.

部分点しか投げてないので,ここには解法を載せてない.

E問題

部分点100は2次元のBITを使えば解けるのだが,C問題でハマりすぎてやる暇がなかった… 満点解法は,解説を聞いてもわからなかった,田端でバタバタ.