TopCoder SRM 695 Div 2

マジで悔しいなこれ
— つたじろう (@_TTJR_) July 19, 2016

今回も悔しい結果となってしまった。あと5分あればMed提出できたのに・・・。TopCoderの制限時間って絶妙ですね。次はMedも解くぞ。

BearNSWE (Easy)

問題→ TopCoder Statistics - Problem Statement

これは累積和とって最後に距離も足すってだけ。

#include <bits/stdc++.h>
#define rep(i,a,n) for(int i=a;i<n;i++)
using namespace std;

class BearNSWE {
public:
double totalDistance(vector <int> a, string dir) {
    int x = 0; int y = 0;
    double ret = 0;
    rep(i,0,dir.length()) {
        ret += a[i];
        if(dir[i] == 'N') y += a[i];
        else if(dir[i] == 'W') x -= a[i];
        else if(dir[i] == 'E') x += a[i];
        else y -= a[i];
    }
    ret += pow(pow(x,2) + pow(y,2), 1/2.0);
    return ret;
}

BearPasswordAny (Med)

問題→ TopCoder Statistics - Problem Statement

やられました。Practiceから投稿したら通ったので多分合ってる。

配列の後ろから見ていって、 $x\left[i\right]$ がもし1以上なら、全て同じ文字で構成された $i+1$ 文字から成る文字列をvectorかどっかに $x\left[i\right]$ 個入れておく。(aだけから成る文字列、bだけから成る文字列を交互に入れられるように工夫すること)

また、 $i+1$ 文字の文字列から、 $j$ 文字の文字列は必ず $i + 1 - (j - 1)$ 個作れるので、それをもとに配列を更新する。

判定としては、配列を更新したことによって要素が負になった時、またはvectorの文字列を全部合わせたものがN文字(= 与えられる配列の大きさ)でない時は空文字にし、大丈夫なら表示する。

#include <bits/stdc++.h>
#define rep(i,a,n) for(int i=a;i<n;i++)
#define repr(i,a,n) for(int i=a;i>=n;i--)
#define pb(a) push_back(a)
using namespace std;

class BearPasswordAny {
public:
string findPassword(vector <int> x) {
    int c = 0;
    vector<string> v;
    repr(i, x.size() - 1, 0) {
        if(x[i] < 0) return "";
        else {
            rep(k,0,x[i]) {
                string temp;
                rep(j,0,i+1) {
                    if(c == 0) temp += "a";
                    else temp += "b";
                }
                v.pb(temp);
                c = 1 - c;
            }
            rep(k,0,i) x[k] -= x[i] * (i + 1 - k);
        }
    }
    string ret;
    rep(i,0,v.size()) ret += v[i];
    if(ret.length() != x.size()) return "";
    else return ret;
}