SRM 404 250pt: RevealTriangle

TopCoder

問題概要

二次元配列A[i][j]が与えられる。A.length=N(<50), A[i].length=N-i。各A[i]はどれか一つの要素が固定されていてそれ以外は未定である。A[i][j] = (A[i-1][j] + A[i-1][j+1])%10となるように全ての要素を埋める問題。

考えたこと

  • これ必ず解がユニークに存在するのか？
  • 下から復元できるからユニークに復元できる。そしてそれが分かればその通りに実装すればよい。
  • updateを検出する書き方で書いたけど、左から右に舐めた後右から左に舐めればかならずその行は完全に復元できるのでちょっと実装が賢くなかった。

practiceで通ったコード

計算量O(N^2)。

#include <vector>
#include <string>
#include <algorithm>
using namespace std;

struct RevealTriangle {

	vector <string> calcTriangle(vector <string> a) {
		vector<string> ans = a;
		const int N = a.size();

		for(int i=N-2; i>=0; i--){
			for(;;){
				for(int j=0; j+1<(int)ans[i].length(); j++)if(ans[i][j] == '?' && ans[i][j+1] != '?'){
					ans[i][j] = ans[i+1][j] - ans[i][j+1] + '0';
					if(ans[i][j] < '0'){
						ans[i][j] += 10;
					}
				}

				for(int j=(int)ans[i].length() - 1; j>0; j--)if(ans[i][j] == '?' && ans[i][j-1] != '?'){
					ans[i][j] = ans[i+1][j-1] - ans[i][j-1] + '0';
					if(ans[i][j] < '0'){
						ans[i][j] += 10;
					}
				}

				if(count(ans[i].begin(), ans[i].end(), '?') == 0){
					break;
				}
			}
		}

		return ans;
	}

};