htkb-proconの日記

初心者がPythonで問題解いた記録

yukicoder No.751 Frac #2

No.751 Frac #2 - yukicoder

最初、問題の意図がつかめなかったが、括線の長さを見ると分子側は一番上から分母側は一番下から処理していくようだ。

分子側は

   1
  ---
   2
 -----
   3
-------
   4

の場合、(1/2)/3 = 1/6(1/6)/4 = 1/24のようにやり、分母側は

   1
-------
   2
 -----
   3
  ---
   4

の場合、2/(3/4) = 8/31/(8/3) = 3/8みたいにやる。これを式にまとめるとyukicoderの解説にある式になるようだ。で最後に分子と分母で約分するんだけど、解説ページにある通り負数を取り得ることに気をつけないと

while n > 0:
    gcd, n = n, gcd%n

みたいなwhileの条件を最初から満たさずわけわからん数がgcdになっちゃうので注意が必要(1WA)。pythonの場合はmath.gcdが用意されててそっちは負数もちゃんと処理してくれるんだけど、3.5から実装なのでpythonが3.4のatcoderで使うともれなくRuntime Errorを食らってしまう諸刃の剣。

なんてことない問題に見えるけど数弱としてはWA叩きまくって色々学びがあったので記す。いやこれatcoderで300点問題とかで出たら泣きますよほんと。