貪欲法 kupc2015 a atcoder

KUPC2015 A - 東京都

KUPC2015 A - 東京都
Feb. 2, 2020, 1:52 p.m.

目次

問題

https://atcoder.jp/contests/kupc2015/tasks/kupc2015_a

入力

T
S1
S2
...
St
  • T - 文字列の数
  • Si - tokyoまたはkyotoを1つ以上含む可能性のある文字列.

出力

N1
N2
...
Nt

それぞれの文字列からtokyoまたはkyotoを何個切り出すことが出来るかを答える問題です.

解説

文字列の先頭から検索し、tokyoまたはkyotoが見つかる度にそこまでの部分をすべて切り捨てて行けばOKです.
とにかく最初から見つかったほうを優先して切り取っていけば、残る文字列にtokyokyotoが見つかる可能性が高まるからです.
見つからなくなるか、文字列が空になったら終了です.
これをすべての文字列について繰り返します.

計算量

文字列の最大数を$T$、検索対象文字列の最大長を$N$、検索される文字列の最大長を$M$とします.
検索される文字列から対象文字列を切り出せる数の最大値は$\frac{M}{N}$です.
1回切り出すごとにfindを実行しこれはC++の仕様では計算量未定義ですが、gccの実装では$O(MN)$です.

$N$同士はキャンセルされます.

$$O(TM^2)$$

今回は$T$も$M$もともに$10^2$です.
十分に間に合います.

$$
{10^2}^3 = 10^6
$$

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
Int N;
vector<string> S;

void input() {
  cin >> N;
  string s_;
  while (cin >> s_) {
    S.push_back(s_);
  }
}

void solve() {
  for (auto s: S) {
    Int count = 0;
    loop(i,0,s.length()) {
      Int m1 = (int)s.find("tokyo", i);
      Int m2 = (int)s.find("kyoto", i);
      if (m1 == -1 && m2 == -1) break;
      if (m1 == -1) i = m2;
      else if (m2 == -1) i = m1;
      else i = min(m1, m2);
      i += 4;
      count++;
    }
    cout << count << endl;
  }
}

int main() {
  input();
  solve();
  return 0;
}