AtCoder Beginner Contest 098 解説備忘録

前書き

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文はとにかく減らせ！！！！