🧭

ABC228 A - On and Off / B - Takahashi's Secret C++解答例

2021/11/21に公開約3,400字

AtCoder Beginner Contest 228 A - On and Off / B - Takahashi's SecretをC++で解きます。

A - On and Off

問題

問題文をAtCoderのページより引用します。

問題文

高橋くんは、毎日S時0分に部屋の電気を付け、毎日T時0分に消します。
電気をつけている間に日付が変わることもあります。

X時30分に部屋の電気がついているかどうか判定してください。

制約

  • 0 \leq S, T, X \leq 23
  • S \neq T
  • 入力はすべて整数である。

解答例

電気をつけてから消すまでに日付を跨がない場合は簡単なのですが、そうでない場合も考えなければならないので少し難しくなります。

電気がついている時間を数直線で表現してみます。
例えば、入力例1(S = 7, T = 20, X = 12)は以下のような図になります。

図のオレンジ色の領域が、電気がついている時間帯を表しています。この入力例ではXが電気のついている時間帯の中にあるため、Yesを出力すればよいことになります。
日付を跨がない場合、S < Tが成り立つことがわかります。

次に、S時からT時までの間に日付を跨ぐ場合を考えます。入力例2(S = 20, T = 7, X = 12)を図で表してみます。

ある日について考えると、その日のうち電気がついている時間帯は、前日のS時からその日のT時までと、その日のS時から翌日のT時まで、ということになります。ここでのXは電気がついている時間帯に無いので、Noを出力すればよいことになります。
日付を跨ぐとき、S > Tとなっていることがわかります。

これをまとめると、以下のことが言えます。

  • S < Tのとき、S \leq X \land X < Tが成り立っていればYesとなる。そうでなければNoとなる。
  • S > Tのとき、T \leq X \land X < Sが成り立っていればNoとなる。そうでなければYesとなる。

実装例

これをC++で実装すると以下のようなコードになります。
電気がついているかどうかをチェックする時刻がX時30分であることに注意して判定式を作ります。

a.cpp
#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人の友達がいます。N人の友達はそれぞれ、友達1、友達2、\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
  • 入力はすべて整数

解答例

友達Xから秘密が伝わっていく様子をシミュレーションして解きます。
N人の友達について、秘密を知っているかどうかを配列で管理しておき、それ以上秘密が伝播しなくなるまでシミュレートし続ければよいでしょう。

実装例

コード例を以下に示します。配列は0-indexedで管理することに注意してください。

b.cpp
#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

ログインするとコメントできます