Time-2 - GET INTEGERS

2 secs 1024 MB

この問題はシミュレーションを問います。

普通に貪欲で計算していくことで正解できます。注意として、一回負の整数を記録した後の和は最大値になり得ないとは限らないことに注意してください。また動作前に記録される整数は $(0,0)$ のものを含むため、最大値の初期値は $C$ ※ $_1$ であることに注意してください。
計算量は $O(N)$ で実装することができます。

以下が解答例になります(C++)。

※ $_1$ 問題の式に $x=0,y=0$ を代入することで直感的にわかります。

※ なおこの問題は $k$ 回目の動作の時点で記録された整数の総和 $S_k$ 、その時点で記録される整数 $C_k$ とすると、 $S_{k+1}=S_k+C_k$ が成り立ちます。
これは累積和の更新と言っても変わりありません。答えは $\max(S_1,S_2,...,S_N)$ となるので、これから貪欲に計算することが適切であることがわかります。

C++

xxxxxxxxxx
 
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < n; i++) //[0,n)
#define srep(i,a,b) for(int i = a; i < b; i++) //[a,b)
#define all(A) (A).begin(),(A).end()
#define rall(A) (A).rbegin(),(A).rend()
#define pmt(A) next_permutation(A)
using namespace std;
using ll = long long;
using ull = unsigned long long;
using P = pair<ll,ll>;
using pq = priority_queue<ll,vector<ll>,greater<ll>>;
const ll inf = 8e18;
const int iinf = (int)1e9;
const int mod9 = 998244353;
const int mod1 = 1000000007;
struct Edge { int to; ll cost; int from; };
bool compe(const Edge &e,const Edge &e2){ return e.cost < e2.cost; }
using Graph = vector<vector<int>>;
using EGraph = vector<Edge>;
using SGraph = vector<set<ll>>;
template <typename T>
int siz(T& a){ return (int)a.size(); }
using namespace std;
​
int main(){
    int n,a,b,c; cin >> n >> a >> b >> c;
    string s; cin >> s;
​
    ll ny = 0,nx = 0;
    ll now = c,ans = c;
    rep(i,n){
        if(s[i] == 'U') nx++;
        if(s[i] == 'D') nx--;
        if(s[i] == 'R') ny++;
        if(s[i] == 'L') ny--;
        
        now += a*ny*ny+b*nx+c;
        ans = max(ans,now);
    }
    cout << ans;
}
​

Python

xxxxxxxxxx
 
n = int(input().rstrip())
a,b,c = list(map(int,input().split()))
s = input()
​
ans = c
t = c
x = 0
y = 0
for i in range(int(len(s))):
    if s[i] == 'U': y += 1
    elif s[i] == 'R': x += 1
    elif s[i] == 'L': x -= 1
    else: y -= 1
​
    t += a*x*x+b*y+c
    ans = max(ans,t)
print(ans,end="")