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を学んだ後は、以下の問題が解けるようになります。
- ABC 029 - D - 1
- 1 以上 N 以下のすべての整数に含まれる 1 の個数を求める問題です。
- ABC 007 - D - 禁止された文字
- [A, B] の範囲の数のうち、4 または 9 が含まれる数値がいくつあるかを求める問題です。
- Typical DP Contest - E - 数
- N 以下の整数で、各桁の和が D の倍数である個数を求める問題です。