codeFlyer （bitFlyer Programmin...) C.徒歩圏内

Python Atcoder

問題文

N 個の都市があり、1,2,…,N の番号がついています。
これらの都市はこの順に一直線上に並んでいます。
各 i (1≤i≤N) について、都市 i の座標は Xi です。

高橋くんは都市 i と都市 j の間の移動手段を以下のように選びます。

  • 都市 i と都市 j の距離 |Xi−Xj| が D 以下であれば、徒歩で移動する。
  • そうでない場合、電車で移動する。

3 つの都市 (の番号) の組 (i,j,k) であって、以下の条件を満たすものの個数を求めてください。

  • i<j<k
  • 高橋くんは都市 i と都市 j の間、および都市 j と都市 k の間を徒歩で移動する。(Rule 1)
  • 高橋くんは都市 i と都市 k の間を電車で移動する。(Rule 2)

制約

  • 3≤N≤105
  • 0≤Xi≤109 (1≤i≤N)
  • Xi<Xi+1 (1≤i<N)
  • 0≤D≤109

考え方

for文を二重構造にしたらそれぞれの都市間を徒歩で移動するか電車で移動するかの情報を
配列で持てる...と思ったけど制限時間がアウト

3つの都市番号の組のうちjに着目して、
【jより左側にある距離D以内の都市の数】✖︎【jより右側にある距離D以内の都市の数】(=Sとする)を求め、 iに着目して、【iの右側にある距離D以内の2点の組み合わせの数】＝(Tとする)を求める。
すると、S-Tが答えになってくれる。

すなわちRule1を満たすものの個数を求めた後、Rule2を満たしていないものを引く。 二分探索で距離D以内の都市の配列番号を求めると良い。 ライブラリbisect...便利...

ソースコード

import bisect

N,D=map(int,input().split())
X=list(map(int,input().split()))

ans=0


#iは配列番号(=自分より左にある点の数)

for i in range(N-1):
 l=bisect.bisect_left(X,X[i]-D)     #lは自分より左にある点で距離D以内にない点の数と同義
 r=bisect.bisect_right(X,X[i]+D)     #rは下図参考
 ans+=(i-l)*(r-i-1)      #Rule1 左側の都市の数*右側の都市の数(rから自分と左側の都市の数を引く) 
 ans-=(r-i-1)*(r-i-2)//2  #Rule2 右側の都市の数から2個選ぶ組み合わせの数

print(ans)

具体例図

f:id:inaba00032:20180606033707j:plain

その他

X or Sum2 ~ABC 098 D~

Atcoder Python

※途中投稿です

問題文

長さ N の整数列A があります。

次の条件を満たす整数  l,  r (  1 ≤ l ≤ r ≤ N ) の組の個数を求めてください。

  • A[l] xor A[l+1] xor ... xor A[r] = A[l] + A[l+1] + ... + A[r]  

 

ソースコード(Python3)

N=int(input())
A=list(map(int,input().split()))
cur=A[0]
ans=0
rp=1

for lp in range(N):
　while rp<N and cur & A[rp]==0:
　　cur+=A[rp]
　　rp+=1
　ans+=rp-lp
　cur-=A[lp]

print(ans)

考え方

lp:lを見るポインタに相当

rp:rを見るポインタに相当

 

  • curに値（和）を蓄積していって、rに相当する所の論理積を取り0ならばrをずらす

二つの数の論理積が0

→和を取った時に繰り上げがない

→和とxorは等しくなる(和とxorの違いは双方に1があった時のみ)

 

 

  • 終わったらcurからlpの値を取り除く

この時、curにいくつかの値が蓄積していれば、

(ex.A[0]=100,A[1]=010,A[2]=001)

lpの値を抜き取っても、

残りの部分列は和とxorが等しい列になっている

(ex.A[1]+A[2]=011=A[1]xorA[2])

rpはそのまま次の判定に用いれる

 

振り返って

par.hateblo.jp