【AtCoder 初心者向け】ABC181の簡単な解説と振り返りについて【python】

2週間振りのABC．

練習問題も全く触ってなかったので，参加するか迷いましたが，結局参加することにしました(笑)

以下，問題の振り返りと簡単な解説です．

A問題：Heavy Rotation

初日に白服を着ている高橋くん．翌日は黒服，その次は白服を着ている(以下，繰り返し)．

N日後は白服(White)と黒服(Black)のどちらを着ているかという問題．

偶数日後ならWhite，奇数日後ならBlackなので，以下のコードでAC．

n=int(input())
if n%2==0:
	print("White")
else:
	print("Black")

B問題：Trapezoid Sum

黒板に書かれた$A_i 以上 B_i以内$の間の数字を全て足していくという問題．

ただ制約が

$1\leq N \leq 10^5$
$1\leq A_i \leq B_i \leq 10^5$

なので，単純にforループで$A_i ~ B_i$を足すとTLEになる．

ここで気がつくのは，足していくのは「初項$A_i$，末項$B_i$，公差1の等差数列」であるということ．つまり，等差数列の和の公式を使うと，全体で0(N)でACできる．

ただ今回は公差が1なので，等差数列の和の公式がなくても自力でできますが．．

#入力:[n1,n2,...nk](int:整数配列)
def input_array():
	return list(map(int,input().split()))

n=int(input())
AB=[input_array() for _ in range(n)]

ans=0
for ab in AB:
	st=ab[0]
	fi=ab[1]
	ans+=int((ab[1]-ab[0]+1)*(ab[0]+ab[1])/2)

print(ans)

C問題：Collinearity

2次元平面上にプロットされた点がN個あって，その中で同一直線上にあるものが存在するorしないかを判定する問題．

制約が$3 \leq N \leq 10^2$なので総探索(3重ループ)でも間に合う．

手順は以下のリンクを参考にするとわかりやすい．

3点が同一直線上の点か調べる - Qiita

調べ方3点の回転方向を調べるにて、$dx2 \times dy1 = dx1 \times dy2$ の場合は、3点は同一直線上の点であることがわかる。例$A=(2,3), B=(7,6), C=(12,9...

上の記事を参考にして，以下のコードでAC．

#入力:[n1,n2,...nk](int:整数配列)
def input_array():
	return list(map(int,input().split()))

n=int(input())
xy=[input_array() for _ in range(n)]
flag=False
xy=sorted(xy,key=lambda x: x[0])

for i in range(n):
	for j in range(i+1,n):
		for k in range(j+1,n):
			dx1=xy[j][0]-xy[i][0]
			dx2=xy[k][0]-xy[i][0]
			dy1=xy[j][1]-xy[i][1]
			dy2=xy[k][1]-xy[i][1]
			if dx1*dy2==dx2*dy1:
				print("Yes")
				exit()
print("No")

D問題：Hachi

数字列Sが与えられて，それを並び替えて8の倍数を作れるかという問題．

ある数字が8の倍数かどうかを判定する手法として，「下3桁が8の倍数なら，その数字は8の倍数である」という手法がある($ 8 \times 125 = 1000$なので)．

この条件を利用すると，

[Sが2桁以下]：数字Sと入替数字(例:Sが64なら46)を検証
[Sが3桁以上]：$100 ~ 999$区間の8の倍数を列挙し，Sに含まれる数字(1~9)で並び替えて作れるかどうかを検証

という流れになる．

特に[Sが3桁以上]の場合，Sに含まれる数字(1~9)のそれぞれの数を辞書で保持しておけば良い．

ということで，以下のコードでAC．

import copy

S=input()
s=list(S)
NUMS={i:0 for i in range(0,10)}
for i in s:
	NUMS[int(i)]+=1


if len(s)>2:
	tmax=3
else: #Sが2桁以下のとき
	if int(S)%8==0 or int(S[::-1])%8==0:
		print("Yes")
	else:
		print("No")
	exit()

# Sが3桁以上のとき
for n in range(112,1000,8):
	nums=copy.copy(NUMS)
	tmps=list(str(n))
	count=tmax
	if "0" not in tmps:
		for t in tmps:
			if nums[int(t)]>0:
				nums[int(t)]-=1
				count-=1
				if count==0:
					print("Yes")
					exit()
			else:
				break
print("No")

ちなみにPythonだと，辞書型配列を作成してくれる「Collections」というライブラリがあるので，それを使えばもう少し実装が楽になる．