Pythonで解くAtCoder(ABC175:B) - クルトンのプログラミング教室

こんにちは、クルトンです！
この記事では

AtCoderの「AtCoder Beginner Contest 175」のB問題をPythonを使って解説します。

問題のリンクを載せておきます。

入力の受け取り方や、for文の使い方、setの使い方は下の記事で解説しています。

1行に複数の数字の入力があるときの受け取り方

list(map(int,input().split()))

今回の場合は

L = list(map(int,input().split()))

とすることで入力を受け取れます。

今回はNが小さいので、3本の棒を選ぶ方法を全通り調べて、そのうち条件を満たすものが何通りあるかを数えればよいでしょう。

for文の3重ループを使うと、3本の棒を選ぶ方法を全通り調べることができます。

for i in range(N-2):
    for j in range(i+1, N-1):
        for k in range(j+1, N):
            (L[i], L[j], L[k]を使った処理)

ではここからは条件をどのようにコードに変換するかについて考えましょう。

まず $「L_i,L_j,L_kがすべて異なる」$ という条件ですが、これはset文を使うことで表せます。

len(set([L[i], L[j], L[k]])) == 3

より一般化すると、「リストLの要素がすべて異なる」という条件は

len(L) == len(set([L[i], L[j], L[k]]))

と表せます。

この条件式は便利なので覚えておくとよいでしょう。

次に $「3辺の長さがL_i,L_j,L_kであるような三角形が存在する」$ という条件をコードに変換します。

ここで、三角形の3辺を $a, b, c$ とし、そのうち一番長い辺を $c$ とすると、三角形の存在条件は

　 $c < a + b$

となります。

また、これをさらに式変形すると

　 $2c < a + b + c$

となり、条件式は

　 $2 \times (最も長い辺) < (三辺の合計)$

となります。

よって今回は

2 * max([L[i], L[j], L[k]]) < sum([L[i], L[j], L[k]])

と表せます。

（※前もってLをソートしておくと $L_k$ が常に最大になるのでより簡潔に書くことができます。しかし、いきなり最初にソートするとなぜソートするのかが分かりにくいため、ソートしない解法について書きました。）

よって、0を代入した変数 $cnt$ を用意しておき、上の条件式を満たす $L_i,L_j,L_k$ が出てくるたびに1を足していけば、最終的に $cnt$ が答えとなります。

このような回数を数えるための変数を「カウンター」と呼びます。

以下にサンプルコードを載せておきます

今回は

という問題でした。

「リストLの要素がすべて異なる」という条件の言い換えはサラッとできるようになっておきましょう！

ではまたお会いしましょう！さようなら～