読解が大変だけど、本質的には木 DP な問題 ジャッジへのリンク AOJ ページ 問題概要 本の棒を用いて、下図のようなモビールを作りたい。 入力としては、各棒 についての 左端から支点までの長さ 右端から支点までの長さ 左端からつながっている棒の index (…

Stern-Brocot 木がちょうどよく使える 問題へのリンク 問題概要 正の整数 が与えられる。分子・分母がともに 以下の正の整数であって、既約分数であるような分数の集合を と表すことにする。 を満たす最大の の要素 を満たす最小の の要素 をそれぞれ求めよ…

資源配分問題とも言われるタイプの問題。均等配分からの摂動で良さそう (嘘解法) だと騙すことを狙った！ 問題へのリンク 問題概要 個の正の整数 (総和を とする) が与えられたとき、 が最小値となる を満たすような非負整数の組 を求めよ。複数通り考えられ…

有理数使った 問題へのリンク 問題概要 二次元平面上に 個の点がある。これらの任意のペアを結んでできり直線たちを考える (異なるペアが同一の直線を生成するときは、一つの直線とみなす)。 これらの直線たちの交点が何点生じるかを求めよ。 制約 考えたこ…

有理数ライブラリ整備とか大げさなことせずに全探索頑張るのが本筋であろうが、ここでは有理数ライブラリの足し算の verify としてやってみた。 問題へのリンク 問題概要 有理数 p/q を n 個以下の 1/r な形の有理数の和として 分母 r の積が a 以下となるよ…

有理数さん。。。 誤差がとんでもなく厳しいらしく、有理数ライブラリを使うということをついに覚えた！！！ あと、問題の解法自体は「区間串刺し」といういわゆる「区間スケジューリング問題」の亜種。 問題へのリンク 問題概要 とある水族館に住むイルカ君…