2021-02-13

Sum of Floor

無限にありそうな問題。

1以上の整数 $N$ と $M$ が与えられます。
$\sum_{i=1}^{M}\lfloor \frac{N}{i}\rfloor$ を求めてね。
$1\leq N,M\leq 10^9$

これを計算量 $O(\sqrt{N}\log{N})$ くらいで解こう〜

解法( $\lfloor(\sqrt{N}\rfloor\leq M$ のとき)

1. baby-step?

$\sum_{i=1}^{\lfloor(\sqrt{N}\rfloor}\lfloor \frac{N}{i}\rfloor$

を計算しよう。愚直にやればいいです。

2. GIANT=STEP?

$\lfloor\sqrt{N}\rfloor \leq i$ とすると、 $\lfloor \frac{N}{i}\rfloor \leq N$ です。

1以上の整数 $j$ を決めたとき、 $\lfloor \frac{N}{i}\rfloor = j$ なる $i$ の個数は二分探索で雑に求められるので、 $\lfloor\sqrt{N}\rfloor$ 回くらいのイテレーションで $j$ を全探索しながら $j$ に対する $i$ の個数を求めましょう。

こ〜ど

気をつけなければいけないことがあって、

baby-stepとGIANT=STEPで数え上げのダブりがあってはならない

$\lfloor \frac{N}{i}\rfloor = j$ になるような $i$ がない場合を警戒する

といった感じのことに気を配りながらコードを書きました。

N, M = map(int, input().split())

#naive
res = 0
for i in range(1, M + 1): res += N // i
print(res)


#cleverer
res = 0
sq = int(N ** 0.5)
for i in range(1, M + 1):
  if N // i <= sq: break
  res += N // i

for i in range(1, sq + 1):
  ok = M
  ng = 0
  while ok - ng > 1:
    m = (ok + ng) // 2
    if N // m <= i: ok = m
    else: ng = m
  l = ok

  ok = 0
  ng = M + 1
  while ng - ok > 1:
    m = (ok + ng) // 2
    if N // m >= i: ok = m
    else: ng = m
  r = ok
  if N // l == i: res += i * (r - l + 1)
print(res)

おしまい

あ〜あこの問題ratedのコンテストでうっかり出ねーかな
あと何となくlog落ちそうな感じがします

2020-12-09

二項係数の積の総和と怪文書

なんかこの前のARCで出てえらい目みたので思いつきでまとめていきたいとおもいます。
verifyとかしてないし議論の正確性は保証しません。

二項係数の積の総和をまとめることを組み合わせ論的解釈を通して試みていきたいと思います。
ここでは、 $(x_i < y_i)$ ならば

$\binom{x_i}{y_i}= 0$

とします。

1. 下が不定

Q.
非負整数列 $a_1, a_2, ..., a_n$ と非負整数 $S$ が与えられます。
総和が $S$ になるようなあり得る全ての非負整数列 $x_1, x_2, ..., x_n$ について、 $\prod_{i=1}^{n}{\binom{a_i}{x_i}}$ を計算して総和を出力してください。

ごちゃごちゃと数式で書けば下式のような感じ。ウワsumの下にsumがあるきも

$\underset{\sum_{i=1}^{n}{x_i}=S}{\sum}\prod_{i=1}^{n}{\binom{a_i}{x_i}}$

言い方を変えていきたいと思います。

Q.
$n$ 個の箱があり、 $i$ 番目の箱には $a_i$ 個の区別可能なボールが入っています。各箱からいくつかボールを選んで合計 $S$ 個ボールを取り出すとき、取り出し方は何通りありますか。
（ただし、取り出し方が同じであるというのは取り出した後のボールの集合が一致することを指します。）

うんうん。例えば次のような感じです。

ex.)
a = [5, 2, 2], S = 5

ooxox xx ox

上の||で囲まれたところが箱で、内部のoが残ったボール、xが取り出したボールを指しています。
この場合は1番目の箱から2個、2番目から2個、3番目から1個取り出す例のひとつを表しています。

ん？

ooxox

↓

ooxox xx ox

↓

ooxoxxxox

なんということでしょう。箱を破壊してボールをひとつにまとめることができてしまいました。なにこれ？
重要なのは「ボールの区別ができる」ということが「箱の区別」を包含しているということです。

取り出したボールが区別可能なら、例えば取り出した後のボールを見て「あ、この形は2番目の箱から取り出した左から1番目のボールだな......」と解釈して箱の状態を復元することができるはずです。
この理屈でいけば、二項係数の積の総和をひとつの大きな二項係数に置き換えられそうです。

問題がさらに言い換えられます。

Q.
$1$ 個の箱があり、箱には $\sum_{i=1}^{n}{a_i}$ 個の区別可能なボールが入っています。各箱から合計 $S$ 個ボールを取り出すとき、取り出し方は何通りありますか。

クソ簡単やん＾＾
というわけで、

$\underset{\sum_{i=1}^{n}{x_i}=S}{\sum}\prod_{i=1}^{n}{\binom{a_i}{x_i}} = \binom{\sum_{i=1}^{n}{a_i}}{S}$

このように変形できました。ひゃ〜〜〜〜

2. 上が不定

Q.
非負整数列 $a_1, a_2, ..., a_n$ と非負整数 $S$ が与えられます。
総和が $S$ になるようなあり得る全ての非負整数列 $x_1, x_2, ..., x_n$ について、 $\prod_{i=1}^{n}{\binom{x_i}{a_i}}$ を計算して総和を出力してください。

少し変わりました。 $a_i$ と $x_i$ が入れ替わりましたね。下式で表せます。

$\underset{\sum_{i=1}^{n}{x_i}=S}{\sum}\prod_{i=1}^{n}{\binom{x_i}{a_i}}$

言い方を変えていきたいと思います。

Q.
$n-1$ 個の仕切りがあり、横一列に並んだ互いに区別可能な $S$ 個のボールたちの間に仕切りを入れて $n$ 個の区間にボールを分割します。この状態でそれぞれ $i$ 番目の区間から $a_i$ 個ボールを取り出す方法は何通りありますか。
（ただし、取り出し方が同じであるというのは、仕切りの置き方が同一で、取り出した後のボールの集合も一致することを指します。）

いや、むっっっっっっっっっず

ex.)
a = [5, 2, 2], S = 12
oxxxox || oxx || xx
xxxxoo || xxo || xx

こんな例も作れるわけですが......
選んだボールxと仕切り||だけ取り出してみます

ん？
oxxxox || oxx || xx　→ xxxx||xx||xx
xxxxoo || xxo || xx　→ xxxx||xx||xx

おやおや＾＾
xと||の順序関係は決まっているので、この中での順列は考えなくて良いです。
ということはxと||は同じものとして見做して良いので、||→xとしましょう。

仕切りの数は $n-1$ 個ですから、次のように問題が言い換えられます。

Q.
横一列に $n-1+S$ 個の区別可能なボールが並んでいます。各箱から合計 $n-1+ \sum_{i=1}^{n}{a_i}$ 個ボールを取り出すとき、取り出し方は何通りありますか。

やった〜〜

したがって下式が得られました。

$\underset{\sum_{i=1}^{n}{x_i}=S}{\sum}\prod_{i=1}^{n}{\binom{x_i}{a_i}} = \binom{n-1+S}{n-1+\sum_{i=1}^{n}{a_i}}$

3. 上下が不定

Q.
非負整数 $S, T$ が与えられます。
総和が $S$ になるようなあり得る全ての非負整数列 $x_1, x_2, ..., x_n$ と、総和が $T$ になるようなあり得る全ての非負整数列 $y_1, y_2, ..., y_n$ について、 $\prod_{i=1}^{n}{\binom{x_i}{y_i}}$ を計算して総和を出力してください。

ふむふむ。式に表すと次のような形です。

$\underset{\sum_{i=1}^{n}{x_i}=S}{\sum} \underset{\sum_{i=1}^{n}{y_i}=T}{\sum} \prod_{i=1}^{n}{\binom{x_i}{y_i}}$

これは実は2.において仕切り||と選んだボールxを区別するバージョンにあたります。
合計 $n-1+T$ 個の（仕切り||と選んだボールx）から $n-1$ 個の仕切り||の位置の組み合わせを考えると、

$\binom{n-1+T}{n-1}$

とわかるので、これを2.で得られた式の右辺に乗じれば良さそうです。

$\underset{\sum_{i=1}^{n}{x_i}=S}{\sum} \underset{\sum_{i=1}^{n}{y_i}=T}{\sum} \prod_{i=1}^{n}{\binom{x_i}{y_i}=\binom{n-1+S}{n-1+T}\binom{n-1+T}{n-1}}$

二項係数を階乗に直して少し計算してもいいでしょう

$\underset{\sum_{i=1}^{n}{x_i}=S}{\sum} \underset{\sum_{i=1}^{n}{y_i}=T}{\sum} \prod_{i=1}^{n}{\binom{x_i}{y_i}}=\frac{(n-1+S)!}{(S-T)!(n-1)!T!}$

4. まとめ

$\underset{\sum_{i=1}^{n}{x_i}=S}{\sum}\prod_{i=1}^{n}{\binom{a_i}{x_i}} = \binom{\sum_{i=1}^{n}{a_i}}{S}$

$\underset{\sum_{i=1}^{n}{x_i}=S}{\sum}\prod_{i=1}^{n}{\binom{x_i}{a_i}} = \binom{n-1+S}{n-1+\sum_{i=1}^{n}{a_i}}$

$\underset{\sum_{i=1}^{n}{x_i}=S}{\sum} \underset{\sum_{i=1}^{n}{y_i}=T}{\sum} \prod_{i=1}^{n}{\binom{x_i}{y_i}=\binom{n-1+S}{n-1+T}\binom{n-1+T}{n-1}}$

かく得られました。やった〜〜

2020-09-12

たまにはなんかかく

ほにゃほにゃぴ

たまにはなんかかく。

いちおうブログだし......

書くことがないけど書くってむずかしいですね。

昔日記をつけようとしていたことがありましたが、文字通りの３日坊主で終わったことを思い出しました。日常、そんなに書くことがない。

近況の箇条書きでもしようかしら。

・学業

調子乗ってすみませんでした......ってかんじ。オンライン授業になってから多少向き合い方が変わりました。なんとかなるといいね。

・就労

塾講師。社会科目以外のだいたい全てを教えていますが知識量に衰えを感じてきました。（合成高分子の製法とか、使わないものは忘れていく）有能三ヶ条をやっていればとりあえずOKな仕事。

・競技プログラミング

AC青、CF青(紫タッチ）。AtCoder青になった時は勢いづいていて黄パフォが結構出たので夏までには黄色になっているだろうと思っていました。現実は厳しい！

初歩的なミスが増えました。バチャとかをあまりしなくなったせいだと思います。コンテスト前にかたならしバチャをするようにしてみたら少しマシになりました。

・音楽ゲーム

Arcaeaばっかりやっていましたが最近Phigrosにはまりました。全譜面を芸術譜面にリニューアルしたり隠し曲にクソデカ解放演出があったりしてびっくりしました。Arcaeaのポテンシャルは今だいたい11くらいです。

・動画

高校生くらいの頃までゲーム実況とかやっていたんですよね〜。動画編集のリハビリに何かを制作しています。学生ライセンスでPremiereを使っていますが、VideoStudioの方が好きかもしれません。AfterEffectは昔使っていました。

・絵

ペン先のエイムが上達しました。塗りの工程をどこかにまとめたい。

・人生

貪慾法最高〜

うお〜ん5000兆円ほしいよ〜（おわり）

2020-09-08

AtCoder Library Python3, PyPy3用

AtCoder

AtCoderから公式スターターパックが遂に待望のリリース！

やべ〜〜〜〜PythonやめてC++に乗り換える方が楽では？

がんばって毎日こつこつ書いて揃えようと思います。名前順とかで書きます。
全部あるかはわかりません。

1. Convolution

mod 998244353に限定したFMT(NTTとも)です。
多項式同士の乗算で各項の係数を求めることができます。nは2冪でa, bの長さより2倍以上大きな値を渡しておき、fmtして得られた数列の同index要素を掛け合わせてifmtすると畳み込みが終了します。重すぎて50万オーダーはさすがに5secでもTLE 7secくらいはいりそう

class FastModuloTransformation:
  def __init__(self, n):
    self.n = n
 
    self.P = 998244353
    self.g = 3
    self.omega = pow(self.g, (self.P - 1) // n, self.P)
  def bitrev(self, a):
    n = self.n
    x = n.bit_length() - 1
    res = a[: ]
    for i in range(n):
      j = 0
      for k in range(x): j |= (i & (1 << k) > 0) << (x - k - 1)
      if i < j: res[i], res[j] = res[j], res[i]
    return res
  def fmt(self, a, base):
    if n == 1: return a
    P = self.P
    omega = base
    A = self.bitrev(a)
    half = pow(omega, n >> 1, P)
    i = n
    m = 1
    while i > 1:
      i >>= 1
      w = pow(omega, i, P)
      wk = 1
      for j in range(m):
        for x in range(j, len(a), 2 * m):
          l = A[x]
          r = wk * A[x + m] % P
          A[x] = (l + r) % P
          A[x + m] = (l + r * half) % P
        wk *= w
        wk %= P
      m <<= 1
    return A
  def ifmt(self, A):
    if self.n == 1: return A
    P = self.P
    nrev = pow(self.n, P - 2, P)
    return [(x * nrev) % P for x in self.fmt(A, pow(self.omega, P - 2, P))]

2. CRT

とど

3. Disjoint Set Union

まあただのUnionFindですよね。DSUの方がメジャーな言い方なのかしら。

class DisjointSetUnion():
  def __init__(self, n):
    self.n = n
    self.root = [-1] * (n + 1)
    self.rank = [0] * (n + 1)
  def leader(self, x):
    rt = self.root[x]
    if rt < 0: return x
    else: self.root[x] = self.leader(rt)
    return self.root[x]
  def merge(self, x, y):
    leader = self.leader
    xrt = leader(x)
    yrt = leader(y)
    if xrt == yrt: return
    if self.rank[xrt] > self.rank[yrt]:
      self.root[xrt] += self.root[yrt]
      self.root[yrt] = xrt
    else:
      self.root[yrt] += self.root[xrt]
      self.root[xrt] = yrt
      self.rank[yrt] += self.rank[xrt] == self.rank[yrt]
  def same(self, x, y): return self.leader(x) == self.leader(y)
  def size(self, x):  return -self.root[self.leader(x)]
  def group(self):
    n = self.n
    leader = self.leader
    res = [[] for _ in range(n + 1)]
    for x in range(n + 1): res[leader(x)].append(x)
    return [res[i] for i in range(n + 1) if len(res[i])]

4. Fenwick Tree

indexは[0, n]で使えます。sumは[l, r)の総和を返します。
lowerboundは総和がs以上になるような最小のindexとかを返すやつですがあんまり試していません。

class FenwickTree:
  def __init__(self, n):
    self.n = n
    self.data = [0] * (n + 2)
  def sum(self, l, r):
    s = 0
    while l > 0:
      s -= self.data[l]
      l -= l & -l
    while r > 0:
      s += self.data[r]
      r -= r & -r
    return s
  def add(self, i, x):
    i += 1
    while i <= self.n:
      self.data[i] += x
      i += i & -i
  def lowerbound(self, s):
    x = 0
    y = 0
    for i in range(self.n.bit_length(), -1, -1):
      k = x + (1 << i)
      if k <= self.n and (y + self.data[k] < s):
        y += self.data[k]
        x += 1 << i
    return x + 1

5. Floor Sum

なにこれ？よくわかりませんが一応作りました。

def FloorSum(n, m, a, b):
  # (a * 0 + b) // m + ... + (a * (n - 1) + b) // m
  res = 0
  if a >= m:
    res += (a // m) * n * (n - 1) // 2
    a %= m
  if b >= m:
    res += n * (b // m)
    b %= m
  if a * n + b < m: return res
  u = (a * n + b) // m
  v = (u * m - b)
  res += (n - (v + a - 1) // a) * u + FloorSum(u, a, m, (a - v) % a)
  return res

6. Lazy Segment Tree

とど

7. LCP Array

suffix arrayのLCPが出せます。

def LCPArray(n, s, sa):
  r = [0] * n
  for i in range(n): r[sa[i]] = i
  lcp = [0] * (n - 1)
  x = 0
  for i in range(n):
    if x > 0: x -= 1
    if r[i] == 0: continue
    j = sa[r[i] - 1]
    while max(i, j) + x < n:
      if s[i + x] != s[j + x]: break
      x += 1
    lcp[r[i] - 1] = x
  return lcp

8. Max Flow

とど

9. Min Cost Flow

とど

10. SCC

とど

11. Segment Tree

とど

12. Sufix Array

induced sortingを使っていません。O(NlogN)くらいです。

def SuffixArray(n, s):
  order = [n - 1 - i for i in range(n)]
  order.sort(key = lambda x: s[x])
  sa = [0] * n
  classes = [0] * n
  for i in range(n):
    sa[i] = order[i]
    classes[i] = S[i]
  k = 1
  while k < n:
    c = classes[: ]
    for i in range(n): 
      if i > 0 and (c[sa[i - 1]] == c[sa[i]]) and ((sa[i - 1] + k) < n) and ((c[sa[i - 1] + k // 2]) == c[sa[i] + k // 2]):
        classes[sa[i]] = classes[sa[i - 1]]
      else: classes[sa[i]] = i
    cc = [i for i in range(n)]
    ss = sa[: ]
    for i in range(n):
      if ss[i] - k >= 0:
        sa[cc[classes[ss[i] - k]]] = ss[i] - k
        cc[classes[ss[i] - k]] += 1
    k <<= 1
  return sa

13. 2-SAT

とど

14. Z-algorithm

ざるごりずむ。各接尾辞に対するLCPがわかる。

def Zalgorithm(S):
  ln = len(S)
  Z = [0] * ln
  Z[0] = ln
  i, j = 1, 0
  while i < ln:
    while i + j < ln and (S[i + j] == S[j]): j += 1
    if j:
      k = 1
      Z[i] = j
      while k < j and (k + Z[k] < j):
        Z[i + k] = Z[k]
        k += 1
      i += k
      j -= k
    else: i += 1
  return Z

2020-06-28

ABC172 F - Unfair Nim 解法

AtCoder

atcoder.jp

本番ではDとEで事故ったのでF見てる余裕ありませんでした。なかなか面白い問題でしたね。

ABCでNim出たの超久しぶりじゃない？

解法：

まず、Nimは山の石の数の累積xorが0以外のとき先手必勝、0のとき後手必勝です。そういうわけなので、3番目以降の山の累積xorを X として計算しておきます。

(1番目の山) xor (2番目の山) = X

となれば良いということがわかります。

ところで、(1番目の山) + (2番目の山) = Sとすると、Sは不変です。

したがって、

(1番目の山) & (2番目の山) = S - X

であることがわかります。これは、(1番目の山) xor (2番目の山)をしたときに、(1番目の山) & (2番目の山)となる部分の寄与は0となることからわかります。（同じ数字同士のxorは打ち消し合うから）

ところで、この問題は「a0 以下で、S - Xの立っているbitを包含するもののうち(S - X)、X以外に立っているbitがない」もののうち最大のものを構築することになります。

S - Xのbitは1番目の山、2番目の山共に含むので、ここから先に構築していきましょう。

S - Xのbitを全部立てた時にa0を超えてしまったら構築不能なので-1を出力します。

あとは「最大のものを構築する」という条件から、大きい方のbitから「Xでも同じbitが立っているか」「これを立てたらa0を超えたりしないか」をチェックしながら貪欲にbitを立てることで1番目の山の理想的な形が構築できます。

最後に、得られた1番目の山の値を元の1番目の山から引けばいくら移動させたかがわかるのでこれを処理して答えを得ます。

計算量はO(N + log(a_0 + a_1))かと思います。構築パートのO(log(a_0 + a_1))を計算量として評価するのってどうなんだろう　冗長でしょうか。

atcoder.jp

2020-05-06

機械学習で災害に関するツイートかどうかを判定する

ほにゃほにゃぴ

これです。

www.kaggle.com

なんか自然言語処理について色々知見があった気がしたので覚え書きをします。

コンペの概要

なんか数千のツイートが与えられるので「災害に関する内容か」をそれぞれ判定してください。学習用データも与えられるよ。

まずうちさあ、汚いデータあるんだけど

学習用と称して渡されたデータを見てみます。

#3: Car Recorder ZeroEdgeå¨ Dual-lens Car Camera Vehicle Traffic/Driving History/Accident Camcorder Large Re... http://t.co/kKFaSJv6Cj

EARTHQUAKE SAFETY LOS ANGELES ÛÒ SAFETY FASTENERS XrWn

tensorflowのtokenizerに渡して単語ごとに分割してもらおうというところですが、先に学習の妨げになる要素を破壊しておいた方が良いでしょう。

データをきれいにする

正規表現ライブラリreを使ってきれいにしましょう。

http://~~~みたいなやつ urlを取り除く
emojiを取り除く。文字コードで指定しておくとよいです
""とかを取り除く
stopwordsを取り除く。aとかtheとかです。nltkに取り除くやつがあります

ついでにnltkのSnowballStemmerで単語を語幹だけにしてやります。

tensorflow用のデータにしていく

データがきれいになったのでtensorflowのtokenizerでとーくんにしてもらいます。

この時にtrain用のデータをちょっと分割して試験用のデータを分けておきましょう。

ひとのモデルをパクる

適当にscipyでTF-IDFしても得点が伸びなかったのでGloVeを拝借しました。これでベクタライズはばっちりだと思います。

レイヤーを張るわね

embeddingレイヤ（GloVeのやつを処理して使う）
dropoutレイヤ（１次元　20%）
bidirectionalレイヤに突っ込んだLSTMレイヤ（よくわかんない）
denseレイヤ（密です活性化関数にはシグモイドを）

kerasのレイヤ多すぎて何がなんだかわからないわね

この辺自在に使えるようになりたいね

結果のやつ

train用データから分離させたデータでテスト

77.259 %

と出た。いいんじゃないの。scipyで色々なモデルつかって学習させてみても70%いかなかったのでびっくり。

提出データの正答率

78.732 %

どんな記事にも終わりはある

レイヤまわりがまだよくわかってない。日本語だったら分かち書きなんかが必要になってもっと面倒くさそうだなってかんじ。

2020-04-24

実績解除：AtCoder青色になった

実績

青タッチです。よかったね。

f:id:lowking:20200424132142p:plain — 青タッチ

実は2020年3月中に青になるのを目標にしていましたがまあええかという感じです。

現在のレートは1605でちょっと水パフォ出ただけで入水する背水の陣なので冷えないうちに早く得意な回を引きたいです。

青色になるまでやったことを書きます。

自己紹介

大学３年生になりました。電子情報系の何かを専攻している大学生です。中学生の頃にhspに触れていて、大学に入ってからpythonを勉強しました。

灰・茶・緑・水色になるまでにやったこと

以前の色変記事で書いたのでヨシ！

青色になるまでにやったこと

水difficulty埋め、青difficulty埋め、EDPC埋めなどに挑戦しました。EDPC埋めまくったあたりから黄パフォが出るようになりなんやかんやで青になりました。ABCでは難しくても50分以内の５完、あわよくば全完ができればいいんじゃないかなと思います。

精進について

f:id:lowking:20200424133935p:plain

前回の入水から300ACほど、RPS60000ほど増えています。知らんうちにShortestも増えました。入水が1月で今は4月ですから、3ヶ月で300ACしていたようです。他にやることないのカナ？＾＾

（これはあさかつなどの定期開催コンテストのおかげで1日あたりのAC数が増えたためだと思っています。参加は不定期ですが...）

水difficultyの問題は基本すぐわかるようになりました。青difficultyは、まあ、青下位くらいなら...という感じです。

精進の基本方針はやはり解けるかどうかわからないレベルの問題に挑戦することです。解法の発見にいたるまでの思考を開拓して、本番でできる限り幅広い思考ができるようにするには精進以外ないと思っています。

入水以降新しく覚えたアルゴリズムについて

ほとんど変わっていないはずです。

・KMP法（あまり使ってない）

・行列累乗（数列やらレピュニットやらグラフやら色々応用がある）

・行列式（行列木定理とか）

・非素数mod逆元（任意modでも大丈夫！だいじょうぶではないが）

・離散対数 Baby step Giant step（あまり使わないし、使う時ははっきりわかる）

・強連結成分分解（案外使わない）

・座標圧縮（無理やりBITやセグ木に載せたいときなどに使う）

・LCA（オイラーツアー＋SegTreeで作ったので要素が多いと役立たず）

・オイラーツアー（非再帰で書かせてくれーという気持ち　非再帰で書けないのかな）

・Dancing Links（₍₍ (ง ˙ω˙)ว ⁾⁾　かわいいね）

・全方位木DP（逆元はなくてもできるはずだけど逆元があると想像するのが楽）

・耳DP（えーたまにでる）

非再帰オイラーツアーとかダブリングLCAをやりたいですね。実際そんなにアルゴリズムは覚えなくてもOKです。

次回コンテストで入水してしまった場合に増える記事

ないです

どんな記事にも終わりはある

おまえのレートをたべちゃうぞー！

解法(のとき)

1. baby-step?

2. GIANT=STEP?

こ〜ど

おしまい

1. 下が不定

2. 上が不定

3. 上下が不定

4. まとめ

・学業

・就労

・競技プログラミング

・音楽ゲーム

・動画

・絵

・人生

1. Convolution

2. CRT

3. Disjoint Set Union

4. Fenwick Tree

5. Floor Sum

6. Lazy Segment Tree

7. LCP Array

8. Max Flow

9. Min Cost Flow

10. SCC

11. Segment Tree

12. Sufix Array

13. 2-SAT

14. Z-algorithm

解法：

コンペの概要

まずうちさあ、汚いデータあるんだけど

データをきれいにする

tensorflow用のデータにしていく

ひとのモデルをパクる

レイヤーを張るわね

結果のやつ

どんな記事にも終わりはある

自己紹介

灰・茶・緑・水色になるまでにやったこと

青色になるまでにやったこと

精進について

入水以降新しく覚えたアルゴリズムについて

次回コンテストで入水してしまった場合に増える記事

どんな記事にも終わりはある

解法( $\lfloor(\sqrt{N}\rfloor\leq M$ のとき)