AtCoder Beginner Contest 073 - u_sho競プロぶろぐ

　日曜にアクセス解析とかいう機能を使ってみたんだけど、アクセス数が毎日１(なお自分の模様)でちょっと心折れそうだった。yukicoderの解説に上げたらアクセス数が４になったので、ちょっと頑張ろうと思った今日であります。

　というわけで、土曜日(9月9日)にあったABC073の挑戦記録ですね。D問題(最短経路問題)が解けなかったのでまだまだですね。要復習です。。。

　じゃあA問題いきますね。問題名は「September 9」、thが欲しいところですね。AtCoderはいつも通り２桁の自然数Nを与えてくれるので、一の位か十の位に「９」が含まれているかどうかを判定すればOK。書き方はいろいろ。

　まずはansの型宣言を忘れ、char型の"9"とint型の9を間違えてしまって私がCE＆WAを食らってしまったchar型配列を使うコーディング。このように書けば通るはずです。

#include <iostream>
using namespace std;
bool ans;
int main(){
    char N[2];
    cin >> N[0] >> N[1];
    if(N[0]=="9" || N[1]=="9")ans++;
 
    if(ans)cout<<"Yes\n";
    else cout<<"No\n";
    return 0;
}

　この前も書いたけど、グローバル変数として宣言すると、勝手に0とかそれっぽいもの(falseとか"\0"とか)に初期化されるので、悪い子(競プロ以外ではあまり使わない方がいいかな)だけど使ってあげてね。タイプ時間とソースコード長の短縮に役立つよ。あと、C++においてbool型は、falseが0、trueが1に対応してるということも、覚えておくと便利ですね。

　まあ、コンテスト中は思考停止してて、なんでWA食らったのか探すのがめんどくさかったので、最初っから書き直したんだ。これでACです。想定解はこっちらしいよ。

#include <iostream>
using namespace std;
int main(){
    int N;
    cin >> N;
    
    int N1 = N%10;
    int N10 = N/10;
 
    if(N1==9 || N10==9){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }
    return 0;
}

　えっと、C系統において整数型(int, long, long long, etc)では、小数点以下は切り捨てられるから、それを生かしたコードですね。以上。

　次はB問題ですね。問題名は「」、1e9(==10^9, 指数表記は便利なので使っていきたい)文字の文字列には、毎度お馴染みN個の欠損があります。i番目の欠損はl[i]文字目からr[i]文字目までで、この文字列全体で何文字欠損があるか教えてあげればいいんですが、Beginnerへの優しさ(易しさ？)ということで、欠損範囲が重なる((l[i],r[i])=(1,3) && (l[j],r[j])=(2,4) && i≠j)ようなことはありません。つまり、各欠損の文字数を適当な変数(このコードではans)に足していけばACがもらえそうですね。

#include <iostream>
using namespace std;

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

    int l, r, ans=0;
    for(int i=0; i<N; i++){
        cin >> l >> r;
        ans += r-l+1;
    }

    cout << ans << endl;
    
    return 0;
}

　このとき気を付けるのは、lとrを配列に入れないということですね。int型の変数は１つにつき32bit(==4Byte)くらいなので、要素数がNの最大値1e9個であるようなint型配列を作るときは、配列１つにつきメモリが(4×1e9)Byte ≒ 4Gb 必要になります。つまり、lとrを配列に入れていくと、私のようにMLE(Memory Limit Exceeded)を食らってしまうというわけです←　気を付けましょう。

　いま奄美大島ー成田のバニラエアの便の中でこれ書いてるんだけど、対地速度950km/hとか機長さんが言ってるので、人力で出せる速度でちゃんと飛行してる鳥人間コンテストの機体製作ってすげえんだなって思った

　では、C問題にゆきましょう。またしてもNが登場するよ。問題名は「」、N個の自然数A[N]がもらえるんで、A[1]から順番に、紙に書いてゆくよ。でも、すでにA[i]が紙に書いてあったら、それは跡形もなく消すよ。例えば、N=3, A={1,2,1,1}だと、紙の上では、1 → 1, 2 → 2 → 1, 2 てな感じで書かれてある数が変わるよ。これもMLEに注意しようね。

#include <iostream>
#include <set>
using namespace std;

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

    set<long long> onPaper;

    long long A;
    for(int i=0; i<N; i++){
        cin >> A;
        bool c = onPaper.erase(A);
        if(c==0){
            onPaper.insert(A);
        }
    }
    
    cout << onPaper.size() << endl;
    return 0;
}

　このコードではsetっていうやつを使っていますね。まあqueとかstackっぽい感じで、要素を追加するときには変数名.insert(要素) 、逆に要素を消すときには変数名.erace(要素) って書けばOK。要素数が知りたいときには変数名.size() 。んで、setやstackと違って、setには同じ数は入らない(要素は重複しない)という大変便利な特徴がありましてですね、今回はそれを使いました。

　onPaper.erace(A) ってやるとonPaperの要素Aを消せるんだけど、当然onPaperの中にAっていう要素がないとAは消せないんだよね。つまり、.erace()って書いてもeraceされないことがあるわけで、それがわかんないのは困る。というわけでうまくいったら1(true)、うまくいかなかったら0(false)を返してくれる機能があるんだよね。便利だね。

　何日もまたいでやる気なくなっちゃったからここで終わるね(←おい)。