AtCoder Regular Contest 018 B - 格子点と整数

目次

はじめに

• AtCoderの問題を復習しています．

• 公式解説や上位陣による解説ブログを読んで，自分に足りなかった部分や得られた知見を自分なりに消化してアウトプットしようと思います．

想定読者

• 筆者と同じくらいのレートの方：失敗談・回り道をみて，共感していただける部分もあるかもしれません．

• コンテストのwriterの方：サンプルではありますが，レート茶色上位～緑下位の参加者がつまづく可能性があるポイントを知っていただく機会になるかもしれません．

記事の狙い

• 丁寧でわかりやすい解説記事がたくさん公開されているため，解法そのものについての記述は少ないと思います．

• ACに至るまでにどうしてそのような発想に至ったのか，考察や実装で試行錯誤した過程（=失敗談や回り道）を重視しています．

• また，得られた前提知識や着眼点について，今後応用できるように抽象化・言語化していきます．

• 間違いや勘違いなどがございましたら，ご指摘・ご指導いただけると幸いです（大歓迎です）．

  • 連絡先：@k_hiro1818

問題のリンク

B - 格子点と整数 (100点)

ACに至るまでの考察・実装のコツなど

• 点のうち，3点を選ぶ組み合わせを列挙する．制約条件から計算量がのため全探索が可能．Python3のライブラリ（itertools.combinations）を使うと実装はかなり楽．
• 面積を計算する．方法は，ABC002 C - 直訴を参照．3点のうち，1点が原点となるように調整する必要がある．
• 面積が整数かどうかを判定する．このときに，面積が0より大きいかつ偶数かどうかで判定すると誤差が発生する心配がない．

提出コード

試行錯誤した過程

• if文で小数を含めた判定をしまった．
  • 誤差が発生する可能性を失念していた．
    
    

得られた知識・知見

• ヘロンの公式で回答されている方も．

疑問点

• 公式解説で「面積が整数かどうかは頂点のxの偶奇,yの偶奇にしかよら ないので各格子点を4通りにグループ分け…」のところがどうしてそう言えるのが理解できていない．

感想

• 組み合わせの列挙するときに，Pythonのライブラリに頼ってしまうところがある．自力で実装できるようにしたいです．

• 小数の扱いについて，見直すきっかけとなったいい問題だったと思います．

• 初見の問題で，過去問で見たという要素（三角形の面積の計算）があると，精進した効果があったのかなと思います．

• 数学の知識・理解を深める必要がありそうだと思いました．

課題

• 公式解説の「ちなみに」部分で計算量の少ない別解が示されている．高難度の問題に向けた基礎力をつけるためにも理解したい．

参考

• 公式解説

• サムネイル画像

記事を執筆された皆さまへ: 掲載不可の場合はお手数をお掛けしますが，@k_hiro1818までご一報ください．