TopCoder SRM 609 Div1 Easy MagicalStringDiv1 [1人競技プログラミング Advent Calendar 2016 9日目]
この記事は1人競技プログラミング Advent Calendar 2016 9日目の記事です。
問題概要:
TopCoder Statistics - Problem Statement
修正前の呪文の文字列Sが与えられる。
がN個の後に<がN個続いている文字列が魔法の呪文となる。元の文字列から任意の箇所の文字を削除して魔法の呪文を作る必要がある。
作ることが出来る呪文の最大の長さを答えよ。
解いた方法:
文字列を適当な箇所で二分割し、左側にある>の個数と右側にある<の個数をカウントして少ない方*2が作れる呪文の長さになる。
全部列挙して試せばよい。
SRM 607 Div1Easy分からなかった…。
#include<bits/stdc++.h> #define MP make_pair #define PB push_back #define ALL(x) (x).begin(),(x).end() #define REP(i,n) for(int i=0;i<(n);i++) #define REP1(i,n) for(int i=1;i<(n);i++) #define REP2(i,d,n) for(int i=(d);i<(n);i++) #define RREP(i,n) for(int i=(n);i>=0;i--) #define CLR(a) memset((a),0,sizeof(a)) #define MCLR(a) memset((a),-1,sizeof(a)) #define RANGE(x,y,maxX,maxY) (0 <= (x) && 0 <= (y) && (x) < (maxX) && (y) < (maxY)) using namespace std; typedef long long LL; typedef unsigned long long ULL; typedef vector<int> VI; typedef vector<VI> VVI; typedef vector<string> VS; typedef vector<LL> VLL; typedef pair<int,int> PII; const int INF = 0x3f3f3f3f; const LL INFL = 0x3f3f3f3f3f3f3f3fLL; const double EPS = 1e-9; const int DX[]={1,0,-1,0},DY[]={0,-1,0,1}; class MagicalStringDiv1 { public: string S; int getLongest(string _SS) { S = _SS; int ans = 0; REP1(i, S.size()){ int l=0, r=0; REP(j, i){ l += S[j] == '>'; } REP2(j, i, S.size()){ r += S[j] == '<'; } ans = max(ans, min(l, r) * 2); } return ans; } };