Abc#004d
Download as pptx, pdf0 likes357 views
This is solution for atcoder begginers contest #004-d merble
![動的計画法
＊ 左から赤、緑、青のマーブルが順にならぶ
＊ 赤が残ってるなら緑、青は置けない。
緑が残ってるなら青は置けない。
＊ 2次元配列dpを用意する
dp[今いる箱の位置][マーブルの個数]
＊ これでマーブルの個数が0になるまで行う
＊ 自分は箱の個数を1000個と想定した](https://image.slidesharecdn.com/abc004d-150220030958-conversion-gate02/85/Abc-004d-11-320.jpg)
![続き
for(int i =0;i<1001;i++){
for(int j =0; j<=N;j++){
int cost=0;
if(j <= r) cost = abs(400-i);
else if( j <= r+g )cost = abs(500-i);
else cost = abs(600-i);
if(!j) dp[i][j]=0;
else if(i+1 < j) dp[i][j]=mi;
else if(!i && j == 1)dp[i][j] =cost;
else{
int x = dp[i-1][j-1] + cost;
int y = dp[i-1][j];
dp[i][j]=min(x,y);
}}}](https://image.slidesharecdn.com/abc004d-150220030958-conversion-gate02/85/Abc-004d-12-320.jpg)
![続き
＊ 最後にどのスタート位置からの距離が最小か調べる
for(int i=0;i < 1001;i++){
mi = min(mi,dp[i][N]);
}](https://image.slidesharecdn.com/abc004d-150220030958-conversion-gate02/85/Abc-004d-13-320.jpg)
Abc#004d
- 2. 自己紹介 ＊ @_ktwr ＊ ctf初心者、競プロ雑魚 ＊ 得意言语は辫测迟丑辞苍()
- 3. 本日の資料 ＊ Maharaにあるよ！！ ＊ ダウンロードしてOfficeで見るのが面倒くさい方に →狠狠撸 Share 後であげます。
- 4. 問題 -100 0 100 ... ... -100 0 100 ... ...
- 5. まずはじめに 最終的なマーブルの始まる位置と終わる位置がわかれば 移動量は求められる！！ -101 -100 -2 0 1 98 100 101 ... ... 1 0 2 1 0 1 1 0 1 移動量=(1)+(2+1+1)+(1+1)=6
- 7. 解き方 ＊ マーブルの数は300までという指定から 緑の動かす範囲を適当に決める 自分は-500?500で指定 ＊ マーブルの始まる位置,マーブルの個数, 基準となる位置から距離を計算する関数の作成
- 8. 前述関数について x c x+N-1 ＊ 開始位置がx,マーブルの個数がN,基準点がcとすると ... ... となるのでこの距離を求めてあげれば良い
- 9. 続き ＊ ただ途中で正負が入れ替わる可能性を考える必要あり -180 -100 -50 ... ... -100 0 40 ... ...
- 10. 続き //距離を求める関数 int calc(int x,int y){ return (x+y)*(y-x+1)/2; } long long dis(int N,int n, int cen){ int x = n -cen; return abs(calc(min(0,x),min(0,x+N-1)))+abs(calc(max(0,x),max(0,x+N-1))); }
- 11. 動的計画法 ＊ 左から赤、緑、青のマーブルが順にならぶ ＊ 赤が残ってるなら緑、青は置けない。 緑が残ってるなら青は置けない。 ＊ 2次元配列dpを用意する dp[今いる箱の位置][マーブルの個数] ＊ これでマーブルの個数が0になるまで行う ＊ 自分は箱の個数を1000個と想定した
- 12. 続き for(int i =0;i<1001;i++){ for(int j =0; j<=N;j++){ int cost=0; if(j <= r) cost = abs(400-i); else if( j <= r+g )cost = abs(500-i); else cost = abs(600-i); if(!j) dp[i][j]=0; else if(i+1 < j) dp[i][j]=mi; else if(!i && j == 1)dp[i][j] =cost; else{ int x = dp[i-1][j-1] + cost; int y = dp[i-1][j]; dp[i][j]=min(x,y); }}}
- 13. 続き ＊ 最後にどのスタート位置からの距離が最小か調べる for(int i=0;i < 1001;i++){ mi = min(mi,dp[i][N]); }