ARC082 ABC072 - u_sho競プロぶろぐ

　きのうARC(AtCoder Regular Contest)に参加したよ。C問題とD問題の２完で終わってしまったよ。しかもてきとーにやり過ぎたせいでD問題めっちゃWAくらって痛かったよ(時間が)。

　やべ、モバイルルーターのバッテリー切れた。半年前から接触悪かった充電器がついに死んでしまった(T^T)。買いにいこうにもめっちゃ雨降ってるしやる気が・・・。

・・・(￣^￣)・・・・・・(￣^￣)・・・・・・(￣^￣)・・・

　夜になって充電器繋ぎ直したら充電はじまった。わーい。

　というわけで、がんばって書きます。ちなみにTwitchでchokudaiさん(AtCoderの社長さん)がこれ解いてるのを配信してるのを聴きながら書いてるよ。やっぱE問題とばして正解だった。いやFも解けなかったけど。

　まずC問題ですね。問題名はTogether。毎度のごとくN個の自然数a[N]をもらえるので、それぞれに1を足したり引いたりしたりしなかったりして、できるだけみんなtogetherな数にしましょうっていう問題。

#include <iostream>
using namespace std;

int anum[100005];

int main(void){
    int N, a;
    cin >> N;
    
    for(int i=0; i<N; i++){
        cin >> a;
        anum[a]++;
    }
    
    int ans=0;
    for(int i=1; i<100004; i++){
        ans = max(ans, anum[i-1]+anum[i]+anum[i+1]);
    }

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

　まあ 1≦a[i]≦10^5 なので1から10^5までの配列(このコードだとanum[ ])を用意して、a[i] っていう数が a[N] の中に何個あるかを anum[ a[i] ] に保存しといて、1から・・・これ説明要る？　あー、aの入力が 1 3 2 5 だと anum={0,1,1,1,0,1,0,0,0,,,} ってなります！　以上！

あ、max(a,b) はaとbを比較して大きい方を返す関数だよ。max(max(a,max(b,c)),max(d,e)) みたいに使えるよ。便利だよ。似たようなのに min(a,b) があるよ。min(max(a,b),min(c,d)) みたいにも使えるよ。C++だけじゃなくてCにもあるよ。いい子たちだからお友達になってあげてね。

　あとねー、グローバル空間(int main(){ }の外)で変数とか配列を宣言すると0に初期化されるよ。だから、はじめ anum={0,0,0,0,0,,,,,,} ってなってるよ。boolでも0(false)に初期化されるよ。便利だよ。そんなにいい子じゃないけど競プロerのみんなはグローバル変数とお友達になってあげてね。

　chokudaiさんからツイッターフォローされた!?(deragement)　嬉しいんですがもしかしてツイッター見ながらあの速度で問題解いてるんですかね。。。

　chokudaiさんのゲーム配信(違わない)も終わったのでD問題行きましょう。どうせ全部書き終わってからしか公開しないのにこんな時間経過感じさせるブログ書いていいんだろうか。まあいいか。問題名はDerangement(混乱)です。いつものようにN個の自然数p[N]がもらえるんですが今回はそれが1からNまでの数。これをderangement (p[i] ≠ i) になるように、隣り合うpを入れ替えるには最低何回入れ替えればいいですかっていう問題。u_shoは雑魚いのでわざわざ太字で書いてあった隣り合うの4文字を読み飛ばしててWAくらったんだよ。気をつけようね←

#include <iostream>
using namespace std;

int main(void){
    int N;
    cin >> N;
    
    long long p, tp=0, tpfront=0;
    for(int i=1; i<=N; i++){
        cin >> p;
        if(p==i) tpfront++;

        if(p!=i || i==N){
            if(tpfront%2) tp += (tpfront/2)+1;
            else  tp += tpfront/2;
            
            tpfront=0;
        }
    }

    cout << tp << endl;

    return 0;
}

　tpfrontは、変数の名付けかたに問題がありそうなんで気にしないでね(・x・)　さすがに上のコードは読みづらいしアルゴリズムが悪いので、書き直しました。

#include <iostream>
using namespace std;

int main(void){
    int N;
    cin >> N;
    
    long long p[N+1];
    for(int i=1; i<=N; i++) cin >> p[i];

    long long tp=0;
    for(int i=1; i<=N; i++){
        if(p[i]==i){
            tp++;
            i++;
        }
    }

    cout << tp << endl;

    return 0;
}

　このアルゴリズムだと説明書かなくていいよね。うん。というわけで、おしまい。