AtCoder ABC136の振り返り

ABC136に参加したので，復習がてら振り返ります．

A問題

普通にをしました．負になる場合だけ気をつけました．こういう簡単な時にさらっと三項演算子使えるようになりたいです．

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

using namespace std;

typedef long long ll;

int main() {
    int A, B, C; cin >> A >> B >> C;

    if (A - B > C) cout << 0 << endl;
    else cout << C - A + B << endl;

    return 0;
}

B問題

一度文字列になおせばsize()の判定でいけるじゃん！と思いましたが，C++で数字から文字列に直す方法を知らなかったので（調べればよかったですが），数字のまま処理しました．1から10倍していって，奇数回目の分だけ数えました．

文字列に直す場合，to_string()なる便利なものがあるみたいです．常識かもしれませんが．．．

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

using namespace std;

typedef long long ll;

int main() {
    int N; cin >> N;

    int cnt = 0, i = 1, j = 1;
    bool flag = true;

    while (1) {
        i *= 10;
        if (i <= N) {
            if (flag) cnt += i - j;
        } else {
            if (flag) {
                cnt += N - j + 1;
            }
            break;
        }
        j = i;
        flag = !flag;
    }

    cout << cnt << endl;
}

C問題

最初は，のときにから１をひく方針でいきましたが，それだと1332とかが無理になるので，少し悩みました．

最初からみていく場合，１引ける場合は引いておいて損はない（引く操作が最適？？）ので，その方針でいけました．回答は後ろからみていってました．確かに後ろからだと1332みたいな状況でもいけますね．

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

using namespace std;

typedef long long ll;

int main() {
    int N; cin >> N;
    vector<int> a(N);
    for (int i = 0; i < N; i++) cin >> a[i];

    a[0] -= 1;
    for (int i = 1; i < N - 1; i++) {
        if (a[i] - a[i+1] > 1 || (a[i] - a[i+1] == 1 && a[i] - a[i-1] <= 0)) {
            cout << "No" << endl;
            return 0;
        } else if (a[i] - a[i+1] <= 1 && a[i] - a[i-1] > 0){
            a[i] -= 1;
        }
    }

    cout << "Yes" << endl;
    return 0;
}

D問題

今回は本番中に初めてD問題が解けました！といっても時間ギリギリですが．．．

子供の人数に比べて移動回数が十分に大きいので，RLのようにRとLが切り替わるところに左右の子供がたまっていくことはすぐにわかりました．切り替わりの位置との相対距離の偶奇によってRLのどっちにいるのか判断できることも割とさくっと気づきました．が，実装力が足りず，実装にとても時間がかかりました．

RからLに切り替わる位置を覚えておいて，前から順番に子供のいる位置を決めていきましたが，もっといい実装の仕方があると思います．解説のように(R, 3), (L, 5)...みたいに保持するやり方を試しに実装したいですが，時間がある時&気が向いたらやりたいです．

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

using namespace std;

typedef long long ll;

int main() {
    string s; cin >> s;

    vector<int> ans(int(s.size()));

    vector<int> ch;
    for (int i = 1; i < s.size(); i++) {
        if (s[i] == 'L' && s[i-1] == 'R') ch.push_back(i);
    }

    int tmp = 0, i = 0;
    while (i != ch.size()) {
        while (tmp != s.size()) {
            if (s[tmp] == 'R' && tmp < ch[i]) {
                if ((ch[i] - tmp) % 2 == 0) ans[ch[i]]++;
                else ans[ch[i]-1]++;
            } else if (s[tmp] == 'L' && tmp >= ch[i]){
                if ((tmp - ch[i]) % 2 == 0) ans[ch[i]]++;
                else ans[ch[i]-1]++;
            } else {
                i++;
                break;
            }
            tmp++;
        }
        if (tmp == int(s.size())) break;
    }


    for (int i = 0; i < s.size(); i++) {
        cout << ans[i];
        if (i != int(s.size())-1) cout << " ";
    }
    cout << endl;
    return 0;
}