WUPC2nd C問題
- 1. 第2回 ?早稲?田?大学プログラミングコンテスト C: ?至?高のケーキ keyword: 全探索索
- 2. 问题概要 : いちご : ケーキ ケーキの切切り分けの例例
- 3. 问题概要 : いちご : ケーキ 無効な切切り分けの例例
- 4. 问题概要 : いちご 得られる効?用の最?大値はいくつ？ : ケーキ 無効な切切り分けの例例
- 5. 制約 ¤?? ケーキの?大きさ <= 30
- 6. 解法 ¤?? 全探索索（全ての場合を試す）するだけです ¤?? (開始x座標, 開始y座標, ケーキのサイズ) ¤?? 4パターンあるのでそれを全部試す ¤?? いちごを?見見つけたら処理理を打ち切切る。 ¤?? 計算量量 : O(N^4)、O(N^5)でも多分OK ¤?? 30^5 = 24,300,000
- 7. 別解 ¤?? 型を回すのではなく、ケーキを回す。 ¤?? 縦横のサイズが変化するので注意 ¤?? ケーキを90度度ずつ回転させ、 それぞれについて1パターンのみを調べればOK
- 8. なぜなら（他の形も同様） ケーキを右に90度度 という形は にそれぞれ等しい 回転させた時の
- 9. 統計 ¤?? First AC : evima(08:06) ¤?? 正解数 : 112 ¤?? 通した?人(112/205) : 55% ¤?? ACだった解答(112/262) : 43%