ABC228 A - On and Off / B - Takahashi's Secret C++解答例
AtCoder Beginner Contest 228 A - On and Off / B - Takahashi's SecretをC++で解きます。
A - On and Off
問題
問題文をAtCoderのページより引用します。
問題文
高橋くんは、毎日
時0分に部屋の電気を付け、毎日 S 時0分に消します。 T
電気をつけている間に日付が変わることもあります。
時30分に部屋の電気がついているかどうか判定してください。 X
制約
0 \leq S, T, X \leq 23 S \neq T - 入力はすべて整数である。
解答例
電気をつけてから消すまでに日付を跨がない場合は簡単なのですが、そうでない場合も考えなければならないので少し難しくなります。
電気がついている時間を数直線で表現してみます。
例えば、入力例1(
図のオレンジ色の領域が、電気がついている時間帯を表しています。この入力例ではYesを出力すればよいことになります。
日付を跨がない場合、
次に、
ある日について考えると、その日のうち電気がついている時間帯は、前日のNoを出力すればよいことになります。
日付を跨ぐとき、
これをまとめると、以下のことが言えます。
-
S < T S \leq X \land X < T Yesとなる。そうでなければNoとなる。 -
S > T T \leq X \land X < S Noとなる。そうでなければYesとなる。
実装例
これをC++で実装すると以下のようなコードになります。
電気がついているかどうかをチェックする時刻が
#include <iostream>
int main() {
int64_t S, T, X;
std::cin >> S >> T >> X;
if (S < T) {
if (S <= X && X < T) {
std::cout << "Yes" << std::endl;
} else {
std::cout << "No" << std::endl;
}
} else {
if (T <= X && X < S) {
std::cout << "No" << std::endl;
} else {
std::cout << "Yes" << std::endl;
}
}
return 0;
}
実際に提出したコードはこちら。
B - Takahashi's Secret
問題
問題文をAtCoderのページより引用します。
問題文
高橋くんには
人の友達がいます。 N 人の友達はそれぞれ、友達1、友達2、 N 、友達 \ldots というあだ名で呼ばれています。 N
ある日、高橋くんはある恥ずかしい秘密を、友達の一人である友達に知られてしまいました。 X
について、友達 i = 1, 2, \ldots, N が高橋くんの秘密を知ったとき、友達 i がまだ高橋くんの秘密を知らなければ、友達 A_i は高橋くんの秘密を友達 i にも教えてしまいます。 A_i
高橋くんの秘密は最終的に何人の友達に知られることになるでしょうか？
制約
2 \leq N \leq 10^5 1 \leq X \leq N 1 \leq A_i \leq N A_i \neq i - 入力はすべて整数
解答例
友達
実装例
コード例を以下に示します。配列は0-indexedで管理することに注意してください。
#include <iostream>
#include <vector>
int main() {
int64_t N, X;
std::cin >> N >> X;
// 0-indexedで管理するためにXをデクリメントしておく
X--;
std::vector<int64_t> A(N);
for (int64_t i = 0; i < N; i++) {
std::cin >> A.at(i);
// 0-indexedにするためにデクリメントしておく
A.at(i)--;
}
// N人の友達が秘密を知っているかどうか管理する配列
std::vector<bool> known(N, false);
// 友達Xは秘密を既に知っている
known.at(X) = true;
// 秘密を知った友達が次に秘密を教えようとする相手
int64_t target = A.at(X);
// 秘密が伝播しなくなるまでループする
while (true) {
// 次に秘密を教えようとする相手が秘密を知らなかった場合
if (known.at(target) == false) {
// その友達に秘密を教える
known.at(target) = true;
// 次のターゲットを決める
target = A.at(target);
} else {
// ターゲットが既に秘密を知っていた場合、ループを終了する
break;
}
}
// 秘密を知っている人数を数える
int64_t answer = 0;
for (int64_t i = 0; i < N; i++) {
if (known.at(i)) {
answer++;
}
}
// 答えの出力
std::cout << answer << std::endl;
return 0;
}
実際に提出したコードはこちら。
Discussion