ABC065 B問題 解法

6月からAtCoderのC++入門に取り組みはじめたにくうさぎちゃんです。
社会人、数学とか久しぶりすぎて頭が固くなってて、びっくりしています。
数学はできなくなくてもいいと思うけど、頭は柔らかいに越したことはないですよね。😅

今日はこれについて。

C++入門 AtCoder Programming Guide for beginners (APG4b)で紹介されていたので取り組んだところ、TLEや、WAが出て、何度かトライしていたので復習。

1回目はタイムアウトしていた。

// 1回目のコード TLE
#include <bits/stdc++.h>
using namespace std;

int main() {
  int n;
  cin >> n;
  vector<int> arrA(n);
  
  for (int i=0; i<n; i++) {
    cin >> arrA.at(i);
  }
  
  int i = 0;
  int y = 0;
  
  while (true) {
    int x = arrA.at(y);
    i++;
    if (x == 2) {
      cout << i << endl;
      break;
    } else if (x == 1) {
      cout << -1 << endl;
      break;
    } else {
      y = x-1;
    }
  }
}

ケース01.txt, 02.txt, 03.txt　でTLEが出ていた。

ボタン2が押されないパターンについて、
入力例2, 出力例2 に記載されている
「押すボタンがループしているパターン」だけを考えていた。

しかし、この時にケースの考慮漏れに気づいていればよかったが気づいておらず、
タイムアウトしちゃった〜ぐらいの感覚だったので、
「押すボタンがループしているパターン」がタイムアウトしないように下記になった。

// 2回目のコード WA
#include <bits/stdc++.h>
using namespace std;

int main() {
  int n;
  cin >> n;
  vector<int> arr(n);
  
  for (int i=0; i<n; i++) {
    cin >> arr.at(i);
  }
  
  int b = 1;
  int count = 1;
  
  for (int i=0; i<n; i++) {
    b = arr.at(b-1);
    if (b == 1) {
      cout << -1 << endl;
      break;
    } else if (b == 2) {
      cout << count << endl;
      break;
    } else {
      count++;
    }
  }
}

全てのボタンを押すのに必要な回数はボタンがある回数なので、
脳死でwhile(true)としていたものを、for文に変えて、i<[ボタンの個数]にした感じ。

で、ここでもやっぱりケース01.txt, 02.txt, 03.txtが通らないわけです。今度はWAとなって。
そこで、やっと考慮漏れしているな…と気づいて、下記に書き換えた。

// 3回目のコード AC
#include <bits/stdc++.h>
using namespace std;

int main() {
  int n;
  cin >> n;
  vector<int> arr(n);
  
  for (int i=0; i<n; i++) {
    cin >> arr.at(i);
  }
  
  int b = 1;
  int count = 1;
  bool f = false;
  
  for (int i=0; i<n; i++) {
    b = arr.at(b-1);
    if (b == 1) {
      cout << -1 << endl;
      f = true;
      break;
    } else if (b == 2) {
      cout << count << endl;
      f = true;
      break;
    } else {
      count++;
    }
  }
  
  if (!f) {
    cout << -1 << endl;
  }
}

ボタン2が押されないパターンについて、「押すボタンがループしているパターン」だけを考えていたけど、

ボタン1 -> ボタン3 ->　ボタン4 -> ボタン3 -> ボタン4 .....

「途中からループされるパターン」というのも考慮が必要だったわね。
不覚だったわ。
あーこういうこともあるわねと思ったので、あらかじめ考慮できてないケースを拾える方法をとっておくとスムーズそうね。

3回目のコードは、とりあえず考慮漏れを拾うという意気込みだけだったけど、
for文内は、b==1の場合を考えなくていいので、こうした方が短くできるわね。

if (b == 2){
  cout << count << endl;
  f = true;
  break;
} else {
  continue;
}