E問題歯が立たなかった・・・・考察が苦手！

defineとかもう大体みんな同じでしょって気持ちでマクロ略でコード載せます。(E以外)

A

文字列Sに’A’,‘B’どっちも含まれていたら’Yes’です。個人的に、setにぶち込んでsizeを見るのが好きです。

1
2
3
4
5
6
7
8


void solve() {
    string s;
    cin >> s;
    set<char> ss;
    REP(i,3) ss.insert(s[i]);
    auto ans = (ss.size()==2)? "Yes" : "No";
    cout << ans << endl;
}

B

これをさくっと解けるようになったので成長を感じます。

1回の操作をセットで考えて、何回出来るか、後はあまりについて場合分けをすれば良いです。

1
2
3
4
5
6
7
8


void solve() {
    ll N,A,B;
    cin >> N >> A >> B;
    ll ans = (N/(A+B))*A;
    ll md = N%(A+B);
    ans+=min(A,md);
    cout << ans << endl;
}

C

制約がかなり弱いので全探索で解けます。 x円は条件を満たすか？を0から見ていく感じです(3000って書いているけどもっと小さくても良いはずです。)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


void solve() {
    int A,B;
    cin >> A >> B;
    REP(x,3000) {
        ll a = (ll)((double)x*0.08);
        ll b = (ll)((double)x*0.1);
        if (A==a && B == b) {
            cout << x << endl;
            return;
        }
    }
    cout << -1 << endl;
}

D

スワップって実はかなり遅いのです。知っていましたか？

それはそうとして入力された文字列Sは$T_i = 1$のクエリが来るたび反転します。

最初に入力された文字列を$S_{in}$と呼ぶと、$S_{in}$は$T_i = 1$のクエリが二回くれば元に戻ります。

このことを利用して、$T_i = 1$クエリの飛んできた回数を見てから、反転すれば、$S_{in}$の形は最大一回の反転で作れるようになります。

次に$T_i = 2$クエリについて考えてみましょう。$S$の先頭に$C_i$が着くようなクエリが飛んできた後に、$T_i = 1$のクエリが何回飛んできたかをカウントします。

こうすることで、最終的に$C_i$が$S$の先頭かどうかが分かります。

後はクエリが飛んできた順に$S_{in}$にくっつけて行けば答えの完成です。

コード中ではその時点での反転数と、合計の反転数を使って上手くやっています。後ろにつけるクエリが飛んできた場合、その時点での反転数を-1したものを保存することで後ろにくっつける動作の対応をしています。

今見ると賢い。(デバッグ用の出力消し忘れて2WAしたのでやっぱり賢くない。cerr(標準エラー出力)使おうね)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37


void solve() {
    // その時点での反転数、文字
    vector<pair<int,char>> v;
    string S;
    cin >> S;
    int Q;
    cin >> Q;
    //　総反転すう
    int turned = 0;
    REP(_,Q) {
        int q;
        cin >> q;
        if(q==1) turned++;
        else {
            int f;
            char c;
            cin >> f >> c;
            bool is_ushiro = (f==2);
            int add = is_ushiro ? -1 : 0;
            v.emplace_back(turned+add, c);
        }
    }
    
    // S_inの反転
    if (turned%2==1) REP(i,S.size()/2) iter_swap(S.begin()+i,S.end()-1-i);
    
    for (const auto &it: v) {
        ll place = (turned-it.first);
        bool is_mae = place%2==0;

        if(is_mae) S.insert(S.begin(),it.second);
        else S.push_back(it.second);

    }
    cout << S << endl;

}

E

E - Divisible Substring

コンテスト中歯が立たなかった・・・

入力例として以下が与えられたとして考えてみる。

この例で行くと、連続する部分文字列には、例えば123とか345とか567とかが挙げられる。

ここで、

$123 = (1234567 - 4567)/10000$

$345 = (34567 - 67)/100$

$567 = (567 - 0)$

と表せられる。

つまり、文字列の右側から$i$個分からなる整数を$a_i$と置けば、$a$だけで全ての部分文字列を表記出来ることが分かる。

今回の例で行くと、

$a_0 = 0 $
$a_1 = 7 $
$a_2 = 67 $
$a_3 = 567 $
$a_4 = 4567 $
$a_5 = 34567 $
$a_6 = 234567 $
$a_7 = 1234567 $

とすれば

$123 = \frac{a_7 - a_4}{10^4}$
$345 = \frac{a_5 - a_2}{10^2}$
$567 = \frac{a_3 - a_0}{10^0}$

と表すことができて、任意の部分文字列について

$$ \frac{a_l - a_r}{10^r} $$

で表す事ができます。

求めたい物は

$$ \frac{a_l - a_r}{10^r} \equiv 0 \pmod{P} $$

を満たす(l,r)の組みの個数

後は、合同式の変換を行い、

$$ \frac{a_l - a_r}{10^r} \equiv 0 \pmod{P} \Rightarrow a_l - a_r \equiv 0 \pmod{P} \Rightarrow a_i \equiv a_r \pmod{P} $$

と変換していきます。

後は、

$$ a_i \equiv a_r \pmod{P} $$

になるようなl,rの組を求めて終わりやんけ！ってなるかもしれませんがこれは違います。

$$ a_i \equiv a_r \pmod{P} \Rightarrow \frac{a_l - a_r}{10^r} \equiv 0 \pmod{P} $$

が常に成り立つ訳ではないからです。合同式の割り算には**「法」と互いに素のものしか割ることができない**というルールがあるため、 10と互いに素であるようなPが設定された場合のみ成り立ちます。

ざっくり言うと、2,5以外です。

ともあれ、Pが2,5でなければ良いので一旦数え上げてみましょう。

$a_i$を$P$で割った余りで分類しmapを使って数えて行けば良いです。

例えば1余るような$a_i%P$が4つあったら、${}_4 C_2$個みたいに、組み合わせを求めて行けば良いのです。

P=2,5の場合について

P=2の場合、最下位の桁が偶数なら2で割り切れます。
P=5の場合、最下位の桁が0か5なら5で割り切れます。

コード

けんちょんさんの実装と差異が無くなってしまった・・・・写経ACですねこれは・・・

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48


#include <bits/stdc++.h>
#define INF 1e9
using namespace std;

#define REPR(i,n) for(int i=(n); i >= 0; --i)
#define FOR(i, m, n) for(int i = (m); i < (n); ++i)
#define REP(i, n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define ALL(a)  (a).begin(),(a).end()

template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
int gcd(int a,int b){return b?gcd(b,a%b):a;}
typedef long long ll;
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}

void solve() {
    int N,P;
    cin >> N >> P;
    string S;
    cin >> S;
    if (P==2 || P==5) {
        ll res = 0;
        REP(i,N) if ((S[N-i-1]-'0')%P == 0) res += N-i;
        cout << res << endl;
        return;
    }


    map<ll,ll> mp;
    // a_0は0なのでその分を考慮する。
    mp[0] = 1;
    ll tenfactor = 1,cur = 0;
    REP(i,N) {
        cur = (cur + (S[N-i-1] - '0') * tenfactor) % P;
        tenfactor = (tenfactor * 10) % P;
        if (mp.count(cur) == 0) mp[cur] = 0;
        mp[cur]++;
    }

    ll res = 0;
    for(const auto &it: mp) res += (it.second*(it.second-1))/2;
    cout << res << endl;
}

int main() {
    solve();
    return 0;
}

提出 #10747581 - AtCoder Beginner Contest 158

気持ち

E無ゾ。実装も結構難しいような・・・・

【Eまで】ABC158を振り返る。

A

B

C

D

E

P=2,5の場合について

コード

気持ち

参考