kumakumaaaaa https://blog.hatena.ne.jp/kumakumaaaaa/ kumakumaaaaa精進記録 https://kumakumaaaaa.hatenablog.com/ 問題へのリンク 問題概要 M人の受験者をN個の機械で監視するとき、機械がが監視しないといけない最大範囲を最小にしたときの値をもとめよ。また監視はx,y両方の方向から行う。 制約 2 1 0 考えたこと x方向,y方向それぞれ独立に考えることができる 最大範囲を二分探索で求めれそう 受験者が存在するx座標、y座標をソートしてX,Yに格納しておく。最大範囲をmとするとき、あるi,j (i よって以下の方法でこの問題が解ける。 mを決める 必要な機械数を求める 必要な機械数がN以下ならmよりも小さい最大範囲で観測ができるか試す。Nより大きいなら最大範囲を大きくして試す。(二分探索) mが定まるまで1… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fkumakumaaaaa.hatenablog.com%2Fentry%2F2020%2F08%2F20%2F225457" title="2008年 日本情報オリンピック春合宿OJ Cheating: カンニング対策 - kumakumaaaaa精進記録" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2020-08-20 22:54:57 rich https://kumakumaaaaa.hatenablog.com/entry/2020/08/20/225457 1.0 100%