ゲームAI備忘録

ゲームAIに使えそうな知識を備忘録として書き留める

人助けと思って何卒インストールをば! 詰碁/ アルコネ/ 五目並べ

SRM596 IE

概要

あるn個の要素 vector<int> desiredArray が与えられている.
要素の値が0となるn個の要素を以下の操作を繰り返すことで,desiredArray と一致させるための最小回数を求めたい.

  • ある要素を+1する
  • すべての要素を2倍する

制約条件

  • 1 <= n <= 50
  • 1 <= desiredArray[i] <= 1000

考えたこと

数 val になるように+1 や *2 した最小回数を f(val) とする.
この最小回数となる方法が複数存在する場合は,*2倍の回数が多いやり方がより最適な解とする.
(*2なら他の要素の回数も減らせる可能性があって効率がいいから.)
この事をn個の要素に対して行い,

  • 2倍する最大の回数 max_dbl と
  • +1 した回数の総数 sum_inc

の和を答えとする.

コード

#define INF (1<<29)
#define MOD 7777
int dp[1050]; // target value => (number of increment, number of double)

class IncrementAndDoubling {
public:
	int f(int val) {
		if (val == 0) return 0;
		if (dp[val] != -1) return dp[val];
		int res = f(val-1) + MOD;
		if (val % 2 == 0) {
			res = min(res, f(val / 2) + 1);
		}
		return (dp[val] = res);
	}

	int getMin(vector <int> desiredArray) {
		for (int i = 0; i < 1050; ++i) dp[i] = -1;
		int n = desiredArray.size();
		int sum_inc = 0;
		int max_dbl = 0;
		for (int i = 0; i < n; ++i) {
			int inc_dbl_pair = f(desiredArray[i]);
			sum_inc += inc_dbl_pair / MOD;
			max_dbl = max(max_dbl, inc_dbl_pair % MOD);
		}
		return sum_inc + max_dbl;
	}
}