AtCoder Beginner Contest 098 解説備忘録

10241 ワード
ABC098 競技プログラミング abc AtCoder C++ C++ テキストリンク

前書き

AtCoder Beginner Contest 098 を解いてみた．解けなかった問題の備忘録．

B問題

[問題はこちら]

[ポイント]

・文字列でもfor文は使える．for(char c='a';c<='z';c++)の要領である．

・文字列にある文字が含まれているかどうか確認するにはs.find("hoge")
含む場合は文字列が最初に出現する位置，含まない場合はstring::nposと出力される．

[参考]-(http://marycore.jp/prog/cpp/std-string-find-search/)

以下はACのコード：

main.cpp
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cmath>
#include <set>
#include <sstream>
#include <bitset>

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)

typedef long long ll;

using namespace std;

int main() {

    int n;
    cin >> n;
    string s;
    cin >> s;

    vector<int> cnt(n-1,0);

    FOR(i, 1, n){
        string l = s.substr(0,i);
        string r = s.substr(i,n-i);
        for(char c='a';c<='z';c++){
            if ((l.find(c) != string::npos)&&(r.find(c) != string::npos)) {
                cnt[i-1]++;
            }
        }
    }

    int max = *max_element(cnt.begin(),cnt.end());

    cout << max << endl;

    return 0;
}

D問題

[問題はこちら]

[ポイント]
・XORとは...同じだったら0，違ったら1を出力する．a^bで表現．

入力1 入力2 出力3
0 0 0
0 1 1
1 0 1
1 1 0

※(0,0),(0,1),(1,0)はxorも+も同じ結果になる！

・ある範囲で題意を満たす → その範囲に含まれる範囲(部分集合？)も題意を満たす

・「尺取り虫」方式で探索するとループが一つなので速い．

main.cpp
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cmath>
#include <set>
#include <sstream>
#include <bitset>

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)

typedef long long ll;

using namespace std;

int main() {

    ll n;
    cin >> n;
    vector<ll> a(n);
    FOR(i, 0, n){
        cin >> a[i];
    }

    ll cnt=0;
    ll l=0,r=0;
    ll tmp=0;
    while (r<n) {
        if((tmp+a[r]) == (tmp^a[r])){
            tmp += a[r];
            r++;
            cnt += r-l;
        }else{
            tmp = tmp - a[l];
            l++;
        }
    }

    cout << cnt << endl;
    return 0;
}

あとがき

高速化のため，for文/while文はとにかく減らせ！！！！