ABC001からABC007までやってみた思い出

AtCoder

AtCoder Biginner Contestの001から007までやってみて学んだことを覚えている限り

ABC001-D 感雨時刻の整理

いもす法というシンプルですごいアルゴリズムを知った。

いもす法 - いもす研 (imos laboratory)

蟻本を買った当時はまだ生まれていなかったアルゴリズムというのもエモい。

ABC003-D AtCoder社の冬

  1. パスカルの三角形を使うと、足し算のみで二項係数を求められることを知った
  2. 剰余演算の分配則

(a+b) \bmod n = ( (a \bmod n) + (b \bmod n)) \bmod n

ABC006-D トランプ挿入ソート

最長増加部分列（ Longest Increasing Subsequence）というアルゴリズムを知った。

最長増加部分列(LIS)の長さを求める - Qiita

ABC007-D 禁止された数字

桁DPというアルゴリズムを知った。

桁DP入門 - ペケンペイのブログ

ここまでJavaScriptで解答してきたが、JavaScriptで表現できる整数が53bitまでという問題があり、Kotlinに切り替えた（AtCoderのNodeのバージョンではBigIntegerは使用できない）。