本記事の内容
- 自分の解法
- 期間中の動き
contest url
問題内容
1000*1000の空間に特定の面積以上をもつ長方形敷き詰める
- N日これを連続して行う
- 面積を敷き詰めた後の仕分け線の「取り除き、追加」がコスト
-「取り除き、追加」が重複している部分はコスト0 - 初日の配置もコスト0
- コストを最小にする
自分の解法
-
重視したのはできるだけ面積が正方形の形に近くように配置
-
しき詰めるときは無駄のないように端っこから詰めていく
-
期間中の動き
03/22 ~ 03/23
- 各面積を高さ1000の長方形を同じ方向に敷き詰めた
03/24 ~ 03/25
- 高さがすこしずづ小さくなるようにしき詰める向きを
- 横
- 縦
の交互になるようにする事で改善した
03/27 ~ 03/28
- 別サイトコンテストに出ていた
- codingame spring challenge 2024
- 結果 143 rd / 2664
- 応用情報とっているけどSQL知識が抜けてたので難しかった
~ 04/01
- 長方形から正方形のほうがスコア改善するので修正した
本解法の問題点
- 一定のコスト削減まで可能だったがこれ以上劇的にスコアを良くすることが難しい
- コスト削減する一番の方法である「重複している所のスコア0」を有効活用いない
自分より上位解法を見た感じ
- 「重複している所のスコア0」の活用を
- 初日:今後変化しない高さ1000の長方形を同じ方向に敷き詰める
- これをさらに切り分ける事で各日の要件を満たしのコストの改善を行っていた
まとめ
- プレテスト 197位
- 最終順位 ?
- 途中まで積み上げたスコアが行き詰まり、改善する際には別方針を考えるのが重要