AtCoder：ABC140振り返り

AtCoderのABC140に参加したのでその振り返りです．今回はなんとかDまで解けたという感じで，D問題の実装にてこずりました．．．ただ，一応全部一発で通せたので，そこはよかったです．

A問題

3桁のうち，それぞれの桁が1からNまでN個の可能性があるので，単純にです．

#include <iostream>
#include <vector>
#include <cmath>
#include <iomanip>
#include <string>

using namespace std;

typedef long long ll;

int main() {
    int N; cin >> N;
    cout << pow(N, 3) << endl;
    return 0;
}

B問題

i番目の料理を食べた時の満足度，なら追加の満足度を足して行きます．これも複雑なアルゴリズムは必要なく，言われた通りに実装すれば良い問題でした．ここ１ヶ月くらいABCに参加した感じでは，基本B問題までは素直に実装すれば良い感じですね．

#include <iostream>
#include <vector>
#include <cmath>
#include <iomanip>
#include <string>

using namespace std;

typedef long long ll;

int main() {
    int N; cin >> N;
    vector<int> a(N), b(N), c(N-1);
    for (int i = 0; i < N; i++) {
        cin >> a[i];
        a[i]--;
    }
    for (int i = 0; i < N; i++) cin >> b[i];
    for (int i = 0; i < N-1; i++) cin >> c[i];

    int res = 0;
    for (int i = 0; i < N; i++) {
        res += b[a[i]];
        if (i < N-1 && a[i+1] == a[i] + 1) res += c[a[i]];
    }

    cout << res << endl;
    return 0;
}

C問題

数列に関する2項間の関係がわかっていて，の最大値を求める問題でした．を読み替えるとになります．をそれぞれ最大にするには，にすればよいことになります．ただし，とは がないので，，になります．

こういうところで（infは十分大きい数）とおければ場合分けなしでかっこよくコードが書けるんですが，なかなかとっさに思いつかないですね．．．

#include <iostream>
#include <vector>
#include <cmath>
#include <iomanip>
#include <string>

using namespace std;

typedef long long ll;

int main() {
    int N; cin >> N;
    vector<ll> b(N-1);
    for (int i = 0; i < N-1; i++) cin >> b[i];

    ll res = b[0];
    for (int i = 0; i < N - 2; i++) {
        if (b[i] <= b[i+1]) res += b[i];
        else res += b[i+1];
    }
    res += b[N-2];
    cout << res << endl;
}

D問題

一応ACになりましたが，無理やり通した感．．．前にもLとRの文字列の問題がありましたが，規則はわかりますが実装が難しいです．．．

この問題では

• LRLLを反転するとRRLR
• LRLRを反転するとLRLR

みたいな感じで，両端以外は反転しても幸福な人は増えません．しかも両端がLRRLみたいに揃っていないと，ひっくり返しても幸福な人は増えないことになります（LLRRをひっくり返してもLLRR）．

なので，基本的な方針としてLLRRLLのRのように別の文字に囲まれている文字を一気にひっくり返すことにしました．この操作１回ずつに幸福な人は２人（両端の人）増えることになります．また，両端を別の文字で囲まれて，同じのみで構成される部分列の個数はLとRで１個違いになります．

ここまで考えて，両端の文字が揃っていない場合にうまくいかない（最後の一回は１人しか幸福な人が増えない）ことに気づいて，慌てて場合分けを増やそうとして，あってるのかわからないけどサンプルは全部通ったし出しちゃえ！でACでした．

今思えば，両端が揃っていなくても最後の１回しか処理は変わらない ＋各操作で2人ずつ増えていくので，最初の幸福な人の人数をfとするとが幸福な人の最大値N-1以上になるかどうかで場合分けすれば良いだけの話でした．つまり，K回の操作すべてで２人増えることにしても差が生じるのは最後の操作だけであり，その場合は幸福な人の最大値を超えてしまうので最大値を出力すればよかったです．うまく言えませんが．．．

#include <iostream>
#include <vector>
#include <cmath>
#include <iomanip>
#include <string>

using namespace std;

typedef long long ll;

int main() {
    int N, K; cin >> N >> K;
    string s; cin >> s;

    int res = 0;
    for (int i = 1; i < int(s.size()); i++) {
        if (s[i-1] == s[i]) res++;
    }

    vector<int> R, L;
    int idx = 0, r=0, l=0;
    while (idx != N && s[idx] != 'R') idx++;
    while (idx != N) {
        while (idx != N && s[idx] != 'L') idx++;
        while (idx != N && s[idx] != 'R') idx++;
        if (idx != N) l++;
    }
    idx = 0;
    while (idx != N && s[idx] != 'R') idx++;
    while (idx != N) {
        while (idx != N && s[idx] != 'R') idx++;
        while (idx != N && s[idx] != 'L') idx++;
        if (idx != N) r++;
    }

    if (r==0 || l==0) {
        cout << N - 1 << endl;
        return 0;
    }
    int sr=0, sl=0;
    if (s[0] == 'L') sl++;
    else sr++;
    if (s[int(s.size())-1] == 'L') sl++;
    else sr++;

    if (K >= min(r+sr, l+sl)) {
        cout << N-1 << endl;
        return 0;
    } else if (K >= min(r, l)){
        cout << res + min(r, l)*2 << endl;
    } else {
        cout << res + K*2 << endl;
    }
    return 0;
}

まとめ

今回はE問題にまわす時間はなかったです．見た感じE問題は時間があっても解けなかったと思いますが．．．D問題のような問題はなんの情報を保持しておけば良いのか（LとR，RとLの変わり目を分けるのかどうか，とか），それをどう処理すれば良いのか難しいです．