ARC059E キャンディーとN人の子供

シェアする

  • このエントリーをはてなブックマークに追加

こんばんは。

本日から早速、プログラミングコンテストに関する記事を書こうと思い、難易度が高めの問題を解いてみました。

が、難易度が高いだけのことはあり、理解して解くまでに時間が掛かり、記事としての内容を充実させる時間がありません……。

ということで、とりあえず解いた報告とコードだけ掲載しておきます。

今回解いたのは、タイトルにもある通り、ARC059のE問題「キャンディーとN人の子供」です。

この問題は、DP(動的計画法)を用いることと、計算を楽に行う方法を思いつくことがポイントです。

練習として、普段はC#を使うのですが、C++で解いてみました。

細かい考察はまた明日追記するとして、とりあえずコードだけ掲載しておきます。考察書きます。

部分点解法:DP

部分点の制約では、A[i]=B[i]なので、f(A[0], A[1], ..., A[n-1])を計算するだけです。

従って、問題は「A[0], ..., A[n-1]を合計C個になるように掛け算したものを全部足す」という問題になります。

言い換えると、f(x_1, x_2, ..., x_n)は「全てのn次の単項式を足したもの」になり、これにA[0], ..., A[n-1]を代入せよ、ということですね。

このような「N個のものを一定条件を満たす個数だけ使ってどうこうする」というタイプの問題は、DP(動的計画法)を使うと解けることが多いようです。ナップザック問題が有名ですね。

DPは「漸化式を利用して計算量を減らす」というのが基本方針ですが、このパターンの場合「アイテムのi-1番目までを使う場合の数値から、i番目までを使う場合の数値を計算する」という手法が多いと思います。

今回の場合、「i-1番目までのA[]を使う場合のfの値から、i番目までのA[]を使う場合のfのを計算する」という手段になります。

ただし、今回は単項式の次数が関係するので、「i変数のj次単項式の総和を表す多項式にi番目までのA[](A[0], ..., A[i-1])を代入したもの」をdp[i][j]として保持しておきます。

そうすると、dp[i][j]は、「i-1番目までの数を使ったk次の総和にA[i-1]のj-k乗を掛けたもの」を全てのkについて足したものになります。

具体的に書くと、A=(2,3,4,5,6)のとき、

dp[2][0]=1

dp[2][1]=2+3=5

dp[2][2]=2^2+2*3+3^2=4+6+9=19

であり、

dp[3][2]=4^2+2*4+3*4+2^2+2*3+3^2

となります。dp[3][2]は、「"3番目までの数字を2個掛けたやつ"を全部足したやつ」です。

上の式をみると、

dp[3][2]=dp[2][0]*4^2+dp[2][1]*4^1+dp[2][2]*4^0

であることが分かります。

従って、

dp[i][j] = Σ[k=0, j] dp[i-1][j-k] * [i番目の数]^k

になることが分かります。A[]の添字は0から始まっているので、i番目の数はA[i-1]になることに注意です。また、j個ではなくj+1個足すことにも注意です。

そして、出力するのは「N番目までの数字をC個掛けたやつの和」なのでdp[N][C]になります。(dp[400][400]を使用する場合があるので宣言時はdp[401][401]として宣言することに注意)

dp[i][0]は、0次単項式(1つしか無い)の和なので全て1になります。

dp[0][i]は、0番目までを使う(つまり何も使わない)ので、i!=0のときは0になります。

これを実現したのが以下のC++コードです。

powMod()はx^nをmodで割った余りを求める関数です。

部分点制約を満たさないケースを飛ばしてジャッジ時間を節約するために、A[i]!=B[i]のものが見つかったら何も出力せず終了するようにしています。部分点狙いのときはよくやります。

・部分点解法

#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <vector>
 
#define repl(i,a,b) for(int i=(int)(a);i>(int)(b);i++)
#define rep(i,n) repl(i,0,n)

typedef long long ll; 

using namespace std;

ll powMod(ll x, ll n, ll mod) { ll res = 1; while (n > 0) {
		if (n & 1) res = res * x % mod;
		x = x * x % mod;
		n >>= 1;
	}
	return res;
}
 
const int MOD = 1000000007;
ll dp[401][401]

int main() {
	int N, C, A[400], B[400];
	ll ans = 0;
 
	cin >> N >> C;
	rep(i, N)cin >> A[i];
	rep(i, N)cin >> B[i];
 
	rep(i, N)if (A[i] != B[i])return 0;
 
	repl(i, 1, C)dp[0][i] = 0;
	rep(i, N)dp[i][0] = 1;
 
	repl(i, 1, N + 1) {
		repl(j, 1, C + 1) {
			dp[i][j] = 0;
			rep(k, j + 1) {
				dp[i][j] += dp[i - 1][j - k] * powMod(A[i - 1], k, MOD);
				dp[i][j] %= MOD;
			}
		}
	}
 
	cout << dp[N][C] << endl;
 
	return 0;
}

満点解法:多項式の性質を利用

満点解法では、以下の性質を利用します。

これは、例えば

のように因数分解できることから分かります。

満点制約において、

とすると、

となります。さらに一般化すると、

が得られます。ここで、右辺の

は、事前に「0からiまでの数のj乗の総和」をpowsum[i][j]として計算しておけば、

に対して

とすることでO(1)で計算することができます(事前計算の時間はO(NC))。

したがって、dp[i][j]の漸化式として

を用いることができ、部分点解法と同じ時間オーダーで計算することができるようになります。

ただし、今回はMOD=10^9+7で割った余りを用いるので、powsum[][]もMODで割った余りとして保持するのですが、そのとき、上記の引き算部分(powsum[B_(i-1)][k]-powsum[A_(i-1)-1][k]の部分)で後者の方が大きく、引き算の結果が負になる場合があります。

そうなると、負の数の剰余算が発生してしまうので、それを回避するためにMODを足して正にしておく必要があります。

以上を実現したのが以下のC++コードです。部分点解法のコードから少し変えている部分があるので注意してください。

・満点解法

#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <vector>
 
#define repl(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define rep(i,n) repl(i,0,n)

typedef long long ll;

using namespace std;

ll powMod(ll x, ll n, ll mod) { ll res = 1; while (n > 0) {
		if (n & 1) res = res * x % mod;
		x = x * x % mod;
		n >>= 1;
	}
	return res;
}
 
const int MOD = 1000000007;
 
ll dp[401][401], powsum[401][401];
 
int main() {
	int N, C, A[400], B[400], ans = 0;
 
	cin >> N >> C;
	rep(i, N)cin >> A[i];
	rep(i, N)cin >> B[i];
 
	// rep(i, N)if (A[i] != B[i])return 0;
 
	rep(i, C + 1)powsum[0][i] = 0;
	repl(i, 1, 401) {
		rep(j, 401) {
			powsum[i][j] = powsum[i - 1][j] + powMod(i, j, MOD);
		}
	}
 
	repl(i, 1, C + 1)dp[0][i] = 0;
	dp[0][0] = 1;
	repl(i, 1, N + 1) {
		rep(j, C + 1) {
			dp[i][j] = 0;
			rep(k, j + 1) {
				// dp[i][j] += dp[i - 1][j - k] * powMod(A[i - 1], k, MOD);
				dp[i][j] += dp[i - 1][j - k] * ((MOD + powsum[B[i - 1]][k] - powsum[A[i - 1] - 1][k]) % MOD);
				dp[i][j] %= MOD;
			}
		}
	}
 
	cout << dp[N][C] <<; endl;
 
	return 0;
}
スポンサーリンク
レクタングル(大)
レクタングル(大)

シェアする

  • このエントリーをはてなブックマークに追加

フォローする