SRM 387 300pt: MarblesRegroupingEasy

TopCoder

問題概要

N(<50)個の箱がある。各箱には種類i(0<=i

考えたこと

  • とりあえずJokerをどれにするか全探索する方針が見える。
  • Jokerを固定したときの移動回数をどうやって求める？
  • 1種類しか無いときは基本的に動かさなくてよくて、それ以外の時は全部Jokerに放り込む。
  • ただし1種類しかないときも、それと同じ種類の箱が既にある時は移動しなければならない。
  • っていうかこれ数は関係ないよね。
  • 後は実装するだけなんだけど、妙に読みづらいコードになってしまった。
  • 提出したけど自信がない。でも一応大丈夫そうなので再提出はしない。
  • 無事通ってた。こういうのもっとスマートに書きたい。

practiceで通ったコード

計算量O(N^2 * (log N + M))。

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

const int INF = 1<<29;

struct MarblesRegroupingEasy {

	int minMoves(vector <string> boxes) {
		const int N = boxes.size(), M = boxes[0].length();
		int ret = INF;

		//どれがJokerか全探索
		for(int joker=0; joker<N; joker++){
			set<int> ns;
			int cnt = 0;
			for(int i=0; i<N; i++)if(joker != i){
				int dig_cnt = 0, key = -1;
				for(int j=0; j<M; j++)if(boxes[i][j] != '0'){
					dig_cnt++;
					key = j;
				}
				if(dig_cnt > 1){
					cnt++;
				}
				else if(dig_cnt == 1){
					if(ns.find(key) != ns.end()){
						cnt++;
					}
					ns.insert(key);
				}
			}
			ret = min(ret, cnt);
		}

		return ret;
	}

};