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

AtCoder
この記事は約5分で読めます。

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」というライブラリがあるので,それを使えばもう少し実装が楽になる.

感想(懺悔コーナー)

なんか今回のABCは「ググり力」が試された問題が多い.特にB問題とC問題.

あと,自分の記事はあくまで「振り返り」を目的としているので,解説記事としては不向きかもしれません.

そのへんはご容赦を...

おーよしの紹介
院卒Webエンジニアマン

「プログラミング」や「開発技術」,「大学院の苦労話」について情報発信してます.これからのIT時代を生き抜くため,自分のスキルを磨き続けます.将来は起業できたらいいなという思いがあります.

oyoshiをフォローする
このエントリーをはてなブックマークに追加
スポンサーリンク
スポンサーリンク
AtCoder python アルゴリズム プログラミング
にほんブログ村に参加中(^~^)
PVアクセスランキング にほんブログ村
おーよしぶろぐ

コメント

タイトルとURLをコピーしました