はじめに 競プロ精進中に「計算量的には間に合いそうなのにTLEする...」と悩んでいたところ、前準備のsort部分がボトルネックになっていたと発覚。 ハマったポイントを共有します。 tupleの配列のsort key指定あり/なしの違いについて、簡潔に説明します。 key指定あり a = [(3,3), (2,2), (3,1), (4,2)] a.sort(key=lambda x: x[0]) print(a) # => [(2, 2), (3, 3), (3, 1), (4, 2)] 指定したkeyの大小によって、sortを行います。keyの要素が等しければ、その順序は保持されます。 sort() メソッドは安定していることが保証されています。ソートは、等しい要素の相対順序が変更されないことが保証されていれば、安定しています。(公式ドキュメント) sort(key=lambda x: