michihiko-yamamoto Blog

AtCoder ABC380 振り返り

Cover Image for AtCoder ABC380 振り返り

AtCoder Beginner Contest 380 の振り返りです。

AtCoder Beginner Contest 380

配点は100-200-300-350-450といつもよりD問題以降が配点低めの回だった。 C問題まで早く解けたので、割と順位は良かったけれど、またしもD問題には歯が立たず。

ABC380

コンテスト成績 >

A: Solved

与えられた６桁の数字に、それぞれ1が1回、2が2回,3が3回含まれているかを判定する問題。 別で良い下配列に1,2,3の個数をカウントしておいて、それぞれ上記の条件を満たしているかを判定しました。 もっとエレガントな解法がありそうな気がしてならない。

#include <bits/stdc++.h>
using namespace std;
 
int main() {
    string s;
    cin >> s;
    
    vector<int> a(3,0);
 
    for(int i=0;i<6;i++){
        if (s[i] == '1') {
            a[0]++;
        } else if(s[i] == '2') {
            a[1]++;
        } else if(s[i] == '3') {
            a[2]++;
        }
    }
 
    if(a[0] == 1 && a[1] == 2 && a[2] == 3){
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
}

B: Solved

文字列が与えられ、|で区切られた-の個数を数えて、数列に復元する問題。 文字列の前から走査していき、-の数を数えて配列に詰めていった。 200点問題としては割と素直な問題。

#include <bits/stdc++.h>
using namespace std;
 
int main() {
    string s;
    cin >> s;
    
    int c = 0;
    vector<int> v;
 
    for(int i = 1; i < s.size(); i++){
        if (s[i] == '-'){
            c++;
        } else {
            v.push_back(c);
            c = 0;
        }
    }
 
    for(int i = 0; i < v.size(); i++){
        if(i!=0){
            cout << " ";
        }
        cout << v[i];
    }
    cout << endl;
}

C: Solved

0と1からなる文字列が与えられ、k番目の1の塊を取り出してk-1番目に連結する問題。

1の塊をどうやって取り出そうかパッと思いつかずに考えてしまった。悩んだ末に、1度文字列全体を走査してk番目の1の塊に含まれる1を数えてから、 改めて文字列を先頭からprintしていき、k-1番目の塊にきたら先に数えた1を表示し、k番目にきたら1を表示しない、といったコードにした。 文字列が1から始まる時と、0から始まる時のケアがちょっと面倒だったけれど、割とすんなりとACできた。

こちらももうちょっと綺麗に書けそうな気はする。
というか、Pythonだとsplit()とかで、簡単に書けそうな気がしてならない。

#include <bits/stdc++.h>
using namespace std;
 
int main() {
    int n,k;
    cin >> n >> k;
 
    string s;
    cin >> s;
 
    int c = 0;
    int cd = 0;
 
    if(s[0] == '1'){
        c++;
    }
 
    for(int i=1; i < n; i++){
        if(s[i-1] == '0' && s[i] == '1'){
            c++;
        }
 
        if(c == k && s[i] == '1'){
            cd++;
        }
    }
 
    if(s[0] == '1'){
        c = 1;
    } else {
        c = 0;
    }
 
    if(s[0] == '1' && k == 2){
        rep(j,cd){
            cout << '1';
        }    
    }
    cout << s[0];
    for(int i = 1; i < n; i++){
        if(s[i-1] == '0' && s[i] == '1'){
            c++;
            if(c == k-1){
                for(int j=0; j < cd; j++){
                    cout << '1';
                }  
            }
        }
 
        if(c == k && s[i] == '1'){
            continue;
        }
 
        cout << s[i];
    }
 
    cout << endl;
}

D: Unsolved

与えられた文字列を大文字小文字を反転させて後ろに連結する。それを新たな文字列として先の反転・連結を繰り返す。このときn番目の文字は何かをクエリとしてq回答えていく問題。

まず、素直に文字列の反転・連結を繰り返すと時間もメモリも足りなくなることが明白だったので、他の方法を思案する。
n番目の文字は、nを与えられた文字列の長さで割った余りから、何の文字であるかは容易に求められる、問題はその文字が大文字小文字反転されたものか否かで、そこがどうしてもわからず...。そのままお手上げ状態となってしまった。

解説を読むとnを二進数で表した時のbitが立っている(1の)数を数えればよいらしいが、流石にそんなこと思い付かなかった。 処理的には350点問題なのかもしれないけれど、私には数学的に難しかった。

所感

順当にABCの3問解けて、ひとまず良かった。早く解けたこともあってレーティングもHighestを更新し500点台に到達した。 ただ、一方で今回もD問題が解けずに終わってしまったのが悔しい。特に、今回はD問題の点数が低く設定されていたので、チャンスは十分にあったように思うので、なおのこと解きたかった。

C問題とD問題の間の壁が何なのか、よくわかっていないけれどどうも思っているよりも険しい道なのかもしれない。 来週も頑張ろう。