2020年6月21日 日記

2020年 6月 21日

まえがき

前にも書くからまえがき。後ろに書くからあとがき。

では、石垣は一体なんなんだ…？？

健康管理

何した

今日はABC171(あっとこーだーびぎなーずこんてすと)でしたね。

E問題まで茶diffでしたね。
にぼしくんはEまでそこそこの速さで解いて1649perfでした(このガキ、天才かもしれない)
自慢に途中までの順位表貼っておきますね。

具体的に

今日解いた問題

ABC016 C- 友達の友達

• [set,重複は許さない]
  

Aの友達にBさんがいる。
Bさんの友達にCさんがいる。
AとCが友達でないならば、CはAの友達の友達

僕は、N人それぞれの友達リストみたいなのをsetとvectorで2つ作って解きました。

int main()
{
    int n, m;
    cin >> n >> m;
    vector<set<int>> frien(n);
    vector<vector<int>> tomo(n,vector<int>(0));
    rep(i,m){
        int a, b;
        cin >> a >> b;
        --a, --b;
        frien[a].insert(b);
        frien[b].insert(a);
        tomo[a].push_back(b);
        tomo[b].push_back(a);
    }

    //if(n == 1){
    // cout << 0 << endl;
    // return 0;
    //}
    rep(i,n){
        vector<int> ans(0);
        for(auto x:tomo[i]){
            // x は i の友達
            for(auto y:tomo[x]){
                // i の友達の友達
                ans.push_back(y); // ansはiの友達の友達を入れるvector(i自身が入ることもある)
            }
        }
        SORT(ans); ans.erase(unique(ans.begin(),ans.end()), ans.end()); // ansから、重複している要素を取り除く
        int kotae = 0;
        rep(j,ans.size()){
            if(frien[i].count(ans[j])){
            } else {
                // ans[j] が i　の友達で無いならばkotaeに+1
                kotae ++;
            }
        }
        cout << max(0,kotae - 1) << endl; // max(0,が無いと、iに一人も友達が居ないときに事故る。
        　
    }
}

ABC171 A~E

A- αlphabet

• [英小文字と英大文字,知らない関数]
  

解説放送3秒だけ見ました。 どうやら、is_lower,is_upperという関数がc++にはあるらしいです。すごいですね。

B- Mix Juice

• [ソート,最小化]
  やすいのをK個買えば良い

C- One Quadrillion and One Dalmatians

• [26進数変換、バグ梅小宮]
  

10進数を2進数に変換するノリでやってあげればノリノリ。
まず、10進数6を2進数に変換してみよう。
6 / 2 = 3 余り 0
3 / 2 = 1 余り 1
1 / 2 = 0 余り 1
このとき 6 は2進数で表すと110となります。
これをc++のコードで書くと

int n = 6;
string ans = "";
while(n != 0){
    int now = n % 2;
    ans.push_back(now);
    n /= 2;
}
reverse(ans.begin(),ans.end());
cout << ans << endl;

となります。 本当？ 多分本当です。

10進数からの進数変換は、変換先をK進数とすると、Kで割った余りとKで割るを駆使して下の桁の方から決めていく、が大体の方針…
それに気づいて一歩前進

まずはWAコード

    ll n;
    cin >> n;
    string ans = "";
    while(n != 0){
        int now = n % 26;
        n /= 26;
        char c = 'a' + (now-1);
        ans.push_back(c);

    }
    reverse(ans.begin(),ans.end());
    cout << ans << endl;

テキトウに動かしてみますか

こんな感じ。'z'が出てくるときだけバグってることが分かります。 26は本来'z'になってほしい。
でも、27は'z'の次なので'aa'で正しいです。

51も'ay'は正しくて、52は'az'になってほしいけど'b`'になってる。 53は52が'az'なので'ba'で正しい。

じゃぁ、どこでバグが埋め込まれたか、一体どこにバグ梅小宮がいるのか…。 そうです。

 while(n != 0){
        int now = n % 26; // ここにバグ梅小宮がいる！！
        n /= 26; //ここにバグ梅小宮がいる！！
        char c = 'a' + (now-1);//ここにバグ梅小宮がいる！！
        ans.push_back(c);

    }

え〜…バグ梅小宮じゃん…
まず,n = 26のときは 'z'にしたい、。つまり char c = 'a' + 26; であってほしい。
でも、n = 26のとき, n % 26 = 0;です。 よって、if(now == 0) now = 26; にするか、now = n % 27 にすれば良さそうだね。

カス
n % 27 にすると死にます。
n = 27 のとき、now は 1 にしたいのに0が出てくるもん（ダメダメだ)

次に、 n /= 26;
これ、n <= 25 のときはn / 26 = 0;になって、終了します。
(実際に、n <= 25 のとき、出力する答えは'a'~'y'の一文字だけなのでこれで正しい)
n = 26のときは、ans.push_back('z')だけして終了したいです。
しかし、 n / 26 = 1;となってしまい、ループが続いてしまいます。

nが26の倍数の時に注意が必要ってことです。
26 / 26 = 0にしたい。

if(n%26==0){  
    n/=26; 
    n--;
} else {
    n/=26;
}

こんな具合に直してあげましょう。

そうして治してやると…？

 while(n != 0){
        int now = n % 26; 
        if(n % 26 == 0){ // now == 0でもいい
            n /= 26;
            n--;
        } else {
            n--;
        }
        ans.push_back('a'+now-1);
    }

ってか、10進数2進数変換ではバグらないのに26進数に変換するときはバグるのなんでだろう
っていうのを解決するところまで記事にしたかったんだけどちょっと頭足りないや。終わり

D- Replacing

• [連想配列,和]
  

Bi を Ci に変えるたびに、a0が3個、a1が514個、a2が3個。みたいにやるのはめんどくさいです。
（計算量的にもね)

最初に全部の和を求めておきます(sum)。
biがciに変わる時、sumからはbi(biの個数)が引かれ、ci(biの個数)がたされます。この操作をするだけです。それぞれの数字が何個あるかは連想配列で管理してあげましょう。

int main()
{
    int n;
    cin >> n;
    map<ll, ll> mp;
    ll sum = 0;
    rep(i,n){
        ll a;
        cin >> a;
        mp[a]++;
        sum +=a;
    }
    ll q;
    cin >> q;
    rep(i,q){
        ll b, c;
        cin >> b >> c;
        ll num = mp[b];
        // num個のbが減る
        sum -= num * b;
        // num個のcが増える
        sum += num * c;

        cout << sum << endl;
        mp[b] = 0;
        mp[c] += num;
    }
}

E- Red Scarf

• [XOR,XORの性質]
  

XORの基本的な性質として、 K XOR K = 0 がありますね。
また、 K XOR 0 = K です。
（多分)

ABC147 D- Xor Sum4
この回で、XORワケワカランくて調べてたときに上の性質は知りました。結局其の性質を知っても上の問題は解けなかったんだけどね。

で、つまり、a[0] ~ a[n-1]までのXORを取ったものに対してa[i] のXORを取れば、a[0] ~ a[n-1] (a[i]は除く)のXORを取ったものが求められるじゃん。え、なめてるの？って感じで通しました。(E,でしょ？え、これで通るよね？でもEだよ？通らなかったらどうしよう…って思いながら提出するとACでした)

あとがき

以下は毎回記事に貼っているテンプレート

基本的に読書はTwitterで絡みのある人だけだと思いますが、僕のブログだけ見てるって人もいるかもしれないので、一応自己紹介っぽいことをしている記事を貼っておきます - 瑞々しぃにぼしの自己紹介(自己紹介の記事です)