9度目のSRM。問題セットがいつもより簡単だったおかげか、はじめてHardまで解けた。でももう少し落ち着いてたらさらに点数が伸びたのに。それは次回頑張ろう。
1174.08で部屋2位、全体74位。1096→1165 (+69)。レーティングは自己ベストを更新。Div1が見えてきた。
追記：Hardの得点は1000から900に変更されてた。

問題はこちら。

Easy 250

同じ要素数の2つの数列Q、Pが与えられる。すべての要素は正の整数でT以下である。それぞれについて、数列のはじめから要素を足し合わせていき、Tを越えたらTを引くという操作をしていく。QとPで、Tを引く操作が同じ要素番号において行われる回数は合計いくらかを答える。

すべての要素はT以下という条件を見過ごしていたので while文を書いているが、引くのは1回だけで大丈夫である。

def meet(self, T, Q, P):
    quimey,pablo,ans = 0,0,0
    for i,j in zip(Q,P):
        quimey += i
        pablo += j
        if quimey >= T and pablo >= T: ans += 1
        while quimey >= T: quimey -= T
        while  pablo >= T: pablo -= T
    return ans

Medium 500

N 個のxy平面座標値が与えられるので、そこから3点選んで三角形を作るとき、原点 (0,0) を内包する三角形はいくつあるか、という問題。ただし、どの3点も直線に並ぶことはなく、どの三角形の辺上や頂点に (0,0) は存在しない。

N が最大50なので組み合わせで全三角形を調べればいい。ある点Dが三角形ABCに内包されているかどうかは、点Dと三角形の頂点A,B,Cとを結んでできる3つの三角形の面積がもとの三角形の面積と同じかどうかで判断できる。

def count(self, x, y):
    ans = 0
    xy = zip(x,y)
    S = lambda x1,y1,x2,y2,x3=0,y3=0: abs(x1*(y2-y3)+x2*(y3-y1)+x3*(y1-y2))/2.0
    for xy1,xy2,xy3 in itertools.combinations(xy,3):
        x1,y1 = xy1
        x2,y2 = xy2
        x3,y3 = xy3
        if not S(x1,y1,x2,y2)+S(x2,y2,x3,y3)+S(x3,y3,x1,y1)-S(x1,y1,x2,y2,x3,y3) > 0.0000001:
            ans += 1
    return ans

Hard 1000 900

2*N枚のカードからなるデッキに対して、1回のシャッフルを次のように定義する。

デックを上 N 枚のAと下 N 枚のBに分ける。
A中のカードを好きな順番に並び替える。B中のカードも同様。
AとBを合わせて1つのデッキに戻す。デックA、Bのカードを上から A[1],A[2],...,A[N]、B[1],B[2],...,B[N] としたとき、デックを1つに戻すとき A[1],B[1],...,A[N],B[N] になるようにする。

今、1から2Nまでのカードがある順番で並んだデックが与えられる。はじめ、1から2Nまで順番に並んだデックがあったとして、2回のシャッフルで与えられたデックの並びにできるかどうかを答える。

1度目の並び替え後の2つのデックをA,B、２度目の並び替え後の2つのデックをA',B'とする。まず、最後のデックを合わせる作業をたどることで、与えられたデックをA',B'に戻すことができる。シャッフルの性質上、A',B'にはそれぞれAとBのカードが約半分ずつ（Nの偶奇により変わる）含まれていることがわかる。AにはN以下の数、BにはNより大きい数が含まれていることから、A'に含まれるN以下の数の個数aとNより大きい数の個数bは、N偶数ならa==b、N奇数ならa-1==bでないといけない。同様にBの場合ではN偶数ならa==b、N奇数ならa==b-1でないといけない。これらの条件を満たすなら"Possible"、満たさないなら"Impossible"を出力すればいい。

def shuffle(self, permutation):
    N = len(permutation)/2
    permutation = permutation[::2] + permutation[1::2]
    ans = "Possible"
    
    a = b = 0
    for i in permutation[:N]:
        if i <= N: a += 1
        else     : b += 1
    if N%2 == 0:
        if a != b  : ans = "Impossible"
    else:
        if a-1 != b: ans = "Impossible"
        
    a = b = 0
    for i in permutation[N:]:
        if i <= N: a += 1
        else     : b += 1
    if N%2 == 0:
        if a != b  : ans = "Impossible"
    else:
        if a != b-1: ans = "Impossible"
        
    return ans

roiti46's blog

主に競プロ問題の解説を載せてます

TopCoder SRM 641 Div2

Easy 250

Medium 500

Hard 1000 900