ABC168

はじめに

この記事では、AtCoder Beginer Contest 168のA~E問題を解説します。

A - ∴ (Therefore)

https://atcoder.jp/contests/abc168/tasks/abc168_a

inを使うと簡単です。

1
2
3
4
5
6
7
8
N = int(input())
N%=10
if N==3:
print('bon')
elif N in (0,1,6,8):
print('pon')
else:
print('hon')

B - … (Triple Dots)

https://atcoder.jp/contests/abc168/tasks/abc168_b

スライスを利用します。

1
2
3
4
5
6
K = int(input())
S = input()
if len(S)<=K:
print(S)
else:
print(S[:K]+'...')

C - : (Colon)

https://atcoder.jp/contests/abc168/tasks/abc168_c

長針と短針の長さが決まっているので、長針と短針のなす角度を求めることで余弦定理により解を求めることができます。
短針はだけでなくによっても動くので注意します。
また、角度は180度以下になるように変換します。

1
2
3
4
5
6
7
8
9
import math
A,B,H,M = map(int,input().split())
H = (H+M/60)*30 # 360度/12時間 = 30度、長針は短針より60倍遅い
M *= 6 # 360度/60分 = 6度
d = abs(H-M) # 長針と短針のなす角度
if d > 180: # 角度は180度以下
d = 360 - d
C = pow(A**2+B**2-2*A*B*math.cos(math.radians(d)),0.5)
print(C)

D - .. (Double Dots)

https://atcoder.jp/contests/abc168/tasks/abc168_d

幅優先探索によって求めることができます。訪問した際に、前の部屋(親)を記録します。この記録を用いて訪問済みかどうかも判定します。

Pythonで幅優先探索を実装する際は、標準ライブラリのqueueを用いると良いです。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import queue
N,M = map(int,input().split())
adj = [[]for i in range(N+1)]
parent = [-1] * (N+1) # -1なら未訪問
for m in range(M):
a,b = map(int,input().split())
adj[a].append(b)
adj[b].append(a)
q = queue.Queue() # 自分の部屋番号、親の部屋番号
q.put((1,0)) # 部屋1の親は部屋0と考える
while(not q.empty()):
x, p = q.get()
if parent[x] != -1: # 訪問済み
continue
parent[x] = p
for next in adj[x]:
if parent[next] == -1: # 未訪問なら
q.put((next,x)) # 探索候補に追加
print ('Yes') # 必ず目標は達成できる
for p in parent[2:]: # 部屋2以降の親(前の部屋)
print(p)

E - ∙ (Bullet)

https://atcoder.jp/contests/abc168/tasks/abc168_e

ポイント

  • aとbの比の情報を考える
    • 約分をしたのちに文字列として格納する
      • 符号がaとbで同じ場合と異なる場合で、別の辞書に格納する
  • どちらか片方のみが0の場合
    • (0,非0)(非0,0)は共存NGで、これらは特別な文字列(例えば0/0)として、別々の辞書に格納すれば問題ない。
  • 両方が0の場合
    • 単独で選ぶパターンのみが有効である。すなわち単純に数え上げて答えに足せば良い。その後イワシは除外する。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
import math
MOD = 1000000007
N = int(input())

even = dict() # (+,+), (-,-)
odd = dict() # (+,-), (-,+)
ans = 1
zz = 0 # (0,0)の場合は、その数だけ答えをインクリメントすれば良い

for n in range(N):
a,b = map(int,input().split())

if a==0 and b==0:
zz += 1 # かぞえあげる
continue # 考察対象から除外
if a==0:
n_sign = 0
b = 0 # こうしておくと後ほど'0/0'として格納される
elif b==0:
n_sign = 1
a = 0 # こうしておくと後ほど'0/0'として格納される

else:
n_sign = ((a<0) + (b<0)) % 2 # -の出現回数が偶数か奇数か
a = abs(a) # 符号は用済み
b = abs(b) # 符号は用済み
gcd = math.gcd(a,b) # 約分のためにGCDを計算
a//=gcd # 約分
b//=gcd # 約分

if n_sign==1:
s =str(b)+'/'+str(a) # '41/3'のように文字列として扱う
odd[s] = odd.get(s,0) + 1 # かぞえあげる
elif n_sign==0:
s =str(a)+'/'+str(b) # 逆数を考えることで単純な文字列比較に持ち込む
even[s] = even.get(s,0) + 1

for k,v in odd.items():
if k in even: # 共存NGあり
ans *= (2**v + 2**even[k] - 1)
even.pop(k) # 辞書から削除
else: # 共存NGなし
ans *= 2**v
ans %= MOD

for k,v in even.items():
ans *= 2**v # 削除していない分を数える
ans %= MOD

ans -= 1 # 1匹も選択しないのはNG
ans += zz
ans %= MOD
print (ans)

関連記事

過去のABC解説記事です。

  • ABC167
    • A-E問題を解いています。
  • ABC166
    • A-F問題を解いています。
  • ABC165
    • A-F問題を解いています。
  • ABC164
    • A-E問題を解いています。
  • ABC163
    • A-D問題を解いています。
  • ABC162
    • A-E問題を解いています。

記事情報

  • 投稿日:2020年5月18日
  • 最終更新日:2020年5月18日