問題

D – マーブル

プログラミング初級者から上級者まで楽しめる、競技プログラミングコンテストサイト「AtCoder」。オンラインで毎週開催プログラミングコンテストを開催しています。競技…

atcoder.jp

記録

• 2022/4/10 ギリギリ。
• 2022/4/9 うまく実装できず。
• 2022/4/5 解法わからず。

解法

• 0から1000まで並んだ箱に R,G,B の順にマーブルを入れていったときの最小コストを求めると考える。
• マーブルを1移動させるのにコストは1必要。
  \(R,G,B \leq 300\) なので、いい感じに並べれば \(1000\)を超えることない。
  \(0 〜 1000\) の \(0\) から R からを置いていくとするとコストはそれぞれ、
  R のコストは 400(中央から-100) – 置いた位置
  G のコストは 500(中央) – 置いた位置
  B のコストは 600(中央から+100) – 置いた位置
  と言える。
• あとは、dp。
  dp[見ている箱][残りのマーブル]:= この状況になるための最小の移動数とする。

コード例

#include <bits/stdc++.h>
using namespace std;
#include <atcoder/all>
using namespace atcoder;
using ll = long long;
using P = pair<int, int>;
#define rep(i, n) for(int i = 0; i < (n); ++i)
// using mint = modint998244353;
// using mint = modint1000000007;
// const int mod = 1000000007;
// const ll INF = 1LL << 60;
const int INF = 1001001001;

int R, G, B;

// マーブルを1移動させるのにコストは1必要。
// R,G,B <= 300 なので、いい感じに並べればは1000を超えることない
// 0 〜 1000 の 0 からRを置いていくとすると
// R のコストは 400(中央から-100) - 置いた位置
// G のコストは 500(中央) - 置いた位置
// B のコストは 600(中央から+100) - 置いた位置
// と言える。

int cost(int pos, int cnt) {
  if(G + B <= cnt) {
    // Rを置く
    return abs(400 - pos);
  } else if(B <= cnt) {
    // Gを置く
    return abs(500 - pos);
  } else {
    // Bを置く
    return abs(600 - pos);
  }
}

int main() {
  cin >> R >> G >> B;

  int sum = R + G + B;
  // dp[見ている箱][残りのマーブル]:= この状況になるための最小の移動数
  vector<vector<int>> dp(1000, vector<int>(sum + 1, INF));

  // マーブルを1個触っていないとき（残りマーブル = sum）は 0
  rep(i, 1000) { dp[i][sum] = 0; }

  // i番目にマーブルを置かなかった場合と、マーブルを置いた場合で小さい方を採用
  for(int i = 1; i < 1000; ++i) {
    rep(j, sum) { dp[i][j] = min(dp[i - 1][j], dp[i - 1][j + 1] + cost(i, j)); }
  }

  // 全パターンの最小値が答え
  int ans = INF;
  rep(i, 1000) { ans = min(ans, dp[i][0]); }

  cout << ans << endl;
  return 0;
}