競技プログラミング概要xy座標上の点がn個与えられる。このうち少なくともk点を含むような正方形のうち面積が最小のものを求めろ。考えたことx座標、y座標でそれぞれソートして小さい方からk点取る貪欲をしようとする。正方形を長方形だと誤読したりなぜか実装をバグらせたりした結果1時間くらい実装にかかる。サンプルを試すと落ちる。考えてみると貪欲が嘘。二分探索を思い浮かべ幅Xの正方形をつくることができるかの判定について考えてみる。各頂点が正方形の4隅になるパターンを試して判定するコードを実装するとサンプルが通った。提出するとシステスで落ちる。考えると二分探索の判定が嘘(4隅以外にすべきパターンが自明に存在する)。解説記事を読むと2辺固定すればk点を貪欲に取れるのでO(n^3logn)で解けるとある。実装するとk=1のときの処理がバグっていてシステスで一回落とす。k=1で4を返すようにしたら通った。難しく考えすぎて方針迷走&&実装バグらせまくりと色々ひどかった。学びオーダーが大きめの解法もちゃんと思考に入れる。変な実装ミスをしない。Close月別アーカイブリンクはてなブログブログをはじめる週刊はてなブログはてなブログProはてなブログをはじめよう!ferin_techさんは、はてなブログを使っています。ブログを報告するスターをつけました引用をストックしましたストック一覧を見る閉じる引用するにはまずログインしてくださいログイン閉じる引用をストックできませんでした。再度お試しください閉じる限定公開記事のため引用できません。