Testing Round #12

はい。
http://codeforces.com/contest/597

A. Divisibility

ざっくりと大意

・a,b(自身の数を含む)間にkで割り切れる数が何個あるか。

方針のようなもの

・計算する。

python

k,a,b=map(int,raw_input().split())
ans=chk=0
if abs(a)%k==0:
    pass
else:
    if a<0:
        a+=abs(a)%k
    else:
        a+=k-abs(a)%k
print (b-a)/k+1

入力の制限とか確認せずに適当に書いたがなんとかなってしまった。aがkで割り切れるかをみて、割り切れない場合はa以上のkで割り切れる数にしているが、その数がbを超えないことを気にしていなかった。

B. Restaurant

ざっくりと大意

・レストランでn件の注文があり、それぞれが\(l_i\)に開始で\(r_i\)に終了の対応予定となる？？
・時間が重複するものはどちらかしか出来ない(7終了で、7開始はどちらかしか出来ない)。

方針のようなもの

・方針まとまらないので他の人のをみよう。

python

n=int(raw_input())
#l=[]
l=[0]*n
for i in range(n):
    #l.append(map(int,raw_input().split()))
    a,b=raw_input().split()
    l[i]=(int(a),int(b))
l.sort(key=lambda x: x[1])
ans=chk=0
for x,y in l:
    if chk<x:
        ans+=1
        chk=y
print ans

入力データを終了時間を優先でソートする。lambdaを使わずに開始時間と終了時間を入れ替えて通常のソートでも可。初回は注文の対応終了時間を0扱いとして、現在の対応終了時間に最も近い開始で最も早く終了するものを選択し続けることで最も多くの注文に対応することが出来る。

C. Subsequences

ざっくりと大意

・後で、Pythonで通してる人がいないっぽい。

方針のようなもの

・後で。

python

# TLEになる
n,k=map(int,raw_input().split())
#l=map(int,raw_input().split())
l=[]
N=range(n)
for i in N:
    l.append(int(raw_input()))
ans=chk=0
dp=[[1]*n]
for i in range(1,k+1):
    dp.append([0]*n)
    for j in range(1,n):
        for p in range(j):
            if l[p]<l[j]:
                dp[i][j]+=dp[i-1][p]
for i in N:
    ans+=dp[k][i]
print ans

TLEになるので後で