Atcoder Beginner Contest 168(ABC168) A〜E解説

たのん

AtCoder Beginner Contest 168(ABC168)のA～Eまでの解説です。
コンテスト中はA～Dまでを解き(45:40+5WA)、Eが難しい回だったこともありABCでは1年ぶりの緑パフォを出してしまいました…。
問題のアドレスは以下になります↓
https://atcoder.jp/contests/abc168/
公式の解説(Editorial)は以下になります↓
https://img.atcoder.jp/abc168/editorial.pdf

A問題:

問題文の通りに、Nの下一桁に対応する答えを出力すればよいです。
具体的な実装としては、配列や連想配列を用いて直接答えを求めたり、Nの下一桁が{2,4,5,7,9},{0,1,6,8},{3}のどれに含まれるかで場合分けしたり、あるいは愚直に場合分けの条件を書いたりすることで解くことができます。

B問題:

問題文の通り、Sの長さがK以下であるかで場合分けし、K以下であればそのまま出力、Kより大きければSをK文字目まで見たものを出力すればよいです。
Pythonであればスライスを用いることで簡単に解くことができます。

C問題:

いかにも高校数学な問題です。
2辺a,bの長さとその間の角∠abが分かっていることから、三平方の定理の拡張である余弦定理を用いることで、c^2=a^2+b^2-2ab*cos(∠ab)としてすぐに答えを求めることができます。
あるいは、各辺の頂点の(x,y)座標を(各象限で場合分けして)求め、三平方の定理を用いて答えを求めてもよいです。

サンプルコード(Python)((x,y)座標を求める方法):
https://atcoder.jp/contests/abc168/submissions/13309307

import math

a,b,h,m=map(int,input().split())
deg1=h*30+m*0.5
x1,y1=0,0
if deg1<=90: #各象限で場合分けして、三角関数を用いて(x,y)座標をそれぞれ求める
 x1=a*math.sin(2*math.pi*(deg1/360))
 y1=a*math.cos(2*math.pi*(deg1/360))
elif deg1<=180:
 x1=a*math.sin(2*math.pi*((180-deg1)/360))
 y1=-a*math.cos(2*math.pi*((180-deg1)/360))
elif deg1<=270:
 x1=-a*math.sin(2*math.pi*((deg1-180)/360))
 y1=-a*math.cos(2*math.pi*((deg1-180)/360))
elif deg1<=360:
 x1=-a*math.sin(2*math.pi*((360-deg1)/360))
 y1=a*math.cos(2*math.pi*((360-deg1)/360))
deg2=m*6
x2,y2=0,0
if deg2<=90: #各象限で場合分けして、三角関数を用いて(x,y)座標をそれぞれ求める
 x2=b*math.sin(2*math.pi*(deg2/360))
 y2=b*math.cos(2*math.pi*(deg2/360))
elif deg2<=180:
 x2=b*math.sin(2*math.pi*((180-deg2)/360))
 y2=-b*math.cos(2*math.pi*((180-deg2)/360))
elif deg2<=270:
 x2=-b*math.sin(2*math.pi*((deg2-180)/360))
 y2=-b*math.cos(2*math.pi*((deg2-180)/360))
elif deg2<=360:
 x2=-b*math.sin(2*math.pi*((360-deg2)/360))
 y2=b*math.cos(2*math.pi*((360-deg2)/360))
ans=math.sqrt((x1-x2)**2+(y1-y2)**2) #三平方の定理で答えを求める
print(ans)

サンプルコード(Python)(余弦定理を用いる方法):
https://atcoder.jp/contests/abc168/submissions/13590871

import math

a,b,h,m=map(int,input().split())
deg=abs(h*30+m*0.5)-(m*6)
if deg>=180:
 deg=360-deg
c=math.sqrt(a**2+b**2-2*a*b*math.cos(math.pi*deg/180))
print(c)

D問題:

どの2部屋間もいくつかの通路を通って移動できることが保証されていることから、目標を達成する道しるべの置き方は必ず存在することが示せます。
具体的には、部屋1から移動できるすべての部屋に、1に移動するよう道しるべを置き、移動したすべての部屋から次に移動できるすべての部屋に、道しるべが置かれていなければ元いた部屋に移動するよう道しるべを置き…という操作をすべての部屋に道しるべが置かれるまで繰り返せばよいです。
これはBFSを用いることで簡単に実装することができ、この問題をO(N+M)で解くことができました。

サンプルコード(Python):
https://atcoder.jp/contests/abc168/submissions/13351533

import collections

n,m=map(int,input().split())
g=[[] for _ in range(n+1)]
for _ in range(m):
 a,b=map(int,input().split())
 g[a].append(b)
 g[b].append(a)
q=collections.deque()
q.append(1)
check=[0]*(n+1)
check[1]=1
ans=[0]*(n+1)
while len(q)!=0:
 v=q.popleft()
 for u in g[v]:
   if check[u]==0: #まだ探索していない頂点について、その頂点に親の頂点に移動する道しるべを置く
     check[u]=1
     ans[u]=v
     q.append(u)
print('Yes')
for i in range(2,n+1):
 print(ans[i])

E問題:

i番目の要素とj番目の要素を同時に選べないのは、Ai*Aj+Bi*Bj=0のとき、すなわち、Aj!=0,Bi!=0を仮定すると、Ai/Bi=-Bj/Aiのとき、i番目の要素とj番目の要素のいずれかしか選ぶことができません。
したがって、Ai/Biと-Bj/Ajをペアとして考えると、このようなペアは高々N個しかなく、ペアの個数を具体的に求められることが分かります。
ペアの個数が分かっているとき、そのペアからいくつかの要素を選ぶ場合の数は、2^(A/Bの個数)+2^(-B/Aの個数)-1で求められることが分かります(∵どちらか一方のペアから、0個～(A/Bの個数)個選ぶことができ、この場合の数は2項定理より2^(A/Bの個数)であると分かります、ただし、このままでは一方のペアから0個の要素を選ぶ場合、すなわち空集合を選ぶ場合が2回出てくるので、-1して個数を補正します)。
以上より、ペアの個数を求めることができれば、この問題をO(N)で解けることが分かりました。
さて、各ペアでの場合の数を求めるためには、A/Bの値が等しいものの個数を上手く数える必要があります。
制約よりA,Bが十分大きいので、単にA/Bの値をキーにして連想配列を作ると誤差が生じ上手くいきません。
ここで、AとBのgcdを求めてA/Bを既約分数として表し、(A,B)という組をキーとすることを考えると、誤差が生じることなく、上手く個数を数えられることが分かります。
ただし、AまたはBが0のときgcdを求めることができないため、この場合は別に考えることにします。
AとBがともに0のとき、そのような要素を選ぶと、ほかの全ての要素を選ぶことができなくなります(∵他の要素のA,Bの値によらず条件式を満たします)。
したがって、このような要素の個数を別途数えておき、このような要素を1つも選ばない場合の数に、このような要素の個数を足し合わせればよいです。
AかBのどちらか一方が0のとき、(1,0)または(0,1)をキーとすることで、AもBも0でないときのキーと重複しないようにキーを設定することができます。
以上によりA/Bの値が等しいものの個数をO(Nlog(max(A,B)))で求めることができるようになったので、この問題をO(Nlog(max(A,B))で解くことができました。

サンプルコード(Python):
https://atcoder.jp/contests/abc168/submissions/13591835

import collections

def gcd(a,b):
 if b==0:
   return a
 else:
   return gcd(b,a%b)

mod=10**9+7
n=int(input())
dic=collections.defaultdict(int)
cnt=0
for _ in range(n):
 a,b=map(int,input().split())
 if a!=0 and b!=0: #aもbも0でないとき、gcdを求めてa/bを規約分数として表す
   g=gcd(abs(a),abs(b))
   if a*b>0: #a*bが正(=a/bが正)であればa/b((a,b)で表す)をdicに追加する
     dic[(abs(a)//g,abs(b)//g)]+=1
   else: #a*bが負(=a/bが負)であれば-a/b((-a,b)で表す)をdicに追加する
     dic[(-abs(a)//g,abs(b)//g)]+=1
 else: #aまたはbが0であるとき
   if a==0 and b==0: #両方とも0であれば、そのような要素を選ぶと他の要素が選べなくなるので別途個数を数える
     cnt+=1
   elif a==0: #aが0であれば、0/1((0,1)で表す)をdicに追加する
     dic[(0,1)]+=1
   elif b==0: #bが0であれば、1/0((1,0)で表す)をdicに追加する
     dic[(1,0)]+=1
ans=1
s=set()
for a,b in dic.keys(): #各(a,b)の組を見る
 if (a,b) in s:
   continue
 s.add((a,b))
 if a>0: #aが正のとき、a/bも正なので-b/aが存在するかを確かめる
   s.add((-b,a))
   cnt1=dic[(a,b)]
   if (-b,a) in dic: #-b/aが存在すればその個数を求める
     cnt2=dic[(-b,a)]
   else: #存在しなければ個数は0とする
     cnt2=0
   ans*=(pow(2,cnt1,mod)+pow(2,cnt2,mod)-1)%mod #a/bと-b/aのペアで取れる場合の数は、(a/bの要素のべき集合の個数)+(-b/aの要素のべき集合の個数)-1である(空集合を除くために-1する)
   ans%=mod
 else: #aが負のとき、a/bも負なのでb/(-a)が存在するかを確かめる
   s.add((b,-a))
   cnt1=dic[(a,b)]
   if (b,-a) in dic:
     cnt2=dic[(b,-a)]
   else:
     cnt2=0
   ans*=(pow(2,cnt1,mod)+pow(2,cnt2,mod)-1)%mod
   ans%=mod
print((ans+cnt-1)%mod) #答えは(各ペアを条件を満たして取る場合の数-1)+((0,0)のペアの個数)に等しい

この記事が気に入ったらサポートをしてみませんか？