atcoder

wiki, tech, tech
Page content

Atcoder でプログラミングの勉強だ

About Atcoder

Contest memo

AtCoder Beginner Contest 042

D - いろはちゃんとマス目 / Iroha and a Grid

むずいなぁ。いい線いっているはずなんだけどなぁ。

  • ポイント

    • 通れないエリアがあって、そこを通らなさそうな地点 p が複数ある。具体的には 座標 (x, B) (ただし 0 <= x <= H-A) に対して y 方向から入っていくパターンの組み合わせを作れば良さそうよ。
    • つまり (start から p の到達方法の組み合わせ) x (p から goal の到達方法の組み合わせ) 的な感じ。これを全 p に対して求めて総和を求める。
    • マス目の移動が組み合わせ問題だというのを思い出せるまで相当時間がかかった。数学の世界懐かしい…よく出来ていたなぁ。
    • 組み合わせを求める nCr について、素直に n! / ((n-r)! * r!) の通り階乗 (r! = 1 * 2 * ... * r ってやつ) を使うと計算時間と数字の桁で死ぬので、注意が必要。
      • そう思っていたけどこれが悪いかも

  • 書いてみたけど重たそう

    def combination(n, r):
    if n == 0:
        return(1)
    answer = 1
    for i in range(r):
        # print('{}/{}'.format(n-i, r-i))
        answer *= (n-i) / (r-i)
    return(answer)


def problem_d():
    H, W, A, B = map(int, input().split())

    answer = 0
    for i in range(H-A):
        # print('{}x{} and {}x{}'.format(i, B-1, H-i-1, W-B-1))
        # print(
        #     'combination({}, {}) * combination({}, {})'.format(
        #         i + B-1, B-1, H-i-1 + W-B-1, W-B-1))
        answer += combination(i + B-1, B-1) * \
            combination(H-i-1 + W-B-1, W-B-1)

    mod = 10**9 + 7
    print(int(answer % mod))


problem_d()

  • わかっていないところ

    • うまくあわないケースが有り、正答に至っていない。なにか考え方間違えている？

  • 改善ポイント推測