3月4日日記

前書き

3日間くらいずっと競プロサボってゲームしたり生活リズムを壊していました。（長時間睡眠が取れずに、2,3時間寝て起きてしまうことが多くて困っていた。）

今日は6＋2の8時間睡眠が取れたので、また競プロの精進を再開していきたいぞ。と思っている。

ということで今日は前回のABC(ABC157)の復習をしま〜っす writerがこrtnさんの回です。コンテスト前のTwitterの盛り上がりが楽しかったですね。

ABC157c Guess The Number

[全探索,if文ゴリ,実装ゲー,しんどい]

本番のタイムは30分23秒の2ペナです。本番では無理やりゴリゴリif文を書いて、条件に合致する整数を作る。という方針で解いていました。正しい（バグを作りづらい）解き方は、0~999を見ていき、各数字が条件と一致しているかを見る方針出といていました。こっちの方が賢いですね。（うん）

解き方

さっき言ったように、0~999の数字を試して行き、それぞれが　条件と一致するかを確認していく。

int main()
{
    int n,m;
    cin >> n>>m;
    vector<P> p(m);
    rep(i,m) cin >> p[i].first >> p[i].second ;
    rep(x,1000){
        int nx = x / 10 ; // 計算用の変数nx これが0になるまでベクターに入れる
        vector<int> d(1,x%10);
        while(nx){
            d.push_back(nx%10) ; 
            nx /= 10 ;
        }
        rSORT(d); /*rSORTは、reverse(d.begin(),d.end())　のこと（マクロです）*/
        //ここまでで、xが301のとき配列dに{3,0,1}のような情報が保持出来た。
        if( d.size() != n ) continue;  //配列のサイズが桁数
        bool ok = true ; 
        //条件に沿ったものかどうかを今から判定する
        rep(i,m){ 
            //入力で受け取った桁数-1番目の数字が、一致していなかったらxは条件を満たさない
            if (d[p[i].first-1] != p[i].second ) ok = false ;
        }
        if(ok){
            cout << x << endl ; 
            return 0;
        }
    }
    cout << -1 << endl;
}

ABC157d Friend Suggestions

[UnionFind,ユニオンファインド,グラフ理論]
初めてunionfindをつかう問題だと本番で気づき、さらに通すことが出来た（やったね）

解き方

友達（友達の友達の…友達の友達）で繋がっているところを集合としてまとめていく。友達の友達（の友達…の友達）の間には辺が出来ているので、そいつらとは友達になれそうだ（やったね）
しかし、その中でもブロックしている人とは友達になれない。

よって、行き来出来る人たちの中で、既に友達である人と、ブロックしている人（と、自分）を引いた数が答えとなる。

行き来できる人たちの数はUnionfindにサイズっていう関数を作ってあげれば見ることが出来る！！

僕の提出コード(写経) 一応、わかりやすいコードだと思いますよ

あとがき

あとで描きたくなったら書きます（あとがきなので）

それじゃ、女の子（概念）とゲームしてくるね