7/28

午前中、昨日かいた復習問題をAC,Flattenは逆元の問題で時間があれば余裕だった。white_pown は前やった時こんなもの解けないって思ってたけど、座標圧縮とかに慣れてきたから割とすんなり。

3時から数学、隣の人が変な人で７時くらいに帰ってしまったけど、４章まで進んだ。。あと集合と位相の勉強しないとルベーグ積分入門できないので夏休みにやる予定の二冊が終わったらちまちまと進めたい。

あとFlutterの環境構築とか。

夜のatcoderではダイクストラ法復元経路問題といた。

synthetic kadomatsuが構築問題というか全探索問題で、こういうのが本当に苦手。でもプログラミングとして結構大事な問題だとは思うので最重要で復習したい。

明日の復習コンテストは

synthetic kadomatsu

sugoroku

multiple of 2019

夜の演習コンテストは

Score Attack

League

753

sugar water

あと一時間だけでいいので統計学の勉強を。

7/27

午前中　桁dpを2問頑張っていたが、てこずり三時間くらいかけて黄色diffを倒して終わり。。

３時から５時は虚無。5；３０あたりから数学の勉強。ガンマ関数とかベータ関数とか、あとは解析学の基本的なところ。進捗ゴミすぎるけど数学は時間かかるからしょうがない。

９時からatcoderに取り組む。ダイクストラ法の復元dpみたいなやつAC(水色)青色のやつも解けそうだったけど、二項係数を事前にdpで出すってことをめんどくさがったら誤差が出て死んだと思われる。

近々パスカルの三角形を履修したい。

明日は朝、復習コンテストとして

Flatten,white pawn,Balanced_Pを頑張りたい。

演習として

Synthetic Kadomatsu

XXOR

Wide flip

Blue Bird

をやる。

昼間、思い切って４章まで終わらせたい。

7/26 精進日記

朝、1:30くらいAtcoder で練習。その後一時間くらいだらだら解説みてました。昼は病院と洗濯、飯などしてたらすぎていて、4:00-8:00にかけて帰省。電車中にred polyominoについて考えたり、水色diffの累積和dp解いたりしました。家に帰ってきてからred polyominoの実装と二時間くらい格闘。

明日の朝は桁dpコンテスト　夜はその復習。

午前中までに統計学の勉強が一章進めばいいなあ。

あとは多変数の微分積分の本1hくらい取り組みたい。あとは昼間にがっつり統計学の勉強しよう。

中国じょうよていり

qiita.com

fenwick treeによる転倒数と使い方

class Fenwick_Tree:
    def __init__(self, n):
        self._n = n
        self.data = [0] * n

    def add(self, p, x):
        assert 0 <= p < self._n
        p += 1
        while p <= self._n:
            self.data[p - 1] += x
            p += p & -p

    def sum(self, l, r):
        assert 0 <= l <= r <= self._n
        return self._sum(r) - self._sum(l)

    def _sum(self, r):
        s = 0
        while r > 0:
            s += self.data[r - 1]
            r -= r & -r
        return s
N = int(input())
A = list(map(int,input().split()))
bit = Fenwick_Tree(N)
ans0 = 0
for n in range(N):
    bit.add(A[n],1)
    ans0 += n+1 - bit._sum(A[n]+1)
print(ans0)
for k in range(N-1):
    ans0 = ans0+N-A[k]*2-1
    print(ans0)
自分より小さいものの数とか数えていける。

DFSでタイムスタンプ

IN = [0 for _ in range(N)]
OUT = [0 for _ in range(N)]
cnt = 0
def DFS(now):
    global cnt
    IN[now] = cnt
    for next in Edge[now]:
        cnt += 1
        DFS(next)
    cnt += 1
    OUT[now] = cnt
DFS(0)

高速素因数分解

num = 10 ** 6 #素因数分解したい最大の数
def primes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    return [i for i in range(n + 1) if is_prime[i]]
P = primes(num)

yaku = [1 for _ in range(num+1)]
for i in P:
    k = int(10**6 / i)
    for j in range(1,k+1):
        if i > 1 and yaku[i*j] == 1:
            yaku[i*j] = i

def prime(a):
    ans = set()
    while yaku[a] != 1:
        ans.add(yaku[a])
        a = int(a/yaku[a])
    return ans
print(prime(24))->{2,3}