はじめに
こんにちは。ももはらです。 AHC037で初黄パフォをとったの参加記を残そうと思います！
問題概要
- N個の(a,b)の座標を作りたい
- 次の操作を0回以上5N回以下できるので、できるだけコストを最小化したい
- 座標 (x,y) から x'>=x, y'>=y の座標 (x',y') をコスト (x'-x) + (y'-y)で作ることができる
- 元の座標も残る
実装
案1: 一番近い座標から作ってみる
- 考察
- まずはN点直接作る場合について考えると、最短距離の座標から伸ばすのが最適
- 提出
- 得点: 3430697513
- sample0の結果: Cost = 43850900145, Score = 22803065
案2: くの字の位置の右下に中継点を足してみる
- 考察
- コスト (x'-x) + (y'-y) でx,y独立なので、 (x', y') -> (x', y) -> (x,y) みたいに、x,yそれぞれで動いてもコストは同じ
- くの字の位置に中継点を置いておく
- 提出
- 得点: 4072232940
- sample0の結果: Cost = 36739552599, Score = 27216851
案2': くの字の位置の右下に中継点を足してみて、使わなかったら左上においてみる
- 考察
- 右下に置いた中継点を使わなかったら、左上に中継点置いてみる
- 確実に損はしないのでこの方針を書いてみた
- （後の方針とぶつかったので案3の時には消えました）
=> 
- 提出
- 得点: 4386163855
- sample0の結果: Cost = 34370792954, Score = 29092576
案3: 左の直線に伸ばした方がよくなるなら、直接伸ばしてみる
- 考察
- すでに左側に直線があったら、そこに中継点を置いて、伸ばした方がいいパターンがある
=> 
- 提出
- 得点: 4534273060
- sample0の結果: Cost = 33013876167, Score = 30288322
案4: 下の直線に伸ばした方がよくなるなら、直接伸ばしてみる
考察
- 案3の下に伸ばすバージョン
- 案3の下に伸ばすバージョン
- 得点: 5120976945
- sample0の結果: Cost = 29490148079, Score = 33907423
案5: 無駄な頂点をのぞく
- 考察
- みやすくしたら考察しやすくなるかなーと思ったら何故かスコア伸びた
- 提出
- 得点: 5218181604
- sample0の結果: Cost = 28842972744, Score = 34668234
おわりに
最終順位は71位でした！
