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を学んだ後は、以下の問題が解けるようになります。

再帰に対する考え方を教えてくれた練習問題

確か『LISP I』だったと思うけど、次のような練習問題があった。

2 つの引数をとり、その 2 つの値の合計を返す関数を書け。ただし + は使わずに 1+ と 1- を使って。
なお、2 つの引数は正の整数と仮定してよい。

答えをみたら「なあんだ」と思えるが、その当時は自力でこの問題を解くことができなかった。 再帰に対する考え方を教えてくれた関数のひとつとして、その影響は大きい。

(defun add (x y)
  (if (zerop x)
      y
    (add (1- x) (1+ y))))

; Emacs の *scratch* バッファでの実行結果
(add 1 2)
; 3
(add 100 2)
; 102

数値文字参照を文字に変換するPythonスクリプト 

import re


def conv(s):
    cs = []
    for e in re.findall("&#x([0-9a-fA-F]+);", s):
        cs.append(chr(int(e, 16)))
    return "".join(cs)


def main():
    s = "ファイルまたはアセンブリ"
    print(conv(s)) # ファイルまたはアセンブリ


if __name__ == "__main__":
    main()

リンク

文字参照 - Wikipedia

自然数から平方数を取り除いた数列の N 番目を求める

A000037 - OEIS の式を使って求めます。

; https://oeis.org/A000037

(define (f n)
  (+ n (exact-integer-sqrt (+ n (exact-integer-sqrt n)))))

実行結果です。

% gosh -l ./not-square-numbers.scm
gosh> (map f (iota 100 1))
(2 3 5 6 7 8 10 11 12 13 14 15 17 18 19 20 21 22 23 24 26 27 28 29 30 
 31 32 33 34 35 37 38 39 40 41 42 43 44 45 46 47 48 50 51 52 53 54 
 55 56 57 58 59 60 61 62 63 65 66 67 68 69 70 71 72 73 74 75 76 77 
 78 79 80 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 
 101 102 103 104 105 106 107 108 109 110)

バットとボールの問題を SageMath で解く

sage

問題：バットとボールはセットで1ドル10セントします。バットはボールより1ドル高いです。ボールはいくらですか？

http://karapaia.com/archives/52047106.html

$ sage                                                             
┌────────────────────────────────────────────────────────────────────┐
│ SageMath version 7.2, Release Date: 2016-05-15                     │
│ Type "notebook()" for the browser-based notebook interface.        │
│ Type "help()" for help.                                            │
└────────────────────────────────────────────────────────────────────┘
sage: var('bat ball')
(bat, ball)
sage: f = [bat + ball == 110, bat == ball + 100]
sage: solve(f, bat, ball)
[[bat == 105, ball == 5]]