SRM 542 500pt : StrangeDictionary2

TopCoder

問題概要

長さL(<50)の文字列がN(≦16)個ある。各文字列の順序をある置換σを適当に選んで置換する。このとき、各文字列について先頭にくる確率を求める問題。文字列はどれも互いに異なる。

考えたことなど

  • (easyが酷い点数で残り時間も少なく、焦った状態で問題を開いた。いつもはDivision Summary見てから問題開くのに今回は余裕がなくて忘れていた)
  • (問題を下から眺める。確率か。しかも複数求めるやつだしどうせDPだろう)。
  • 問題文を読んだ。これも題意が実にわかりやすい。
  • これ文字列どれか同じものが入る場合あるのかな。そうだとしたら撃墜ポイントの予感。
  • 制約見たら全部違うと書いてあった。残念…。
  • 文字列の数が16で文字列長が50か。逆なら良かったのに…。
  • とりあえず電卓で2^16 * 50 * 16とかを計算する。何かこれっぽいな…。
  • とりあえずどう見てもbit DPな制約なので、素直に状態をdp[i][bit]={bitが残っている文字列で、iが先頭にくる確率}とする。
  • 後は残っている文字列の中で最小になっているポジションを選んで減らしていけば答え出そう？
  • え、こんな簡単でいいのか？ああ毎回計算するのは重いから前処理する必要はあるな。とはいえほんとにこんな簡単なのでいいの？
  • この状態のとり方だと各i毎にdpを独立にやることになるのでちょっと頭悪い感はあるけど、しかしそれで十分間に合うよね？
  • よし、書き始めよう。
  • 前処理の部分あまり詳しく考えないまま書き始めてしまったけど、何とか行けそうな気がする。
  • 書けた。コンパイルが一発で通ってサンプルも全部通ってむしろ疑心暗鬼になった。
  • まあこんなこともあるか、とポジティブに考え直して提出。
  • 最大ケースをテストする。セグフォ。うおーー。
  • 文字列の長さ16って書いてた。ひどい。修正して再提出。
  • 一応最大らしいケースが1.3secとかだったのでTLEに関して若干不安感はあるものの、チェックリストで調べた限り他は大丈夫そうな気配。
  • テストケースをいくつか試して定性的には正しそうな振る舞いをしていることを確認。
  • 前処理せずに書いてる人がいるかもしれないので枝刈り効きにくい最大ケースとランダムケースを準備してチャレンジフェーズを待つ。
  • (以下はコンテスト終了後に考えたこと)
  • 個人的にはメモ化一択な感じだと思っていたけど、普通にループのDPで書いていた人もたくさんいて、むしろ上位陣はループの方が多かった印象すらある。
  • 前処理とかせずにビットのループを回しながらその中で複合的にいろんなことやっている人も多かったけど、自分は問題分離したほうが混乱しないので分離できるときはなるべく分離するようにしている。
  • よくあるのが素数関連の問題で、篩をしながら同時に別の処理で答を求める、みたいなやり方する人がいるけど、自分がそれを真似したら確実に混乱する。自分の場合はまず篩をやってからそれから改めてループを回す、みたいな書き方をすることが多いし、それで困ったことは特にないのでこれからもそうすると思う。コードが長くなりがちなのは欠点だけど。
  • 実際、今回通ったコードも他の人に比べると結構長い。でも長さの割に書いてるときはそんな手間取ることはなかった。メモ化の部分はほとんど定型だし。

acceptされたコード

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

const int MAX_W = 50;
const int MAX_N = 16;

int N, L;
vector<string> words;

char firsts[1<<MAX_N][MAX_W];
bool all_same[1<<MAX_N][MAX_W];
int counts[1<<MAX_N];
int to_bit[1<<MAX_N][MAX_W];

double memo[MAX_N][1<<MAX_N];
double visited[MAX_N][1<<MAX_N];

struct StrangeDictionary2 {

	vector <double> getProbabilities(vector <string> words_) {
		words = words_;
		N = words.size();
		L = words[0].length();

		memset(firsts, 'z', sizeof(firsts));

		for(int bit=0; bit<1<<N; ++bit){
			for(int i=0; i<L; ++i){
				for(int j=0; j<N; ++j)if( (bit>>j)&1 ){
					firsts[bit][i] = min(firsts[bit][i], words[j][i]);
				}
				bool same = true;
				for(int j=0; j<N; ++j)if( (bit>>j)&1 ){
					same &= firsts[bit][i] == words[j][i];
				}
				all_same[bit][i] = same;

				to_bit[bit][i] = bit;
				for(int j=0; j<N; ++j)if( (bit>>j)&1 ){
					if(firsts[bit][i] != words[j][i]){
						to_bit[bit][i] &= ~(1<<j);
					}
				}
			}
		}

		for(int bit=0; bit<1<<N; ++bit){
			for(int i=0; i<L; ++i)if(!all_same[bit][i]){
				++counts[bit];
			}
		}


		vector<double> ret(N);

		for(int i=0; i<N; ++i){
			ret[i] = rec(i, (1<<N)-1);
		}
		return ret;
	}

	double rec(int v, int bit){
		if(visited[v][bit]){
			return memo[v][bit];
		}
		visited[v][bit] = true;

		double& ret = memo[v][bit];
		ret = 0.0;

		if( !((bit>>v)&1) ){
			return ret = 0.0;
		}

		if(__builtin_popcount(bit) == 1){
			return ret = 1.0;
		}

		for(int i=0; i<L; ++i)if(!all_same[bit][i]){
			ret += rec(v, to_bit[bit][i]) / (double)counts[bit];
		}

		return ret;
	}

};