ひとりも見捨てないことを、あきらめない

学校教育、社会教育、数学、技術家庭科、Youtube、EdTech、ICT、プログラミング、その他

むずかしいなあ・・・(●'◡'●)汗。11/08 金

 先日、AtCoder のコンテストに参加したのですが、難しくて制限時間内には正答できませんでした。くやしいなあ。問題は、次のとおりです。

問題文
長さ N−1 の文字列 S が与えられます.
S の各文字は < または > です.
長さ N の非負整数列 a1,a2,⋯,aN は, すべての i (1≤i≤N−1) について次の条件をみたす時,良い非負整数列と呼ばれます.
Si= < のとき: ai<ai+1
Si= > のとき: ai>ai+1
良い非負整数列の要素の総和としてありうる最小の値を求めてください.

 

 制限時間内に正答できなかったので、翌日、再度挑戦しました。時間外なので、得点にはなりません。結局のところ、何度も失敗し、ようやく正答にたどりつきました。

f:id:takase_hiroyuki:20191104095631p:plain

 

 具体的には、次のようなプログラムになります。

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

int main() {
 string S;
 cin >> S;
 long sz = S.size();

 vector <long> T(sz+1);
 vector <long> T1(sz+1);
 vector <long> T2(sz+1);

 T1.at(sz) = 0;
 for (long i=sz-1; i>=0; i--)
 if (S.at(i)=='>') {
  T1.at(i) = T1.at(i+1)+1;
 } else {
  T1.at(i) = 0;
 }

 T2.at(0) = 0;
 for (long i=0; i<sz; i++)
 if (S.at(i)=='<') {
  T2.at(i+1) = T2.at(i)+1;
 } else {
  T2.at(i+1) = 0;
 }

 for (long i=0; i<sz+1; i++ ) T[i] = max( T1[i], T2[i] );

/*
 cout << T1[0] ;
 for (long i=0; i<sz; i++ ) {
  cout << S[i];
  cout << T1[i+1] ;
 }
 cout << endl;

cout << T2[0] ;
 for (long i=0; i<sz; i++ ) {
  cout << S[i];
  cout << T2[i+1] ;
 }
 cout << endl;
 
 cout << T[0] ;
 for (long i=0; i<sz; i++ ) {
  cout << S[i];
  cout << T[i+1] ;
 }
 cout << endl;
*/

 long ct =0;
 for (long i=0; i<sz+1; i++ ) ct = ct + T[i];
 cout << ct << endl;
}

 

 今後も、がんばって修行します。