Tenka1 Programmer Contest C - 4/N ( Python )

今日はこの１問！！
atcoder.jp

難易度は緑で1151diff

なかなか面白い要素が色々詰まっていたので紹介したいと思います！

1. 問題見て考えたこと

これは制約がであるから、O(n^2)までなら間に合いそう。

だけどそれだと仮にh, nを決めても w が決まらないじゃん...と考えてしまいます。

しかしこれは無理やり等式を式変形して w = 〇〇の形にしてしまえば全部の未知数を定めることが出来るのです！！

2. 無理やり式変形する

という結果が得られたので、後はコード書くだけ！！

3. 嘘解法

これで準備が終わりいざ提出！ポチッ
...
...
...

WA結果

なんとWA！！
この時の提出コードはこちら

N = int(input())
for h in range(1,3501):
    for n in range(1,3501):
        if (4*h*n-N*h-N*n) != 0 and ((N*h*n)/(4*h*n-N*h-N*n)) > 0:
            if 4/N == ((4*h*n-N*h-N*n)/(N*h*n)) + (1/n) + (1/h):
                exit(print(h,n,int((N*h*n)/(4*h*n-N*h-N*n))))

なぜだろう。すると隣にいた緑コーダーの友達が、
「これ浮動小数点数のままで計算してるからバグるんじゃないですか？」
と言われました。

自分のコードはif文で = で与式のまま確かめていたのでダメみたいでした。

なので少し言い換えると、
このような w が存在する ⇆ Nhnを4hn-Nn-Nhで割った時に余りが0になる
ということを確かめれば良いという事がわかります！！

4. 正しい解法

したがって、改善してACしたコードはこちら

N = int(input())
for h in range(1,3501):
    for n in range(1,3501):
        if (4*h*n-N*h-N*n) != 0 and ((N*h*n)/(4*h*n-N*h-N*n)) > 0:
            if N*h*n%(4*h*n-N*h-N*n) == 0:
                exit(print(h,n,int((N*h*n)/(4*h*n-N*h-N*n))))

5. 最後に

初めて緑diffの解説をしました。
なかなか面白い問題で解いていて楽しかったです。
間違っている場所などがあれば報告お願いします。
最後までありがとうございました！！