AtCoder蟻本 初級編 2-2 貪欲法 ②区間スケジューリング問題

KUPC2015 A - 東京都

A - 東京都

概要

英小文字からなる文字列を任意の文字間で任意回区切り、
tokyoという文字列とkyotoという文字列を作るとき、合わせて最大で何個作れるか出力せよ。

制約

方針

文字列の前からtokyo、kyotoそれぞれでマッチングしていく。
マッチしたらすぐその区切り方を採用してよい。
（証明の概略：例えば先にtokyoでマッチしてそれを採用しない場合、
得する可能性があるのはそのtokyoからkyoを使ってkyotoを作れる場合のみ。
その場合でも、tokyoを採用する場合よりtoを余計に使うので少し損をしている。）

解答

Submission #3879075 - 京都大学プログラミングコンテスト2015

#include <bits/stdc++.h>
 
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define rep(i,n) FOR(i,0,n)
#define RFOR(i,a,b) for(int i=(a)-1;i>=(b);i--)
#define rrep(i,n) RFOR(i,n,0)
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
 
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
 
	int t;
	cin >> t;
 
	string s[t];
	rep(i, t) cin >> s[i];
 
	rep(i, t){
		string a = s[i];
		int n = a.length();
		bool used[n];
		int ans = 0;
		rep(k, n) used[k] = false;
		for(int j = 0; j+4 < a.length(); j++){
			if(!used[j] && a.substr(j, 5) == "tokyo"){
				ans++;
				rep(l, 5) used[j+l] = true;
			}
			if(!used[j] && a.substr(j, 5) == "kyoto"){
				ans++;
				rep(l, 5) used[j+l] = true;
			}
		}
 
		cout << ans << endl;
	}
}