pythonのsortの公式ドキュメントを読んでみた。

要点
sortの方がsortedよりも速い。
キーをラムダで指定するより、itemgetterの方が速い
itemgetterでは、二段階でのソート条件を指定できる。
パイソンでは、Timsortを使っているらしい。参考

from operator import itemgetter
sorted(student_tuples, key=itemgetter(2))

sorted(student_tuples, key=itemgetter(1,2))
>>[('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]

GitHub で初めてのHPを公開

まずは、Create a new repositoryから、新しいレポジトリーを作成。
名前は、ユーザーネーム.github.io.git とした。

作成したレポジトリーアドレスを、自分のパソコンにクローン。
コマンドプロントから、

git clone https://github.com/username/username.github.io.git

を実行。

cd username.github.io

ディレクトリーをクローンしたディレクトリーに移動。

クローンディレクトリー内に、htmlファイルを作成。名前はindex.htmlとした。

コマンドから、
git add index.html
git commit -m "First commit"
git push

としたら、クローンディレクトリーが、githubに反映されます。

初めてのHPができました。

ABC 176

また少しレーティングは上昇。今日はA-Cの三問解けましたが、緑以上になるためにはやはり、4問5問解かないとダメそうです。時間内には解けませんでしたが、今回はD問題、E問題もそんなに難しくなかったです。

今日の学びは、E - Bomberから。

if 〇〇　in list

がとても遅いと言うこと。

if 〇〇　in set

に変更したら、簡単にE問題が通りました。高速化のところは、まだまだ知識が足りません。

Dのような問題が自力で解けると少し嬉しい。

ABC175

C問題まで解いて、少し上がりました。

for/else

for 文の最後にelse節を書くと、ループが最後まで回った後、else節が実行される。
今までは、if節で、iが最後になった時と書いていたけど、知ってればちょいちょい便利！
早速使ってみた。

atcoder.jp

n = int(input())
ls = [int(input())]
for _ in range(n-1):
    next = int(input())
    ls.sort()
    for i in range(len(ls)):
        if next <= ls[i]:
            ls[i] = next
            break
    else:
        ls.append(next)
print(len(ls))

区間スケジューリング問題を考える

区間スケジュール問題では、後ろの値でソートして、前側から順に決定していくが、その答えが本当に最適解なのか考えてみた。

上段の図を、アルゴリズムから決定したものとして、それが最適解でなかったと仮定する。

その場合、両端のバーの中に2個のバーが含まれる可能性が考えられるが、そのようなバーが存在するとすると、バーの決定順序は後ろの値でソートされているので、一個目のバーはBの様なバー（後ろの値が、Aの後ろの値よりも後ろ）が想定される。その上で、もう一個バーが存在するとなると、右端のバーの左端と、Bの右端の間に含まれる事になる（Cのバー）が、Cのバーが存在していた場合、区間スケジューリングのアルゴリズムでAと右端のバーの間に挿入されているはずで、矛盾する。

キーエンス プログラミング コンテスト 2020 B - Robot Armsatcoder.jp

n = int(input())
ls = [(0, 0)] * n
for i in range(n):
    x, ln = map(int, input().split())
    l = x - ln
    r = x + ln
    ls[i] = (l, r)
#print(ls)

ls.sort(key=lambda x: x[1])
#print(ls)
last = -float('inf')
count = 0
for i in ls:
    if last <= i[0]:
        count += 1
        last = i[1]
print(count)

全BIT探索 061ABC C - たくさんの数式

s = input().rstrip()
n = len(s)


def value(m):
    num = s[0]
    ans = 0
    for i in range(1, n):
        t = (m >> (i - 1)) & 1
        if t == 1:
            ans += int(num)
            num = s[i]
        else:
            num = num + s[i]
    ans += int(num)
    return ans


count = 0
for i in range(2 ** (n - 1)):
    count += value(i)

print(count)