SRM 572 DIV1 本番

SRM 本番 半分の指数

神回だった

Coding

Easy (250)

こういう系の問題苦手すぎる。
とりあえず(K<=n-K)で場合分け。
(K<=n-K)の時は簡単。対応する文字が違う場合にcostが増加。
さて、問題は(K>n-K)の時。
これは考えると(n-K)ごとのブロックに分かれて、(i

Medium (500)

(サイズ<=9)という制約が目立つ。それをどうにか生かせないか？
これは半分全列挙できる。
半分の桁までを全列挙し、(各guessesでヒットの数 → それを満たす数値、もしくはそれが2つ以上あるというフラグ)というマップを作る。
もう片方も全列挙して、そのマップ[bulls-このヒットの数]を見ればよい。
このヒットの数のSubset-Sumっぽい感じが半分全列挙って感じであると思う。指数の底が2の形とは限らないよな、と。
枝刈り全探索でもうまくやれば通るらしい

Hard (1000)

考えてない

Challenge

Med落ちる人いそうだなーと思って全探索チェッカーを書いた。
でもコードを写してるうちに結構落とされてて、しかも写した人もそのチェッカーでは落ちなかった。
結局何もChellengeしなかった

結果

Easy: 185.23/250
Medium: 334.66/500
Chellenge: 0/0 = +0
Division Place: 20/715
Rating: 1719→1898

コメント

Easyの「同じ文字である必要がある」って同値関係なんだから推移律的に考えてunionFind的になるのはそうだろ！推移的に考えるべき。
Mediumの半分全列挙は一回自分で問題を考えてみたりして身につけたのがよかったと思う。
半分全列挙は、考え方は難しくないけど身につけている人が少ない狙い目問題だと思う。
今回は良かったが、この調子を維持して3月中に赤になりたい

コード

Easy
#include <string>
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define INF 0x3f3f3f3f
using namespace std;

struct NewArenaPassword {
	int minChange(string oldPassword, int K) {
		int n = oldPassword.size();
		if(K <= n - K) {
			int r = 0;
			rep(i, K) if(oldPassword[i] != oldPassword[n-K+i]) r ++;
			return r;
		}else {
			int r = 0, t = n - K;
			rep(i, t) {
				int x = INF;
				rer(c, 'a', 'z') {
					int y = 0;
					for(int j = i; j < n; j += t) {
						y += c != oldPassword[j];
					}
					x = min(x, y);
				}
				r += x;
			}
			return r;
		}
	}
};
Medium
#include <string>
#include <vector>
#include <map>
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
using namespace std;
typedef vector<int> vi;  
typedef long long ll;   
typedef vector<string> vs; 
struct EllysBulls {
	vs g; vi b; int n, m;
	string getNumber(vector <string> guesses, vector <int> bulls) {
		g = guesses, b = bulls, n = g[0].size(), m = g.size();
		map<vector<unsigned char>,int> half;
		static ll pow10[11];
		pow10[0] = 1;
		rer(i, 1, 10) pow10[i] = pow10[i-1] * 10;
		vector<unsigned char> v(m);
		rep(i, pow10[n/2]) {
			static char a[6];
			int x = i;
			rep(j, n/2) a[j] = '0' + x % 10, x /= 10;
			rep(j, m) {
				int q = 0;
				rep(k, n/2) q += a[k] == g[j][n-1-k];
				v[j] = q;
			}
			if(half.count(v)) half[v] = -1;
			else half[v] = i;
		}
		string ans = "";
		rep(i, pow10[n-n/2]) {
			static char a[6];
			int x = i;
			rep(j, n-n/2) a[j] = '0' + x % 10, x /= 10;
			rep(j, m) {
				int q = 0;
				rep(k, n-n/2) q += a[k] == g[j][n-n/2-1-k];
				v[j] = b[j] - q;
			}
			if(!half.count(v)) continue;
			if(half[v] == -1 || !ans.empty()) {
				ans = "A";
				break;
			}else {
				ans.resize(n);
				int y = half[v];
				rep(k, n/2) ans[n-1-k] = '0' + y % 10, y /= 10;
				y = i;
				rep(k, n-n/2) ans[n-n/2-1-k] = '0' + y % 10, y /= 10;
			}
		}
		if(ans.empty()) return "Liar";
		else if(ans == "A") return "Ambiguity";
		else return ans;
	}
};