正方形

問題の説明

1個の1×1サイズのメッシュからなる横長W、縦長Hの矩形紙を左上から右下に切り取った場合、切り取られていない格子数を求める.

例

上図の色が付いていない格子の数は80格子です.

に答える

アイデア

1.欲しい価格は？

=>取得する値=セル全体の個数-クリップされたセルの個数=W*H-クリップされたセル

2.カットされたチェックの数は?

青い三角形と緑の三角形は似たような関係です.そのため、青い三角形の雨辺の長さを知れば、緑の三角形の雨辺を知ることができます.このとき、青色三角形の一辺の長さは、緑色三角形の一辺の長さ/緑色三角形の横方向、縦方向の最大公約数に等しい.したがって、図中の青色三角形の横、縦は2,3である.

青三角形の横、縦2×3サイズの長方形で、三角形の斜辺によってカットされたセルは、最左上隅のセルの下、右の順にコーナーを描き、最右下隅のセルと同じパスになります.このパスのセル数は、一番左上のセルから一番右下のセルまでの最短距離に等しくなります.したがって、切り出されたセルの個数は、横長+縦長-1=2+3-1=4となる.

青三角形の斜辺は、切り出された格子の個数が緑三角形の横、縦の最大公約数の個数と重複するため、切り出された格子の個数が青三角形で切り出された格子の個数の最大公約数=4 4 4=16個となる.

3.最大公約数を得るには?

ユークリッド湖製法を利用する.

ユークリッドアークほう

ウィキペディア-ユークリッドスキンケア参照.

コード#コード#

def solution(w, h):
    def get_gcd(a, b):
        while b > 0:
            a, b = b, a % b
        return a
    
    gcd = get_gcd(w, h)
    
    # (w * h) - (w / gcd + h / gcd - 1) * gcd
    return (w * h) - (w + h - gcd)