SRM571 Div1 Easy - FoxAndMp3

問題

mp3プレイヤーにn曲の曲が入っており、i曲目の名前は "i.mp3" である
このプレイヤーは曲名を数字の昇順ではなく文字列の昇順にソートする
このプレイヤーの表示順に、
1) n<=50のときは全曲の曲名
2) そうでないときは最初の50曲の曲名
を書け

1 <= n <= 10^9

解法

2桁以下は全部試す
3桁以上は先頭50個だけ試せば十分
それでも1万文字も行かないから計算量もメモリも大丈夫

class FoxAndMp3 {
public:
	vector<string> playList(int n) {
		vector<string> res, x;
		reps(i,1,min(n,99)+1) x.push_back(to_string(i) + ".mp3");
		ll t = 100;
		rep(d,10) {
			rep(i,55) if (t+i<=n) x.push_back(to_string(t+i) + ".mp3");
			t *= 10;
		}
		sort(all(x));
		rep(i,min(n,50)) res.push_back(x[i]);
		return res;
	}
};

https://community.topcoder.com/stat?c=problem_statement&pm=12436&rd=15491

SRM570 Div1 Easy - RobotHerb

問題

無限に広いグリッド上にロボットがいる
長さnのプログラムが組み込まれており、i番目は「正面にa[i]マス進んでからa[i]*90度右に回れ」という内容
このプログラムをt回実行した後に辿り着くマスと最初にいたマスのマンハッタン距離を求めよ

1 <= n <= 50
1 <= a[i] <= 10^7
1 <= t <= 10^9

解法

プログラム実行時の向きによってプログラム実行による座標の変化が変わってくるから、単純にプログラムを1回実行したときの座標変化をt倍するだけではダメ

最初の向きを上方向だとする
プログラムを1回実行し終わった時点での向きが上方向なら1回、下なら2回、左右なら4回、それぞれプログラムを実行すると向きが元に戻る
つまり4回プログラムを実行すれば必ず元の向きに戻る
よってプログラムを4回セットにしたものをfloor(t/4)回実行して、残りt%4回は普通にシミュレーションすればok

class RobotHerb {
public:
	ll getdist(int t, vector<int> a) {
		ll x = 0, y = 0, dir = 0;
		rep(k,4) each(i,a){
			x += dx[dir]*i, y += dy[dir]*i;
			(dir += i) %= 4;
		}
		x *= t/4, y *= t/4;
		rep(k,t%4) each(i,a) {
			x += dx[dir]*i, y += dy[dir]*i;
			(dir += i) %= 4;
		}
		return abs(x) + abs(y);
	}
};

https://community.topcoder.com/stat?c=problem_statement&pm=12427&rd=15490

SRM569 Div1 Easy - TheDevice

ちょっと面白かった

問題

長さmのビット列がn個ある
これらのうち2個を選んで機械に入れると、各ビットごとにそれらのor / and / xor和のどれかを計算して出してくれる
この機械の各ビットがor / and / xor和のどれを出しているのか特定したい
今あるn個のビット列だけで特定できないこともある
特定するために追加する必要のあるビット列の個数の最小値を求めよ

1 <= n <= 50
1 <= m <= 50

解法

01 -> 0ならand, 1ならorかxor
11 -> 0ならxor, 1ならorかand
というように特定できるから、試す必要のあるビットの組み合わせはこの2通り
よってiビット目を特定するために
・iビット目が0の列が最低1個
・iビット目が1の列が最低2個
これだけ必要になる
ビットごとに足りない列の個数を求め、それらの最大値が答えになる

class TheDevice {
public:
	int minimumAdditional(vector<string> s) {
		int n = s.size(), m = s[0].size(), x[55] = {}, y[55] = {};
		rep(i,n) rep(j,m) (s[i][j]=='0' ? x : y)[j]++;
		int res = 0;
		rep(i,m) chmax(res, max(1-x[i],0) + max(2-y[i],0));
		return res;
	}
};

https://community.topcoder.com/stat?c=problem_statement&pm=12388&rd=15489

SRM568 Div1 Easy - BallsSeparating

問題

n個の箱があり、i番目の箱には赤緑青のボールがそれぞれr,g,b[i]個入っている
ある箱からある色のボールを取り出し違う箱に入れるにはコストが1かかる
それぞれの箱に入っているボールの色の種類を1以下にするためにかかるコストの最小値を求めよ

1 <= n <= 50
1 <= r, g, b[i] <= 10^6

解法

赤緑青それぞれのボールを集める箱(i,j,kとする)を全探索する
箱i,j,kに関しては対応しない2種類の色のボールの個数だけコストがかかる
それ以外の箱については最も個数が多い色のボールだけ残して、その他の2色のボールだけ移動すればいい

class BallsSeparating {
public:
	int minOperations(vector<int> r, vector<int> g, vector<int> b) {
		int n = r.size(), res = 1<<30;
		if (n<3) return -1;
		rep(i,n) rep(j,n) rep(k,n) if (i!=j && j!=k && k!=i) {
			int s = 0;
			rep(x,n) {
				if (x==i) s += g[x]+b[x];
				else if (x==j) s += b[x]+r[x];
				else if (x==k) s += r[x]+g[x];
				else s += r[x]+g[x]+b[x] - max(r[x],max(g[x],b[x]));
			}
			chmin(res,s);
		}
		return res;
	}
};

https://community.topcoder.com/stat?c=problem_statement&pm=12398&rd=15488

SRM567 Div1 Easy - TheSquareRootDilemma

問題

整数n,mが与えられる
a,bがn,m以下かつ (√a + √b)^2が整数になるような正整数のペア(a,b)の個数を求めよ

1 <= n, m <= 77777

解法

(√a + √b)^2
= a+b + 2√ab
だからabが平方数ならok

aを全部試す
aを平方数で割れるだけ割った結果をa'とする
するとこのaとペアにできるbの条件は、b = a' * (平方数) であることになる
これはb = i * (平方数) という形で表せるm以下のbの個数をiごとに事前計算しておけばO(1)で求められる

class TheSquareRootDilemma {
public:
	int countPairs(int n, int m) {
		int b[100100] = {};
		reps(i,1,m+1) reps(j,1,1001) {
			if (j*j*i<=m) b[i]++;
			else break;
		}
		int res = 0;
		reps(i,1,n+1) {
			int a = i;
			for (int j=2; j*j<=a; j++) while (a%(j*j)==0) a /= j*j;
			res += b[a];
		}
		return res;
	}
};

https://community.topcoder.com/stat?c=problem_statement&pm=12377&rd=15487

SRM566 Div1 Easy - PenguinSledding

問題

n頂点m辺の無向グラフが与えられる
グラフがどんな形になっていても絶対に辺同士が交差しないように辺を削除するとき、最終的なグラフとしてあり得るものは何通りあるか

2 <= n <= 50
1 <= m <= 50

解法

最終的なグラフは
1) 辺が1本もない
2) 辺が1本だけある
3) 辺が2本以上あり、全ての辺が同じ頂点から伸びている
4) 辺が3本あり、それらが三角形になっている
という4パターンに分けられる
それぞれ計算して足し合わせればok

class PenguinSledding {
public:
	ll countDesigns(int n, vector<int> x, vector<int> y) {
		ll m = x.size(), e[55] = {}, res = m+1;
		rep(i,m) e[x[i]-1]++, e[y[i]-1]++;
		rep(i,n) if (e[i]>=2) res += (1ll<<e[i]) - (e[i]+1);
		int t[55][55] = {};
		rep(i,m) t[x[i]-1][y[i]-1] = t[y[i]-1][x[i]-1] = 1;
		rep(i,n) reps(j,i+1,n) reps(k,j+1,n)
			if (t[i][j] && t[j][k] && t[k][i]) res++;
		return res;
	}
};

https://community.topcoder.com/stat?c=problem_statement&pm=12336&rd=15486

SRM565 Div1 Easy - MonstersValley

問題

マナオは一人で旅に出た
道中で出会うモンスターはn匹いて、i番目に出会うモンスターの怖さはd[i]で、仲間にするにはp[i]円かかる
モンスターに出会ったとき、金を払って仲間にするという選択肢が常にある
またはマナオのチームの怖さの合計がそのモンスターの怖さ以上であれば、無視してやり過ごすこともできる
そうでないときはモンスターはマナオを襲う
モンスターに襲われずに旅を終えるために必要な金の最小値を求めよ

1 <= n <= 50
1 <= d[i] <= 10^12
p[i] = 1 or 2

解法

dp[i][j]: i番目のモンスターと遭遇し終えた時点でj円使った場合のチームの怖さの合計の最大値

class MonstersValley {
public:
	int minimumPrice(vector<ll> d, vector<int> p) {
		ll n = d.size(), dp[55][111] = {};
		memset(dp, -1, sizeof(dp));
		dp[0][0] = 0;
		rep(i,n) rep(j,111) if (dp[i][j]!=-1) {
			chmax(dp[i+1][j+p[i]], dp[i][j] + d[i]);
			if (d[i]<=dp[i][j]) chmax(dp[i+1][j], dp[i][j]);
		}
		rep(i,111) if (dp[n][i]!=-1) return i;
		return -1;
	}
};

https://community.topcoder.com/stat?c=problem_statement&pm=12350&rd=15187