全問リアル就活Qの問題

ねむい

• 寝ようと思ったらTwitterで流れてきた問題文を読んで考えてしまった。
• 人は考えると寝れなくなるそうですね。知らんけど

問題文

大文字の英字のみからなる文字列が与えられる。文字列のうち3箇所を選び、左から順に取り出した時にABCとなるのは何通りか。ただし、計算量は$O(N)$とする

入力例1

AABBCC

出力例1

8

入力例2

ABCABCABCABCABCABCABCABCABCABCABC

出力例2

286

---

想定解

• $S_i$を頭から見ていく。そのとき、$S_i$まで見たときのAの個数、ABの個数、ABCの個数を持つ変数を用意しておく
• $S_i$がAのとき、Aの個数をプラス1する。
• $S_i$がBのとき、ABの個数にAの個数を足し合わせる。
• $S_i$がCのとき、ABCの個数にABの個数を足し合わせる。

# include <bits/stdc++.h>
using namespace std;

int main() {
  string s;
  cin >> s;

  int a = 0, ab = 0, abc = 0;
  for (int i = 0; i < s.size(); i++) {
    if (s[i] == 'A') {
      a++;
    }
    if (s[i] == 'B') {
      ab += a;
    }
    if (s[i] == 'C') {
      abc += ab;
    }
  }

  cout << abc << endl;

  return 0;
}

他の解法

• Bを固定して考える
• 各Bの左側のAの個数とCの個数の積が、そのBを使った時にできるABCの場合の数になる
• $S_i$まで見たときのAの個数とBはあらかじめ求めておけば良い
• なんかコード汚い気がする。ごめんなさい

# include <bits/stdc++.h>
using namespace std;

int main() {
  string s;
  cin >> s;

  int n = s.size();
  vector<int> ruiA(n+1), ruiC(n+1);

  // この辺で累積和取ってる
  for (int i = 0; i < n; i++) {
    ruiA[i] = s[i] == 'A';
    ruiC[i] = s[i] == 'C';
    if (i >= 1) ruiA[i] += ruiA[i-1];
  }
  for (int i = n-1; i > 0; i--) {
    ruiC[i-1] += ruiC[i];
  }

  // 答えを求める
  int ans = 0;
  for (int i = 1; i < n-1; i++) {
    if (s[i] == 'B') {
      ans += ruiA[i-1] * ruiC[i+1];
    }
  }

  cout << ans << endl;


  return 0;
}

他の解法

• 想定解のやつをDPでやる
• 文字数が増えるとDPの方が良いって強い人が言ってた
• dp[0]がA、dp[1]がAB、dp[2]がABCの状態になってる.

# include <bits/stdc++.h>
using namespace std;

int main() {
  string s;
  cin >> s;

  vector<int> dp(s.size());

  for (int i = 0; i < s.size(); i++) {
    if (s[i] == 'A') {
      dp[0]++;
    }
    if (s[i] == 'B') {
      dp[1] += dp[0];
    }
    if (s[i] == 'C') {
      dp[2] += dp[1];
    }
  }

  cout << dp[2] << endl;

  return 0;
}

感想

• 普通に思いつかなかった。
• 走査したとき、Bを見つけたらそのときのABの個数はAの個数。Cを見つけたらそのときのABCの個数はABの個数。普通に考えればそうか。なんで思いつかなかったんだろ。えーんえーん。
• 僕がやったことないDPの使い方が知れてよかった。今までインデックスを持つタイプのDPしかやったことなかったから。