ABC218-D問題
N = int(input())
def read():
locateXY = []
for _ in range(N):
x,y = map(int, input().split())
locateXY.append((x,y))
return locateXY
locateXY = read()
locateXwithYlist = {}
for locateX, locateY in locateXY:
if not locateX in locateXwithYlist:
locateXwithYlist[locateX] = []
locateXwithYlist[locateX].append(locateY)
newLocateXwithYlist = {}
xlist = []
for x, ylist in locateXwithYlist.items():
if len(ylist) < 2:
continue
newLocateXwithYlist[x] = locateXwithYlist[x]
countall= 0
for x1, ylist1 in newLocateXwithYlist.items():
for x2, ylist2 in newLocateXwithYlist.items():
if x1 >= x2:
continue
count = 0
for y1 in ylist1:
if y1 in ylist2:
count+=1
c = 1
for k in range(count-1, count+1):
c*= k
countall += c//2
print(countall)
ABC218-D問題を解きました。変数名やコードなどがぐちゃぐちゃですが、出来上がったコードを保存する目的でこちらに投稿しました。
一応僕なりの手法を、後で自分が見返したときに分からなくならないように記載しておきます。
問題の内容は、二次元平面上にN個の点があり、それらの点のうち4つを結んだときに出来上がる長方形はいくつありますか、というような問題です。
また、長方形の辺はx軸またはy軸に平行である必要があるようです。
入力としては最初の行に与えられる点の個数、その次の行からは各点の座標(x y)が与えられます。出力としては、4点を結んだときにx軸y軸に平行になるような長方形の個数を出せばいいらしいです。
ここからは僕なりのやりかたを書いていきます。
まずx軸またはy軸に平行な長方形を作るには、x座標が同じでy座標が異なる頂点が二つ、そして、それと対になるような形で、x座標が同じで、先ほどの二つの点と同じy座標をもつような二つの点が必要です。
言葉にするのが難しいので例をあげると、
二つの赤い点は同じx座標をもっていますよね。
そして、二つの青い点は、青い点同士のx座標が同じで、赤い点のy座標と同じですよね。
なのでx座標ごとにグループ分けをして、あるx座標に結び付くy座標が、他のx座標に結び付くy座標と何個一致するかをカウントしていけば最終的な答えに辿り着けそうです。
以下はプログラムの細かい解説です。
N = int(input())
def read():
locateXY = []
for _ in range(N):
x,y = map(int, input().split())
locateXY.append((x,y))
return locateXY
locateXY = read()
ここまででx,y の情報をリストに格納しています。
locateXwithYlist = {}
for locateX, locateY in locateXY:
if not locateX in locateXwithYlist:
locateXwithYlist[locateX] = []
locateXwithYlist[locateX].append(locateY)
この処理では、点のx座標をkeyに、そのx座標に対応した複数のy座標のリストをvalueに設定しています。
ちょっと正しい日本語が使えているか怪しいので、具体的に説明させてもらうと、
(2 0),(2 1), (2 2) といった三つの座標があるとします。これらの点はx座標が一致しているのでこのx座標をキーにして、y座標をリストとして紐づけると、
{ 2 : [ 0 , 1 , 2 ]} みたいな辞書になります。
newLocateXwithYlist = {}
xlist = []
for x, ylist in locateXwithYlist.items():
if len(ylist) < 2:
continue
newLocateXwithYlist[x] = locateXwithYlist[x]
次に先ほどの辞書のxに結び付いたyのリストが2つ以上ないような要素を排除した新たな辞書を作っています。
言い換えるなら、x座標が同じになる二つ以上の点が無いような状態です。この状態だとx軸に平行な直線が作れないので排除します。
countall= 0
for x1, ylist1 in newLocateXwithYlist.items():
for x2, ylist2 in newLocateXwithYlist.items():
if x1 >= x2:
continue
count = 0
for y1 in ylist1:
if y1 in ylist2:
count+=1
c = 1
for k in range(count-1, count+1):
c*= k
countall += c//2
print(countall)
この処理ではあるx座標に結び付いたy座標のリストから一つ一つyを取り出して、他の異なるx座標に結び付いたy座標リストの中に何個ぐらい一致するものがあるかをcount変数でカウントしています。
例として、このcount変数が2になるときは、あるx座標と他のx座標において、一致するy座標が二つあるということになるので、長方形の個数はこの二つから二つを選んだ組み合わせとなるので、2C2 = 1 みたいな感じになります。
そしてカウントした値を基に組み合わせの公式を使って、何個ぐらい長方形を作れるかをcountall変数でカウントしています。
組み合わせの公式は
5C2 = (5*4)/(2*1)みたいな感じのやつです。
もっと簡略化して書きたいのですが、実力が追いつきません。今回、atcoderをやっていて、ふと自分のコードを記録したいと思ったのでこうやって駄文を書き連ねさせていただきました。プログラミングに関しての記事を書くのは今回が初めてとなるのですが、分かりやすい文章を書くのってメチャクチャ難しいですね。
他人のプログラム解説記事などを見ていると分からないことも多くて、その度に「もっと分かりやすく書いてくれよ」などと偉そうなことを思っていたので、過去の自分をぶん殴ってきたいと思います。
この記事が気に入ったらサポートをしてみませんか?