kojingharangの日記

SRM 593 Div1 500 BitwiseAnd

09:50 |

• Nと、N以下の要素を持つlong long配列Sが与えられる。
• S に必要ならいくつか要素を追加して、(1)任意の2組のAND＞0, (2)任意の3組のAND==0, (3)数値は1以上2^60-1以内, になるような辞書順最小の配列を求めよ。
• 3≦N≦50, 1≦S[i]≦2^60-1

• ビット表現にして配列を各行に書いてくと...
• 各列に1がちょうど2個あって、任意のi, jにたいして行iと行jが連結(どちらも1の列がある)してればOK
• 連結状態を行列で管理してみる
• すでに3つ以上あるときはだめ
• 追加する数字に関しては、
• すべての列に対して、縦に見て1の数を数えて、1個なら連結じゃないので連結できそうな行を見つけて1を書いていく
• 連結じゃないときは全ての列が0であるとこを探して無理やり1を2つ書いて連結にする
• でいいと思われる

001100011  //99
010011101  //157
?????????
?????????

001100011  //99
010011101  //157
100000110  //262
100101000  //296

Returns: {99, 157, 262, 296 }

• バグりまくる

• 終了

• 書いた
• サンプルの{}, 5が合わない
• 紙に書いて分析。辞書順最小になってない。
• 連結じゃないときに無理やり追加するのは毎回じゃなくて最後に1回だけにしないと辞書順最小にならないようだ
• いろいろ証明できてなくてもやもやしてるけどpracticeで通った

• ↓あとで(accepted in practice room)

class BitwiseAnd {
	public:
	ll add;
	VVI w;
	int N, M;
	VI S;
	bool check(bool init) {
		REP(bit, 60) {
			VI one;
			REP(i, S.size()) {
				if((S[i]>>bit)&1) one.PB(i);
			}
			if(one.size()>2) return false;
			if(one.size()==2) w[one[1]][one[0]] = w[one[0]][one[1]] = 1;
			if(!init && one.size()==1 && w[one[0]][S.size()]==0) {
				add |= 1LL<<bit;
				w[one[0]][S.size()] = w[S.size()][one[0]] = 1;
			}
		}
		if(!init) {
			S.PB(add);
		}
		REP(i, S.size()) REP(j, S.size()) {
			if(i!=j && w[i][j]==0) {
				if(init) {
					return false;
				}
			}
		}
		return true;
	}
	vector<long long> lexSmallest(vector<long long> _S, int N) {
		S=_S;
		M=S.size();
		w = VVI(N, VI(N));
		if(!check(true)) return vector<ll>();
		while(S.size()<N) {
			add=0;
			if(!check(false)) return vector<ll>();
		}
		REP(i, S.size()) REP(j, S.size()) {
			if(i!=j && w[i][j]==0) {
				if(i<M || j<M) continue;
				bool ok=false;
				REP(bit, 60) {
					bool lok=true;
					REP(k, S.size()) if((S[k]>>bit)&1) lok=false;
					if(lok) {
						ll a = 1LL<<bit;
						S[i] |= a;
						S[j] |= a;
						w[i][j]=w[j][i]=1;
						ok=true;
					}
					if(ok) break;
				}
			}
		}
		if(!check(true)) return vector<ll>();
		sort(ALL(S));
		return S;
	}
};

ツイートする