Treeone’s Blog

競技プログラミングの記録など

ICPC 国内予選 2017 参加記

初参加記。チームyellow_jamで ACM-ICPC 2017 国内予選 に参加しました。

結果

ABCDFを解いて5完で19位。無事、国内予選通過!

f:id:treeone:20170715182639p:plain

チーム紹介

チーム名:yellow_jam
弊学を卒業した偉大な先輩のハンドルネームから

メンバー:強い先輩、強い同期、@treeone79
(名前書いていいか分からないので一応)

当日まで

チーム全員が集まれたのは模擬国内と前日の2回。

同期氏が当日実験で1時間以上遅れそうということで、コンテスト序盤を2人でうまく立ち回る必要があった。

前日に立てた作戦では、僕はまずA問題をやって、その間に先輩がBとCを見て、Cの解法がすぐ思いついたら僕にBを残してくれることになった。

コーチのkonjo氏からは5完目標と言われてたけど、4完できたらいいねーという感じ。

当日

  • -1:30

4限がなかったので15時前には学内オンサイト会場に着いて、ひたすら過去のAB問題の早解きをやっていた。

  • 0:00

問題文を印刷して、僕がAに取りかかる。問題読んですぐに2重ループ回すだけじゃんってなったけど、緊張からか手間取ってしまう。
模擬国内で提出ミスをしたので慎重に提出する。

  • 0:09

A問題をAC。C問題が簡単そうということで、先輩がCをやって僕はBを読む。Bは面倒だけどやるだけっぽい。

  • 0:17

先輩がC問題をAC。Bのコーディングを始める。僕が実装で苦戦してる間に、想定していたよりも早く同期氏が到着して、先輩とDの考察を詰めていた。

  • 0:37

やっとB問題を通す。
先輩がDの実装をしている間に、同期氏と先の問題を読む。
H問題の幾何はINF時間あればできるという気持ちになったけど(それはそう)、国内予選は3時間しかないので切ることにした。

  • 0:52

D問題をAC。4完できてひとまず安心する。この時点で10位とかだったと思う。
EがヤバそうなのでFの考察をする。
同期氏と折り紙をして遊んでいたら、規則性を見つけたので同期氏に説明する。
今日何もコード書いてないじゃんと同期氏を煽って実装を投げる。
途中でバグっていたので全員でコードを読む。
座ってるだけをしている間にEとGを考えるけどよく分からない。

  • 2:40

F問題をAC。この間2時間くらい座っていた。残り20分だけど先輩がEの実装を始める。

  • 3:00

コンテスト終了。5完19位で大学内1位、予選通過できたっぽくて安心。

感想

今まで参加してきたチーム戦の中で一番うまく回っていて良かった。
これ読むと 自分は何も やってない (575) ので、アジア地区予選までには戦力になれるように精進したい。

ARC067 E Grouping

初投稿。それなりに頑張って解いたので自分用のメモとして書いた。

問題概要

1からNまでの番号がついた人がN人いる。以下の条件を満たすようなグループ分けは何通りあるかを求め、1000000007で割った余りを出力する。

  • 各グループの人数はA人以上B人以下
  • 任意のiについて、ちょうどi人が含まれるグループの数は0またはC以上D以下


制約
1 \leqq n \leqq 1000

解法

動的計画法(DP)を用いて解く。
i人未満からなるグループのみでj人をグループ分けした時の場合の数をdp[i][j]通りとする。
残りのn-j人の中から、i人グループをk個作る時( k=0 or C \leqq k \leqq D)、どのようにdp配列を更新すればよいだろうか。
まず、k=0の場合は簡単で、何もしないので dp[i+1][j]+=dp[i][j]である。
次に、C \leqq k \leqq D かつ i \times k \leqq n-jを満たしている場合、以下の式のようにdp配列が更新される。
dp[i+1][j+i\times k]+=dp[i][j]\times{}_{n-j}C_i \times _{n-j-i}C_i \times ... \times _{n-j-i\times (k-1)}C_i\times \frac{1}{k!}
ただし、全て1000000007で割った余りを取ることに注意する。
このDPの計算量は一見O(N^3)に思われるが、k0 \leqq k \leqq \frac{n-j}{i}の範囲しか取らないので、全体の計算量はO(N^2 log N)となる。*1

ソースコード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const ll mod = 1e9 + 7;
ll n, a, b, c, d;
ll dp[1010][1010];
ll fact[1010], fact_inv[1010], inv[1010];

long long mod_pow(long long x, long long n){
    if(n == 0) return 1;
    long long res = mod_pow(x * x % mod, n / 2);
    if(n & 1) res = res * x % mod;
    return res;
}

long long combination(long long n, long long k){
    return fact[n] * fact_inv[k] % mod * fact_inv[n - k] % mod;
}

int main(){
    cin >> n >> a >> b >> c >> d;
    
    memset(dp, 0, sizeof(dp));
    for(int i = 0; i < 1010; i++) dp[i][0] = 1;

    fact[0] = fact_inv[0] = 1;
    for(int i = 1; i < 1010; i++){
        inv[i] = mod_pow(i, mod - 2);
        fact[i] = fact[i - 1] * i % mod;
        fact_inv[i] = fact_inv[i - 1] * inv[i] % mod;
    }

    for(int i = a; i <= b; i++){
        for(int j = 0; j <= n; j++){
            if(dp[i][j] == 0) continue;
            if(j != 0) (dp[i + 1][j] += dp[i][j]) %= mod;
            ll p = 1;            
            for(int k = 1; k <= d; k++){
                if(j + i * k > n) break;
                p = p * combination(n - j - i * (k - 1), i) % mod * inv[k] % mod;
                if(c <= k && k <= d){
                    (dp[i + 1][j + i * k] += dp[i][j] * p % mod) %= mod;
                }
            }
        }
    }
    cout << dp[b + 1][n] << endl;
}

典型DPが解けるようになりたい

*1:\sum_{k=1}^{N} \frac{1}{k} \approx logNという近似を用いた