[ABC275 Python]AtCoder Beginner Contest 275 A～C問題Python解説

ABC275の解説記事です。
ミス等ありましたらコメントにてご連絡ください。

A問題

A - Find Takahashi

N = int(input())
H = list(map(int, input().split()))

h = 0
ans = 0
for i in range(N):
    if H[i] > h:
        ans = i
        h = H[i]
print(ans+1)

よく出題される変数を2個保持する問題です。

まずは橋の高さを表すh
そして何番目の橋が高いのかを表すansです。

与えられたリストHの先頭から順番に見ていき、
今までの最長の橋よりも高い橋であれば、
最長の橋を更新します。

最後に何番目(インデックスなので+1)の橋が一番高いのか出力します。

B問題

B - ABC-DEF

A, B, C, D, E, F = map(int, input().split())

print((A*B*C-D*E*F)%998244353)

C言語等で解いている方はオーバーフローに気を付けて項を1つずつ余りを求める必要がありますが、Pythonではそのようなことはありません。

C問題

C - Counting Squares

import itertools

S_sharp = set()
for i in range(9):
    S = list(input())
    for j in range(9):
        if S[j] == "#":
            S_sharp.add((i,j))

ans = 0
for i in itertools.combinations(S_sharp, 4):
    distance = set()
    for j1, j2 in itertools.combinations(i, 2):
        # print(j1,j2)
        distance.add((j1[0]-j2[0])**2+(j1[1]-j2[1])**2)
    
    if len(distance) == 2:
        ans += 1

print(ans)

（PyPy3で実行してください！）

いろいろな求め方が考えられますが、
1例として説明いたします。

プログラムの概要としては、
＃の座標を保存して、
その中から4点を取ってきます。
その4点が正方形ならカウントされるという感じです。

では、プログラムを見ていきましょう。
S_sharpに＃の座標を保存します。

次にS_sharpの中から考えられる4点の組み合わせを全探索します。
私のお気に入りitertools.combinations()です。

最後にこの4点が正方形を成すかどうかですが、
正方形の性質として、まず「4つの辺の長さが同じ」があります。
ただ、これだけだとひし形も含まれてしまうため、
この性質に加えて、「対角線の長さが等しい」
という性質も加えて正方形だけを判定します。

具体的にはこれも4点の中から2点を選ぶ組み合わせを全探索します。
1つの点から他の3つの点への組み合わせがありますが、
3つのうち2つは正方形の辺となるもの
残りの1つは正方形の対角線となるものになります。

判定方法としては組み合わせの種類数を数えて、
辺の長さと対角線の長さの2種類のみであれば、
正方形と判断します。
辺の長さと対角線の長さが一致することはないので、
2種類として断定できます。