ABC118-ABCを解いた - zxc_programmingのブログ

　最近はうまくいかないこととか頑張り切れないことも多い中、
レートを維持どころか上昇させられたのは大変うれしい。
　Dはやっぱまだわからん。AからCまで自分なりの解き方を以下に示す。
　今回はすべてC++で解いた。

　A : 約数ってなんだっけ？から確認しなきゃならなかったけど、
サンプル見たらわかった。
　ある数を割り切る数のことらしいな。
　A問題は短く書いてしまいたいので条件演算子が有用。

　解き方：問題文の通りに実装すれば良い。

#include<iostream>
int main() {
	int a, b;
	std::cin >> a >> b;

	std::cout << (b%a == 0 ? a + b : b - a) << "\n";
	return 0;
}

B - Foods Loved by Everyone
　B : あんまり似たものはBで出ない気がする。
Kの意味が分からなくて何度か文章とサンプルを行き来した。
（入力のルールを見る限り、i番目の人間の回答の数、つまりi番目の入力の数らしい。）

　解き方：食べ物ごとに何回好きと言われたかカウントする。
N人全員が好きだと答えたのならば、ある食べ物が好きと言われた数はN回であるはずだ。
したがって、食べ物のカウントがちょうどNであるものの数を出力すれば良い。
　（他の実装では、boolかstd::bitsetあたりを使って一度でも選ばれなかったらfalseにして、　 trueの数を数えるのもありかもしれない。）

#include<iostream>
#include<algorithm>

int main() {
	int n, m;
	std::cin >> n >> m;

	int food[30]{};  //[1,30] = [0,29] = [0,30)

	for (int i{}; i < n; ++i) {
		int k{};
		std::cin >> k;
		
		for (int ki{}; ki < k; ++ki) {
			int t;
			std::cin >> t;
			food[t-1]++;
		}
	}
	/*
	for (const auto&e : food) {
		std::cout << " " << e;
	}std::cout << "\n";
	*/
	auto ans = std::count(std::begin(food), std::end(food), n);

	std::cout << ans << "\n";

	return 0;
}

C - Monsters Battle Royale
　C : 難しかった。
　ACはできたけれど証明して提出したわけではないので、
あまりいい回答ではないのかもしれない。
公約数だったかを求めるやつとか使えそうって思ったけど直接は使わない実装にした。
　結構ぐだぐだなので読み飛ばしてコードを見るほうがいいかもしれない。
　ちなみに今回載せる回答は提出後により良いコードに書き直したものだ。

解き方：
　まず入力される数列 Ai ( 1 <= i <= N ) の順序は
結果に影響を与えないっぽいのでソートしても良いだろう。
　次に Ax と Ay ( x != y かつ 0 < Ax < Ay とする ) の2体のモンスターが戦うことを考える。
愚直に問題文のとおりに書いてしまうとwhileで減算(a)とかになるだろうけど、
そこで得られる結果は %(b) の結果と同じだろう。(一応疑似コード載せるけどいらないかも。)

//疑似コード
//(a)
while( Ay > Ax )
  Ay -= Ax
  
//(b)
Ay %= Ax // 右のように書いてもいい==>  Ay = Ay % Ax

　他にも解くのに色々考えたのだけれど上手に説明できない。
ので列挙する。

数列 Ai に 1 が（戦闘が進んで一度でも）現れたら答えは1
そうでないならAi %= Ax ( i != x ) を繰り返した0ではない最小値が答え
ではどのようにAxを選ぶのが良いのか?
（選び方によっては
<i>結果が同じでも計算コストが増える
<ii>結果が変わる
　ことはないのか？）

<i >A%Bした結果は[0, B-1]になるので、Bが小さい方が解も早く収束しそう？
<ii>については分からなかった。反例も思いつかなかった。
上記2点が弱い部分で、可能であれば証明か反例どちらかを成し遂げて
実装を決められたら良かったのだろう。

効率を考えて、除算する数は最小値 Aminにした。
以下コード。
　大事な部分？は余りが0の時は要素 *itk を余りではなく最小値に書き換えているところ。
最小値に書き換えれば重複するので、次のuniqueで間違いなく消えてくれる。　
　余りが0の場合でも余りで書き換えてしまうと次のループで0除算が起きるようになって面倒。　
(コンテスト中の提出はこっちで通した)

#include<iostream>
#include<vector>
#include<algorithm>

int main() {

	int n;
	std::cin >> n;

	std::vector<int> v;
	v.resize(n);

	for (auto&e : v)
		std::cin >> e;
			

	std::sort(std::begin(v), std::end(v));

	auto it = std::unique(std::begin(v), std::end(v));

	while (std::distance(std::begin(v), it) != 1) {
		auto beg = std::begin(v);

		for (auto itk = ++std::begin(v); itk != it; ++itk) {
				*itk = *itk % *beg == 0 ?*beg : *itk % *beg;
		}
		std::sort(std::begin(v), it);
		it = std::unique(std::begin(v), it);
	}
	
	std::cout << v[0] << "\n";

	return 0;
}

(　何度もソートとuniqueするのは計算コスト的に如何なものか、
と実装しながら考えたが、まぁ一応ACする程度には早いらしい。
　「まぁ最初の数回は大きなコストを支払うかもしれないけれど、
最小値が小さくなるほど重複する要素が増えて、
この次に計算の対象になる要素数が大きく減るんじゃなかろうか」
みたいな感覚はあったけれど、実際どうなのだろう。)