AtCoder など競プロで学んだこと

これはCompetitive Programming Advent Calendar 2017の 17 日目の記事です。

AtCoder のレートは緑です。最近ようやく水色に届きました。そんな筆者ですが、AtCoder など競プロで学んだ内容をいくつか紹介したいと思います。

long に収まらない整数の余りを BigInteger を使わずに求める

64 bit を超える整数の余りを BigInteger を使わずに求める方法を、この問題から学びました。
BigInteger を使える言語には関係ないと思われるかも知れませんが、BigInteger に変換するだけで TLE になるケースがあるため、この計算方法を知っておくことは重要です。

# s mod m を計算する
def mod(s, m)
  n = 0
  for c in s.chars
    n = (10 * n + c.to_i) % m
  end
  n
end

n / m の切り上げ

// いままでずっとこう書いてました
int x = (n / m) + (n % m == 0 ? 0 : 1);

// 上の式は、以下のように書けます
int y = (n + m - 1) / m;

この計算方法は、以下で紹介されています。

gcd と lcm の分かりやすい説明

最小公倍数と最大公約数についての、とても分かりやすい説明があります。図がわかりやすく理解を助けてくれます。

この記事を読んだあとに、実際に SRM 611 の問題にチャレンジすると大変勉強になります。

桁 DP の学び方

pekenmpy さんの桁DP入門は非常に分かりやすいです。

上記の記事で桁DPを学んだ後は、以下の問題が解けるようになります。