PI(円周率を覚える)

(ソース)https://algospot.com/judge/problem/read/PI

完全ナビゲーションの場合:

問題として入力できる数字文字列の最大長は1万個で、前から3個、4個、5個の計3つの選択肢の中から1つを選択し、数字がすべて分割されるまで繰り返す.したがって,できるだけ少なく見積もっても3^2000個を超える.これでは完全に探求で問題を解決することはできず、別の方法を考えなければならない.

注釈

そこで,1万個の数値の各要素に,その要素から作成できる最小難易度値をキャッシュして答えを求めることを考えた.

Cache[index]=min(3難易度+cache[index+3]、4難易度+cache[index+4]、5難易度+cache[index+5])

上記の場合,一部の問題は合計1万個発生し,各部分の問題は定数時間の計算時間しか必要としないため,O(N)の時間的複雑さだけで解決できる.

コード#コード#

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <string>
#include <string.h>

using namespace std;
string num;
int cache[10000];
int INF = numeric_limits<int>::max() - 100000;

int cal_difficulty(string num) {
	int differ_before = (int) num[1] - (int) num[0] ;
	int first = (int) num[0] - 48;
	bool sequence = true;
	bool alter = true;

	for (int i = 1; i < num.size() - 1; i++) {
		int current = (int) num[i] - 48;
		int next = (int) num[i + 1] - 48;
		int differ_current = next - current;

		if (differ_before != differ_current) {
			sequence = false;
		}
		if (first != next) alter = false;
		differ_before = differ_current;
		first = current;
	}

	if (sequence) {
		if (differ_before == 0) return 1;
		else if (differ_before == -1 || differ_before == 1) return 2;
		else return 5;
	}
	if (alter) return 4;

	return 10;
}

int pi(int index) {
	//예외처리
	if (index == num.size()) return 0;
	if (index > num.size() - 3) return INF;
	
	//메모이제이션
	int& ret = cache[index];
	if (ret < INF) return ret;
	
	ret = min(cal_difficulty(num.substr(index, 4)) + pi(index + 4), cal_difficulty(num.substr(index, 3)) + pi(index + 3));
	ret = min(ret, cal_difficulty(num.substr(index, 5)) + pi(index + 5));

	return ret;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int testcase;
	cin >> testcase;
	while (testcase--) {
		cin >> num;
		fill_n(cache, 10000, INF);
		int ret = pi(0);
		cout << ret << "\n";
	}
	return 0;
}

覚えたいこと

これまでMemset関数の初期化にはmemset関数が用いられていた.そこで今回の問題ではmemsetを用いて配列を初期化しようとしたが,私が渡した値ではなく奇妙な値で配列を初期化する現象がしばしば発生した.
そこで理由を調べてみると、memset関数は1バイト単位で遮断され、各バイトが私が覚えている値を上書きし、パラメータとしてメモリアドレスに渡されるようにしている関数であることがわかりました.
以前は問題を解くときに常に-1初期化値を使用していたため、すべてのメモリアドレスを1バイト単位で-1で埋め込んでも、最終的には配列に-1が残るため、通常の初期化のように見えます.今回はmemsetで非−1の整数を初期化するので,問題は表面に露呈する.
そこで,今回は速度は遅いが,値を正確に初期化できるfill関数を用いた.
今回の問題は簡単で、実施面でも面白い要素があるので、興味深い問題を解決しているようです.