AGC001 参加記

気づけば前ブログを書いてから4ヶ月経ち、もう学生ではなくなっていた..

6月末くらいから再び競プロに参加できるようになり、先日記念すべきAGC001に参加しました！

agc001.contest.atcoder.jp

遂にAtCoderも世界展開ということで、第一回に参加できて嬉しく思います。結果だけ見ると二完で悲しい感じですが(--;)

以下は復習できた問題にだけ触れます。

ちなみにeditorialはこちら

A - BBQ Easy

A: BBQ Easy - AtCoder Grand Contest 001 | AtCoder

基本的に「一番大きな串に肉をできるだけ多く刺したいなら、対となる串もできるだけ大きくする」という発想で解きました。まあソートして順番に出力していけばOK。

実装

N = int(raw_input())
L = map(int,raw_input().split())
L.sort(reverse = True)
ans = 0
for i in xrange(N):
    ans += min(L[2*i],L[2*i+1])
print ans

B - Mysterious Light

B: Mysterious Light - AtCoder Grand Contest 001 | AtCoder

一応解けたものの、時間使いすぎて結局二完に終わってしまいました。シミュレーションするのは無理だろうってことで $N=2,3,..,11$ ぐらいまで三角形描いて $O(1)$ 解を考えたのですが（なぜかあると思い込んでた）、結局時間を使っただけという..。

ただ、例を何個も描いて行く過程で光の軌跡の長さの変化がユークリッドの互除法っぽくなってることに気づいてそれで解けました。想定解法が美しすぎて感動しましたね。

実装

N,X = map(int,raw_input().split())
X = min(X,N-X)
ans = 0
N -= X
while X > 0:
    ans += N/X * X *3
    N,X= X,N%X
print ans

C - Shorten Diameter

C: Shorten Diameter - AtCoder Grand Contest 001 | AtCoder

コンテスト中最後に考えていて結局解けなかった問題。解説聞くとああーって感じです。これは解きたかったなあ。コンテスト中は木の直径をとりあえず求めて、直径の長さを持つパスの端を削ってまた直径計算して..まで考えて、いやうまくいかんやんどうしようって言ってたら終了しました。

直径が $K$ なら木の中心から各ノードへの距離が $K/2$ になるってのは言われてみれば確かにそうですね。勉強になりました。

実装については $K$ が偶数のときは各ノードが中心であると仮定して、中心からの距離が $K/2$ 以下となるノードの数を数えてます。 $K$ が奇数のときはエッジが張られてる一組のノードをペアとして、このエッジを無視して両ノードからの距離が $(K-1)/2$ 以下となるノードの数を数えました。

実装

from sys import setrecursionlimit
setrecursionlimit(100000)
def rad_reach(b,h,dist,E,rad):
    cnt = 1
    if dist < rad:
        for nxt in E[h]:
            if nxt == b:
                continue
            cnt += rad_reach(h,nxt,dist+1,E,rad) 
    return cnt
def solve():
    N,K = map(int,raw_input().split())
    pairs = []
    E = [[] for i in xrange(N)]
    for i in xrange(N-1):
        a,b = map(lambda x:int(x)-1,raw_input().split())
        E[a].append(b)
        E[b].append(a)
        pairs.append((a,b))
    ans = N
    rad = K/2
    if K % 2 == 0:
        for c in xrange(N):
            ans = min(ans,N-rad_reach(-1,c,0,E,rad))
    else:
        for c1,c2 in pairs:
            ans = min(ans,N-rad_reach(c2,c1,0,E,rad)-rad_reach(c1,c2,0,E,rad))
    print ans
solve()

再帰で書いたほうがすっきりするんですけど、pythonで出すとギリギリTLEしました（pypyなら通る）。ところがこれを繰り返しで書くとpythonでもギリギリ通りました。前もこんなことあった気がします。

D - Arrays and Palindrome

D: Arrays and Palindrome - AtCoder Grand Contest 001 | AtCoder

コンテスト中読んだもののそもそも問題の意味がわからなくて、解説放送見てやっと理解しました。なんか数列の問題かと思ったら一筆書きの話になっててびっくりした。

まだ完全に解説が理解できてないので解けたら復習記事書こうと思います。

E - BBQ Hard

E: BBQ Hard - AtCoder Grand Contest 001 | AtCoder

コンテスト中読んで意味はわかったけどどうしていいかわからず放置しました。問題文読んだ中で解説聞いて一番感動した問題です。なのでこの問題だけ詳しく書こうと思います。

ある二つの串焼きセット $i,j$ を選んだとき、串焼きの刺し方は同じものを含む順列を考えて

$\frac{(A_i+B_i+A_j+B_j)!}{(A_i+A_j)!(B_i+B_j)!}$ （通り）

になる（前準備しとけば $O(1)$ で求められる）ってのはいいんですが、問題はこれを全部の組やると ${}_NC_2$ 組だけ計算することになるということ。これだと計算量が $O(N^2)$ になるので余裕で死にます。それで諦めたのですが..

解法としては、 ${}_{n+m}C_m = \frac{(n+m)!}{n!m!}$ が座標平面上で $(0,0)$ から $(n,m)$ まで左と下に進まずに至る経路の数であることを利用してます。解説放送見たとき「天才か！」って思いましたね。

サンプルを例に取ると、串焼きセット $3:(2,1)$ と串焼きセット $1:(1,1)$ で作れる串焼きの種類は $(0,0)$ から $(2+1,1+1)$ へ至る経路の数になります。で、解説だと分かりやすいように、 $(-2,-1)$ から $(1,1)$ への経路数と言い換えてます。

この経路をdpを使って求める方法は計算量が $O(1)$ になりませんが、重要なのは複数の組での計算が同時に行えることです。串焼きセット3と1,串焼きセット2と1で作れる串焼きの種類を以下のように一回のdpで一気に求められます。同じものを含む順列が出てくると条件反射で $O(1)$ で求めようとしちゃうので、これは本当にビックリしました！

f:id:Tawara:20160720003248p:plain f:id:Tawara:20160720003712p:plain f:id:Tawara:20160720003745p:plain

で、実際の実装としては全部の組み合わせを計算するために、各串焼きセット $(A_i,B_i)$ について $(-A_i,-B_i)$ に 1 を加算し、dpで計算した後は各 $(A_i,B_i)$ で値を回収して和を取ります。サンプルだと $(1,1)$ が二つあるので、 $(-1,-1)$ には2が加算され、 $(1,1)$ で値を二回回収します。

f:id:Tawara:20160720011914p:plain

すると求める値は $22 \times 2 + 35 = 79$ となる..あれ？本来の解 $10 + 10 + 6 = 26$ と全然違います。理由は下の表に示したいらない部分(青字と黒字)の値も含まれているからです。

f:id:Tawara:20160720011349p:plain

なので、同じ串焼きセットで串焼きを作った場合の種類数を引いて $2$ で割れば、 $(79 - (15+6+6)) \div 2 = 26$ と答えが出せます。これで今度こそOKです。

余談

ところでいきなりなのですが、以下に示すpythonコードの一部を見てください。( $p = 10^9+7$ です)

print ((ans - dup) / 2 + p) % p

違和感を覚えたでしょうか？僕はこれのせいで解法を理解したにもかかわらずめちゃくちゃ時間を無駄にしました。

当たり前なんですけど、modとってるのに割り算しちゃダメですよね..本当に何で気付かなかったんだろう..階乗の逆元は前準備のためにしっかり求めてるのに2はそのまま割るという愚行を犯しました。今度から気を付けます。

実装

pypyでも誤差レベルでギリギリ間に合ったのですが（1998ms）、今のPCにC++導入したのでC++でも解いてみました。※include等は省略

#define range(i,a,b) for(int i=(a); i < (b); i++)
#define rep(i,n) range(i,0,n)
 
#define BASE 2000
#define MAX 4000
#define MOD 1000000007
 
LL F[MAX*2+1],Finv[MAX+1];
LL dp[MAX+2][MAX+2];
int A[200000],B[200000];
 
LL pow_mod(LL b,LL e){
    LL ret = 1;
    for (;e>0;e>>=1){
        if(e&1) ret = ret * b % MOD;
        b = b * b % MOD;
    }
    return ret;
}
int main(){
    int N,A_MAX=0,B_MAX=0;
    LL ans = 0,dup;
    F[0] = 1;
    rep(i,MAX*2) F[i+1] = F[i]*(i+1) % MOD;
    Finv[MAX] = pow_mod(F[MAX],MOD-2);
    rep(i,MAX) Finv[MAX-i-1] = Finv[MAX-i]*(MAX-i) % MOD;
    rep(i,MAX+1) rep(j,MAX+1) dp[i][j] = 0;
    scanf("%d",&N);
    rep(i,N){
        scanf("%d %d",A+i,B+i);
        A_MAX = max(A_MAX,A[i]);
        B_MAX = max(B_MAX,B[i]);
        dp[BASE-B[i]][BASE-A[i]] += 1;
    }
    range(i,BASE-B_MAX,BASE+B_MAX+1){
        range(j,BASE-A_MAX,BASE+A_MAX+1){
            dp[i+1][j] = (dp[i+1][j]+dp[i][j])%MOD;
            dp[i][j+1] = (dp[i][j+1]+dp[i][j])%MOD;
        }
    }
    rep(i,N){
        dup = F[A[i]*2+B[i]*2]*Finv[A[i]*2]%MOD*Finv[B[i]*2]%MOD;
        ans = (ans + dp[BASE+B[i]][BASE+A[i]] - dup + MOD) % MOD;
    }
    printf("%lld\n",ans*pow_mod(2,MOD-2)%MOD);
    return 0;
}