後７問

Project Euler完答まで後７問。残ってる問題に対するメモ。

• 177 Integer angled Quadrilaterals
  • 問題まだ読んでない。どう見ても幾何。いやだなぁ。
• 195 Inscribed circles of triangles with one angle of 60 degrees
  • これも幾何。方針はなんとなく分かる。
• 194 Coloured Configurations
  • DPで解けそう。詳しく検討してないが。
• 208 Robot Walks
  • まったく見当もつかなかったが、一時間程前に突如解法が思い浮かんだ。まだ確かめる事がいくつかあるが解けそう。
• 212 Combined Volume of Cuboids
  • 区分木＋sweep line algorithm、もしくは包除原理で解けるはず。二次元版は解いたことある。コーディング待ち。
• 210 Obtuse Angled Triangles
  • 「中心が原点にある半径rの円に含まれる整数座標の個数」と等価な問題。解法はもう浮かんでる。コーディング待ち。
• 199 Iterative Circle Packing
  • Descartes' theoremを使えば解けそう。コーディング待ち。

ついでに今日解いた問題に対するコメント。

• 167 Investigating Ulam sequences
  • 「ulam(2,2n+1), n>=2はちょうど二つの偶数項を持つ」という事実を利用（この事実に対する証明が書いてある論文が見つからない、、、）。循環が現れるのでそれを利用。