CSAcademy Round #21 問題と解説 - はまやんはまやんはまやん

問題

Min Coin Payment

https://csacademy.com/contest/round-21/#task/min-coin-payment
無限の1,5,50ドルがある。
これを使ってKドルを最小個数で作れ。

Prime Distance

https://csacademy.com/contest/round-21/#task/prime-distance
ある数Aに以下のどちらかの操作をする。
1. Aに素数を掛ける
2. Aから素数を割る
最小何回の操作でBにできるか

Max Wave Array

https://csacademy.com/contest/round-21/#task/max-wave-array
全ての要素が異なる数列Aがある。
これをA[1] > A[2] < A[3] > A[4] < ...のような規則で並べるとき、辞書順最大のものを答えよ

0-K Multiple

https://csacademy.com/contest/round-21/#task/0-k-multiple
ある数Nの倍数で全ての桁の数がKか0である最小の数を答えよ。

Special MVC

https://csacademy.com/contest/round-21/#task/special-mvc
N頂点M辺の無向グラフがある。
このグラフには奇数長の閉路しかない。
このグラフの最小頂点被覆数を求めよ。
最小頂点被覆 : 頂点の部分集合で全ての辺の端点のどちらかが必ずその集合に属す

Tournament Cycle

https://csacademy.com/contest/round-21/#task/tournament-cycle
N頂点のtournament graphのうち、長さKの閉路が少なくとも1つ含まれる個数を求めよ。
tournament graph : 完全グラフを有向グラフにしたもの

Catch the Thief

https://csacademy.com/contest/round-21/#task/catch-the-thief
N頂点M辺の無向グラフがある。
泥棒は

初期頂点は分からない
毎晩、隣接する頂点に移動する

自分は

毎日夜まで任意の頂点で張り込みをする

どのような順番で張り込みを行えば捕まえられるか、張り込みをする頂点の順番を答えよ。
必ず捕まえられないなら"-1"

以下、解説

解説

Min Coint Payment

金額が大きいものから順に使っていく

int K;
int main() {
	cin >> K;

	int ans = 0;
	ans += K / 50;
	K %= 50;
	ans += K / 5;
	K %= 5;
	ans += K;
	cout << ans << endl;
}

Prime Distance

どちらも素因数分解をして、素因数の個数の差の総和が答えとなる。

typedef long long ll;
map<ll, int> enumpr(ll n) {
	map<ll, int> V;
	for (ll i = 2; i*i <= n; i++) while (n%i == 0) V[i]++, n /= i;
	if (n>1) V[n]++;
	return V;
}
ll A, B;
//-----------------------------------------------------------------------------------
int main() {
	cin >> A >> B;

	auto a = enumpr(A);
	auto b = enumpr(B);

	set<ll> pr;
	for (auto p : a) pr.insert(p.first);
	for (auto p : b) pr.insert(p.first);

	int ans = 0;
	for (ll p : pr) ans += abs(a[p] - b[p]);
	cout << ans << endl;
}

Max Wave Array

まず実験する

123456789を並べるときは、
9________
9_8______
978______
978_6____
97856____
97856_4__
9785634__
978563412

123456を並べるときは
6_____
6_5___
645___
645_3_
64523_
645231

これを見ると、

最初は最大の数
その次は(3番目)(2番目)->(5番目)(4番目)のように2要素毎にswapしてある

なので、降順ソートをして2要素ごとにswapすれば答え

int N, A[101010];
//-----------------------------------------------------------------------------------
int main() {
	cin >> N;
	rep(i, 0, N) scanf("%d", &A[i]);
	sort(A, A + N, greater<int>());

	for (int i = 1; i+1 < N; i += 2) swap(A[i], A[i + 1]);

	rep(i, 0, N) {
		printf("%d", A[i]);
		if (i != N - 1) printf(" ");
	}
	printf("\n");
}