SRM145 Div.2 250 ImageDithering

こんにちは〜。・・・こんばんわか。

はい。コンピュータ部に入ってきました！
部長さんからは完璧Android開発者としてみられてるようですが、まぁプログラミングコンテストは今までどおり。

見かけ脅し

今回解いた問題は見かけ脅しでした。

大体の意味はなんか指定した色がディスプレイのどのくらいを占めるかみたいなもんだいで、入力も配列でアルファベットだらけのディスプレイ渡されるなんか一見難しそうな問題。

でも実際はサンプル見れば分かるけど、ディスプレイの中に指定の色…というよりもアルファベットがどのくらいディスプレイにあるか数えるだけ。

というわけでこんな感じになります。

class ImageDithering {
	public:
	int count(string dithered, vector <string> screen) {
		int c=0;
		for (int i=0; i<dithered.length(); i++) {
			for (int j=0; j<screen.size(); j++) {
				for (int k=0; k<screen[j].length(); k++) {
					if (dithered[i] == screen[j][k])
					{
						c++;
					}
				}
			}
		}
		return c;
	}
};

簡単ですね。

さて、まぁコレだとあっさりしすぎるので、chokudaiさんのITメディア連載記事から一問(っていってもSRMの過去問だけど。)

A[i]に関して、

i<=0のとき、A[i] = 1
i>0のとき、A[i] = A[i/p-x] + A[i/q-y]
と定義する。n、p、q、x、yが与えられた時、A[n]を求めなさい。
ただし、nは10^13以下、p,qは2以上10^9以下、x、yは0以上10^9以下とします。

メモ化再帰、動的計画法の良質なサンプルだそうで。

…解けましたでしょうか？
僕はわかんなかったよ←

というわけでchokudaiさんの模範解答(もちろんchokudaiさんはC#使いなのでC++に翻訳)

class InfiniteSequence2
{
public:
    long long dp[1000001];
    long long calc(long long n, int p, int q, int x, int y)
    {
		if (n <= 0) { 
			return 1;
		}
		if (n <= 1000000 && dp[n] != 0) { 
			return dp[n];
		}
		long long res = calc(n/p-x, p, q, x, y)+calc(n/q-y, p, q, x, y);
		if (n <= 1000000) { 
			dp[n] = res;
		}
        return res;
    }
};