誤差
Grundy 数がフラクタルっぽい構造を示していた! 問題へのリンク 問題概要 個の石の山がある。各山には 個の石がある。先手と後手が交互に以下の操作を繰り返す。 山を一つ選ぶ。その山には石が 個あるとする。 その山の石の個数が 個または 個となるように…
数学っぽい問題好き!!! 問題へのリンク editorials 問題概要 個のカフェオレがある。 番目のカフェオレは、コーヒーが mg、ミルクが mg だけ入っている (ともに整数)。 これらを混ぜて作れるカフェオレのうち、コーヒー量 とミルク量が がともに正の整数…
平面グラフの面の個数を考える系問題 ジャッジへのリンク 問題へのリンク 問題概要 二次元平面上に 本の直線が与えられる。これらの直線は、それらを通る 2 点の座標 ( と を通る) で与えられる。 これらの直線によって、平面全体が何個の領域に分割されるの…
幾何だ!! ジャッジページへのリンク editorial 問題概要 の長方形の紙上に 個の点がある。これらの点は互いに相異なる。 これらの点から 4 つの点 A, B, C, D を選ぶ (選ぶ順番も考慮する)。そして、点 A を中心として点 B を通る円を O1 とし、点 C を中…
ICPC 系列でよくありそうな雰囲気の問題! 問題へのリンク 問題概要 二次元平面上で原点から出発し、 回にわたって、以下の動きのいずれかを確率 1/4 で選択して実施する。 回の動き終了後に座標 にいる確率を求めよ (許容誤差は )。 x 座標を する x 座標を…
資源配分問題とも言われるタイプの問題。均等配分からの摂動で良さそう (嘘解法) だと騙すことを狙った! 問題へのリンク 問題概要 個の正の整数 (総和を とする) が与えられたとき、 が最小値となる を満たすような非負整数の組 を求めよ。複数通り考えられ…
面白かった! 問題へのリンク editorial 問題概要 次の問題が ケース分与えられる。 二次元平面上に 個の格子点が与えられる。これらに対し、以下の条件を満たす直線 が存在するかどうかを判定せよ。 どの点に対しても、 との距離が等しい 制約 考えたこと …
誤差は怖い!!!!!!! 問題へのリンク 問題概要 整数 と、"x.yz" のフォーマットで与えられる実数 が与えられる。 の小数点以下を切り捨て、結果を整数として出力せよ。 制約 考えたこと 数値誤差が怖いというテーマの問題は、パナソニックコンでもあっ…
最小包含円と似て異なる問題。 問題へのリンク 問題概要 二次元平面上に 個の点がある。 半径 1 の円を上手に配置したときに、その中に含めることにできる点の個数の最大値を求めよ。 制約 考えたこと 「 点のうち 2 点を通る半径 1 の円」に探索候補を絞っ…
sky さんの Monotone Minimma の例題!!! 練習として解いてみた。 問題へのリンク 問題概要 (意訳) 個の値の組 , が与えられる。 で であり、 は狭義単調増加、 は狭義単調減少である。 を適切に定めたときのスコアが、 で与えられる。スコアの最小値を求…
ついこの間の AGC でもあった「〜が終了するまでの回数の期待値」に関する問題!!! それにしても数値誤差しゃん... 150 人が提出してAC 2 人という恐ろしい問題。 実はこの回の writer であった ymatux さんから、直接話を聞いたのだった。Petr はこの回 r…
連立方程式の練習。多項式補間でも解ける。誤差がきつい。 問題へのリンク 問題概要 次多項式 がある (係数はわからない)。 個の点 の値がわかっている...はずだったが、そのうちの 1 個については間違った値が出力された状態で入力が与えられる。どれが間違…
有理数さん。。。 誤差がとんでもなく厳しいらしく、有理数ライブラリを使うということをついに覚えた!!! あと、問題の解法自体は「区間串刺し」といういわゆる「区間スケジューリング問題」の亜種。 問題へのリンク 問題概要 とある水族館に住むイルカ君…
ごろごろごろごろ 問題へのリンク 問題概要 球を、地面を点 から点 へと直線的に移動する。 直線の周りには直方体が配置されていて、その直方体と球が物理的に干渉しないようにしたい。 極端な話、球の半径が ならば干渉することはない。球の半径をどこまで…