夢追い人

"It takes a dreamer to make a dream come true."―Vincent Willem van Gogh

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]に関して、
  1. i<=0のとき、A[i] = 1
  2. 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;
    }
};

さて、このコードから学んでほしいことは…

  • メモ化再帰は速い
  • メモ化再帰はメモリを大量消費する
  • ただ単に使うのではなく、「同じ計算をやる無駄を省いている」という本質を知って最も効率的な方法で使う

ということです。

では、明日は健康診断なので欲張って二問ぐらいとこうかな。。。
多分Easyばっかになると思いますが、しばらくはこう言うことで。


それでは(^^)ノシ

広告を非表示にする