AtCoder Beginner Contest (ABC) 106 を解いてみた

AtCoder Beginner Contest (ABC) 106 の解法ログです。

問題文はAtCoder公式からどうぞ。

注:ソースコードの変数と解法中の文字は無関係です

A - Garden

解法

算数の問題にこういうのありましたね。道の重なりに注意。

ソースコード

int main(void) {
    int a, b;
    cin >> a >> b;
    cout << a * b - a - b + 1 << endl;

    return 0;
}

B - 105

解法

Nが小さいので、N以下の数で割ったあまりを全て見ていけばOK。

余り0になる場合が8つあるなら、その数は約数を8個持つ。

ソースコード

int main(void) {
    int n;
    cin >> n;
    int result = 0;
    for (int i = 1; i <= n; i += 2) {
        int count = 0;
        for (int j = 1; j <= i; j++) {
            if (i % j == 0)
                count++;
        }
        if (count == 8)
            result++;
    }

    cout << result << endl;

    return 0;
}

C - To Infinity

解法

1<=n<=K文字目に1以外の文字が存在する場合、5000兆日経つと、たとえK=10^18でも1以外の文字がKの場所に到達する(指数関数は一瞬で膨れ上がるので)。

そうでない場合は5000兆日経ってもK文字目は1のまま。

K文字目まで1が続くのなら1を、そうでないなら最初に出現した1以外の文字を出力する。

ソースコード

int main(void) {
    std::string s;
    int64_t k;
    cin >> s;
    cin >> k;
    for (int i = 0; i < k; i++) {
        if (s[i] != '1') {
            cout << s[i] << endl;
            return 0;
        }
    }
    cout << '1' << endl;

    return 0;
}

D - AtCoder Express 2

解法

愚直に解く場合、『クエリ(p,q)に対して、「全列車に対しp<=L,R<=qであるかを調べる」』という解法を思いつける。計算量はO(Q*M)なので間に合わない。

都市の数が少ないことに着目すると、train[L][R]=LからRに向かう電車の数という配列を作ることができそう。この配列を利用して「p<=L,R<=qを満たす場所を足していく」という解法を思いつける。計算量はO(QN^2)。……計算量増えてるじゃーん!!

しかし、「p<=L,R<=qを満たす場所を足していく」処理は累積和を利用することでO(N)に落とせる。ということで、先程の配列から累積和を作ってクエリに答えればAC。

ソースコード

(printf/scanfで書いてます)

int main(void) {

    int n, m, q;
    cin >> n >> m >> q;
    int train[501][501] = {};
    int cum[501][501]   = {};

    int m1, m2;
    for (int i = 0; i < m; i++) {
        scanf("%d%d", &m1, &m2);
        train[m1][m2]++;
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cum[i][j] = cum[i][j - 1] + train[i][j];
        }
    }

    int a, b;
    int answer;
    for (int i = 0; i < q; i++) {
        answer = 0;
        scanf("%d%d", &a, &b);
        for (int j = a; j <= b; j++) {
            answer += cum[j][b];
        }
        printf("%d\n", answer);
    }

    return 0;
}

その他

37分全完やったぜ。

AtCoder Beginner Contest (ABC) 105を解いてみた

AtCoder Beginner Contest (ABC) 105の解法をまとめてみます。今回はD問題が詳しめです。

問題文はAtCoder公式からどうぞ。

注:ソースコードの変数と解法中の文字は無関係です

A - AtCoder Crackers

解法

なるべく公平に配るなら、

• N%K==0のとき 差は0
• N%K!=0のとき 差は1

になる。

ソースコード

int main(void) {
    int n,k;
    cin>>n>>k;
    if(n%k==0){
        cout<<"0"<<endl;
    }else{
        cout<<"1"<<endl;
    }
 
    return 0;
}

B - Cakes and Donuts

解法

7ドルのドーナツを買う→残額が4で割り切れるならtrue、割り切れないならドーナツをもう一つ→……というふうにやっていく。

一応4ドルのケーキを買った後で判定する処理も書いたけど無駄だった。

ところでArcとかいう人はこの問題で2WAも出しているそうですよ。酷いですね。

ソースコード

int main(void) {
    int n;
    cin >> n;
    bool can_buy = false;
    if (n % 7 == 0 || n % 4 == 0) {
        can_buy = true;
    } else {
        for (int i = 0; i <= n; i += 7) {
            if ((n - i) % 4 == 0) {
                can_buy = true;
                break;
            }
        }
        for (int i = 0; i <= n; i += 4) {
            if ((n - i) % 7 == 0) {
                can_buy = true;
                break;
            }
        }
    }
 
    if (can_buy)
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
 
    return 0;
}

C - Base -2 Number

解法

10進数nを普通の2進数に変換する際の処理を考えてみると、

nが0になるまで{

(a-1ビットで表現できる最大の数)<nを満たすような最大のaを探す
2進数a桁目にフラグを立てる
n-=2^(a-1)

}を繰り返す

と言う風になる。これを応用して、

nが0になるまで{

n<(a-1ビットで表現できる最小の数)か(a-1ビットで表現できる最大の数)<nを満たすような最大のaを探す
-2進数a桁目にフラグを立てる
n-=(-2)^(a-1)

}を繰り返す

という処理を作ってみる。

ソースコード

const long long MAX_N = 1000000000;
const long long MIN_N = -1000000000;
 
int main(void) {
    int n;
    cin >> n;
    if (n == 0) {
        cout << 0 << endl;
        return 0;
    }
 
    bool is_on[101] = {};
    std::vector<long long> max;
    std::vector<long long> min;
 
    // max,minを計算
    //max[a]=(aBitで表現できる最大値)
    max.push_back(0);
    min.push_back(0);
    long long add = 1;
    int count     = 0;
    while (1) {
        count++;
        if (count % 2 == 1) {
            max.push_back(max[count - 1] + add);
            min.push_back(min[count - 1]);
        } else {
            max.push_back(max[count - 1]);
            min.push_back(min[count - 1] + add);
        }
        if (max[count] >= MAX_N && min[count] <= MIN_N)
            break;
        add *= -2;
    }
 
    int top_digit = 0;
    while (n != 0) {
        if (n > 0) {
            int digit = 1;
            while (max[digit] < n) {
                digit++;
            }
            is_on[digit] = true;
            if (top_digit == 0)
                top_digit = digit;
            n -= std::pow(-2, digit - 1);
        } else {
            int digit = 1;
            while (min[digit] > n) {
                digit++;
            }
            is_on[digit] = true;
            if (top_digit == 0)
                top_digit = digit;
            n -= std::pow(-2, digit - 1);
        }
    }
 
 
    for (int i = top_digit; i >= 1; i--) {
        if (is_on[i])
            cout << 1;
        else
            cout << 0;
    }
    cout << endl;
 
    return 0;
}

D - Candy Distribution

解法

累積和を計算した後、累積和のそれぞれの項に対してMで割った余りを計算。 Mで割った余りがiであるような項がn個あるなら、それらの項から2つを選択すると条件を満たす和が得られる。個数はn C 2。これをそれぞれのiに対して計算することで答えが得られる。

実装

実装がきつかったので詳しめに書いてみる。

「余りがiであるような項の個数」をどう保持するか?

余りのパターンはM通り存在するから、配列を用意するとメモリが足りない。

公式PDFにもある通り、std::map系のコンテナを利用することになる。今回の実装はstd::multimapを利用している。キーを余り、値を累積和の項にして、count(i)で個数を取得する作戦。なおmap系を利用するのは今回が初めてな模様。

イテレータを最初から最後まで回して、前に見たキーと別のキーが出現したら計算用関数を呼び出す事にした(キーが順番通りに出現する必要があるのでunordered_multimapは使えない)。

unorderedの実装ってどうやるんでしょうね……。

組み合わせの数n C 2をどう計算するか?

ソースコードでコメントアウトした関数のように、階乗を利用して計算するとlong longでもオーバーフローしてREを吐く。階乗をなめたらいけない。

結局「n!を少しずつ計算→途中で(n-2)!か2!の因数で約分できそうだったら約分」というクッッッッソ醜いやり方で押し通した。

……と、ここまで書いたが実は全て罠。n C 2なら普通に(n-1)+(n-2)+...+2+1を計算するだけで済む。

これに気づいたのはACした後の話でしたとさ。

コンパイラによって異なる言語実装

GCC5.4.1、ローカル環境のClang(clang-902.0.39.2)だと、ローカル変数宣言時に自動で0初期化が行われる。

Clang 3.8.0だと初期化が行われないらしく、結果「ClangでコンパイルするとWAになる」という現象が発生していた。

とりあえず明示的にint hoge=0としておいた方が精神衛生上よろしいかも。

ソースコード

/*
long long factorial(long long n) {
    long long result = 1;
    for (long long i = 1; i <= n; i++) {
        result *= i;
    }
    return result;
}
 
long long combination(long long n, long long r) {
    long long result = factorial(n) / factorial(n - r) / factorial(r);
    return result;
}
*/
 
long long combination_improved(long long n, long long r) {
    long long d      = n - r;
    long long result = 1;
    while (n > 1 || d > 1 || r > 1) {
        if (n > 1) {
            result *= n;
            n--;
        }
        if (d > 1 && result % d == 0) {
            result /= d;
            d--;
        }
        if (r > 1 && result % r == 0) {
            result /= r;
            r--;
        }
    }
    return result;
}
 
int main(void) {
    long long n, m;
    long long count;//Clangだと初期化の必要あり
    long long cum[100001];
    std::multimap<long long, long long> mod_map; //(mod M,number)
    cin >> n >> m;
    long long m1;
    for (int i = 0; i < n; i++) {
        cin >> m1;
        if (i == 0)
            cum[i] = m1;
        else
            cum[i] = cum[i - 1] + m1;
    }
    for (int i = 0; i < n; i++) {
        mod_map.insert(std::make_pair(cum[i] % m, cum[i]));
    }
 
    int prev = m;
    for (auto itr : mod_map) {
        if (prev != itr.first) {
            if (itr.first == 0) {
                if (mod_map.count(0) >= 1)
                    count += combination_improved(mod_map.count(0) + 1, 2);
            } else {
                if (mod_map.count(itr.first) >= 2) {
                    count += combination_improved(mod_map.count(itr.first), 2);
                }
            }
        }
        prev = itr.first;
    }
 
    cout << count << endl;
 
    return 0;
}

おまけ

ABC105-D AC!!
やっと通ったああああ(画像はこれまで積み上げてきた屍の山です) pic.twitter.com/1ui6LwKflJ

— ｱｰｸ@std::mapを使え (@arcslab123) August 12, 2018

散っていったコードに敬意を。(?????)

Mujin Programming Challenge 2018 を解いてみた

無人コン(参加者800人以上)の解法メモです。

問題文はAtCoder公式からどうぞ。

注:ソースコードの文字と解法中の文字は無関係です

A - コンテスト名

文字列MUJINとSを比較するだけ。

ソースコード

int main(void) {
    std::string s;
    std::string ans;
    cin >> s;
    ans = "MUJIN";
    for (int i = 0; i < 5; i++) {
        if (ans[i] != s[i]) {
            cout << "No" << endl;
            return 0;
        }
    }
    cout << "Yes" << endl;

    return 0;
}

B - セキュリティ

一文字ずつ読んでシミュレート、0になったらYesを返して即return 0。

一番最初に0人だった(A==0)場合もYesになることに注意。

ソースコード

int main(void) {
    cout << std::fixed << std::setprecision(10);
    int a;
    cin >> a;
    std::string s;
    cin >> s;

    if (a == 0) {
        cout << "Yes" << endl;
        return 0;
    }

    for (int i = 0; i < (int)s.size(); i++) {
        if (s[i] == '+') {
            a++;
        } else {
            a--;
        }
        if (a == 0) {
            cout << "Yes" << endl;
            return 0;
        }
    }
    cout << "No" << endl;

    return 0;
}

C - 右折

解けてないです><

あるマスで右折するルートの総数は、

左、上、右、下に(そのマスを除いて).がa,b,c,d個並んでいた場合a*d+b*a+c*b+d*c=(a+c)*(b+d)で求められる

このことを利用していけばO(NM)で解けるはずです(通らないよぅ……)。

D - うほょじご

解法

準備

数の組に対して、

enum status { ns = 0, wj, wa, ac };
//ns(No Submission)は未確認
//wj(Waiting for Judging)は確認中
//wa(Wrong Answer)は無限回操作ができないと確定
//ac(Accepted)は無限回操作ができると確定

を定義する。

status grid[x][y]=(x,y)のstatusとしておく。

初期状態では(0,n)(n,0)(nは任意の整数)のみwa、その他はns。

探索

あるnsの数の組(x,y)に対して、とりあえず一回操作をしてみる。

操作後の数の組(a,b)の状態によって、以下のことを行う。

grid[a][b]==nsの場合

grid[a][b]=wjとして、さらにstd::vector<std::pair<int, int>> vecに数の組をpush_back()しておく(後で役に立つ)。 vecは「探索中に通過したwjの状態の記録」として考えてください。

その後、(a,b)をもう一度操作。

grid[a][b]==waの場合

waになっている組になったら、その数の組が向かう先は(0,n)か(n,0)しかない。

探索中に通った数の組についても同じことが言える。

vecに保存しておいたすべての数の組(s,t)に対して、grid[a][b]=waにする。(vecに保存しないでgrid[][]を全探索すると時間が掛かるが、vecに保存すると計算量を落とせる)

grid[a][b]==ac、grid[a][b]==wjの場合

探索中にwjにたどり着いた場合、以降は無限回操作ができる。

また、無限回操作ができると確定した状態にたどり着いた場合、無限回操作ができる(それはそう)。

探索中に通った数の組は無限回操作が可能、と言えるので、vecに保存しておいたすべての数の組(s,t)に対して、grid[a][b]=acにする。

仕上げ

あとはgrid[x][y]==acになっている場所を数えて終了。

ソースコード

void dp_search()となっていますが、DPと言えるかは人それぞれだと思います。

enum status { ns = 0, wj, wa, ac };

int n, m;
status grid[1000][1000];

int rev(int x) {
    int a, b, c;
    int reverse;
    if (x >= 100) {
        a = x / 100;
        x -= a * 100;
        b = x / 10;
        x -= b * 10;
        c = x;
        reverse = c * 100 + b * 10 + a;
    } else if (x <= 9) {
        reverse = x;
    } else {
        b = x / 10;
        x -= b * 10;
        c = x;
        reverse = c * 10 + b;
    }
    return reverse;
}

void dp_search(int x, int y, std::vector<std::pair<int, int>> vec) {
    if (grid[x][y] == wa) {
        //終了措置
        for (int i = 0; i < vec.size(); i++) {
            int a = vec[i].first;
            int b = vec[i].second;
            grid[a][b] = wa;
        }

    } else if (grid[x][y] == ac || grid[x][y] == wj) {
        //成功措置
        grid[x][y] = ac;
        for (int i = 0; i < vec.size(); i++) {
            int a = vec[i].first;
            int b = vec[i].second;
            grid[a][b] = ac;
        }
        return;
    } else {
        grid[x][y] = wj;
        if (x < y)
            x = rev(x);
        else
            y = rev(y);
        if (x < y)
            y -= x;
        else
            x -= y;
        vec.push_back(std::make_pair(x, y));
        dp_search(x, y, vec);
        return;
    }
}

int main(void) {
    cout << std::fixed << std::setprecision(10);
    cin >> n >> m;

    for (int i = 0; i <= 999; i++) {
        for (int j = 0; j <= 999; j++) {
            grid[i][j] = ns;
        }
    }
    for (int i = 0; i <= 999; i++) {
        grid[0][i] = wa;
        grid[i][0] = wa;
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (grid[i][j] == ns) {
                std::vector<std::pair<int, int>> vec;
                vec.push_back(std::make_pair(i, j));
                dp_search(i, j, vec);
            }
        }
    }

    int answer = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (grid[i][j] == ac) {
                answer++;
            }
        }
    }
    cout << answer << endl;
    return 0;
}

これ以降

やってません

まとめ

時間内では2完でした。

腕、落ちてないか?? 青になれるのか???

ABC072/ARC082を解いたので記録を残す

だいぶ昔のやつですが、ABC072/ARC082のA~D問題を解いたので記録を残します。

問題文はAtCoder公式からどうぞ。

A - Sandglass2

ans=x-tをして、ans>=0だったらそのまま出力。それ以外だったら0を出力。

int main(void)
{
    int x, t;
    cin >> x >> t;
    int answer = x - t > 0 ? x - t : 0;
    cout << answer << endl;
 
    return 0;
}

B - OddString

一文字飛ばしで文字を足していく。実装ゲー。

int main(void)
{
    std::string s;
    std::string answer;
    cin >> s;
    for (int i = 1; i <= (int)s.size(); i++)
    {
        if (i % 2 == 1)
        {
            answer += s[i - 1];
        }
    }
    cout << answer << endl;
 
    return 0;
}

C - Together

数はかかになれる。

数に対して、count[x-1]++; count[x]++; count[x+1]++;をしていった後、どのcount[]が最大の値かを調べればOK。

イメージとしては「長さnの直線上に積み木を3つずつ積んでいく」感じ。一番高く積み上がった場所が答え。

int main(void)
{
    int n;
    int count[100000] = {};
 
    cin >> n;
    int m1;
    for (int i = 0; i < n; i++)
    {
        scanf("%d", &m1);
        count[m1]++;
        if (m1 - 1 >= 0)
            count[m1 - 1]++;
        if (m1 + 1 < 100000)
            count[m1 + 1]++;
    }
 
    int max = 0;
    for (int i = 0; i < 100000; i++)
    {
        if (count[i] > max)
            max = count[i];
    }
 
    cout << max << endl;
 
    return 0;
}

D - Derangement

である所をt,そうでない所をfとする。

ffとなっている所をスワップするとttにできる。

また、ftとなっている所をスワップしてもttにできる(数は1つずつしかないため、スワップ後にtがfになってしまうことはない)。

貪欲的に「fが見つかったら右隣とスワップして、さらに右隣の場所から検索を再開する」という操作をしていけばいい(自分のソースコードだと無駄な処理をしています)。

int main(void)
{
    int n;
    int answer = 0;
    int m1;
    std::vector<int> number;
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        scanf("%d", &m1);
        number.push_back(m1);
    }
 
    for (int i = 0; i <= n; i++)
    {
        if (number[i] == i + 1)
        {
            if (i + 1 < n && number[i + 1] == i + 2)
            {
                answer++;
                i++;
            }
            else
            {
                answer++;
            }
        }
    }
 
    cout << answer << endl;
 
    return 0;
}

C++＆Siv3Dでリアルタイム動画加工ソフト作ったった

Arcです。突然ですが、謎ソフト作ってみました。

機能追加しやすい設計にはしましたが、機能が足りてないです。動作も重いです。クオリティには期待するな。

名付けてRealtimeMovieHacker。厨ニっぽい

製作経緯

• CombNaf3のネタを何か持ってみたかった
• Siv3Dを使ってみたかった
• 高校生のうちにプログラミングで何か「形あるモノ」を作ってみたかった

こんな感じですね。

ソフト概要

キーボード操作によって、Webカメラで取得した映像をリアルタイム加工して出力します。

このように動作します。

RealtimeMovieHacker v0.1.1の動作映像です pic.twitter.com/qyO4Hh66v4

— ｱｰｸ@謎ソフト開発者 (@arcslab123) March 24, 2018

動作環境はWindows 7 SP1,8,8.1,10です。CPUはできるだけ高性能なものが望ましい。

macOSとLinuxには対応していません……が、いつの日か対応するかもしれません（後述）。

ダウンロード

ソフトウェア本体はGithubのReleasesからどうぞ。（無保証です） 一番上が最新版です。"Assets"の下の"RtMovieHacker_vX.Y.Z.zip"をダウンロード、展開してください。

ソースコードもGithubで公開しています。

使い方

1. RtMovieHacker.exeを起動する
2. Webカメラを起動する
3. キー操作などで映像にエフェクトを掛ける（詳細は付属のREADME.txt)

実装

ここからは技術的な話。

使ってる言語とかライブラリとか

全てC++14を利用しています。

また、外部ライブラリとしてSiv3Dを利用しています。

Siv3DはWindowsのみ対応。macOS/Linuxに対応するOpenSiv3Dが開発されていますが、現状だと機能が足りなかったので使いませんでした。機能が増えてきたらOpenSiv3Dを利用して移植するかも。

開発はVisual Studio 2015で行いました。

ルーチン

最初に、使用可能なWebカメラを全て起動します。

また、全てのエフェクタクラスをインスタンス化します。

後は以下の処理をずっと回すだけ。

カメラ切り替えキーが押されたらカメラを切り替える(ここの動作は不安定です)
カメラで新しいフレームを取得する
エフェクタ起動条件を満たしていたらエフェクタを起動する
エフェクタ停止条件を満たしていたらエフェクタを停止する
フレームにエフェクトを掛ける
フレームを出力する

エフェクタ管理の実装

std::list<std::reference_wrapper<Effecter>> effecter_disabled（停止しているエフェクタへの参照のリスト）、std::list<std::reference_wrapper<<Effecter>> effecter_enabled（起動しているエフェクタへの参照のリスト）という２つのリンクリストが核になっています。任意位置での削除操作を高速化したいのでstd::listを使用しました。

また、全てのエフェクタは、抽象クラスclass Effecterをpublic継承して実装しています。こうすることで、全てのエフェクタに必須な関数を一元管理できます。

再実装する必要のある関数は以下の通り。

• virtual bool needs_enable()(起動条件を満たしていたらtrue)
• virtual bool needs_disable()(停止条件を満たしていたらtrue)
• virtual void effect()(エフェクトを実行する)

また、全てのエフェクタにはcore_dataという構造体への参照が呼ばれます。core_data.imageを書き換えることで出力フレームが加工されます。

初期化処理として、全てのエフェクタクラスをインスタンス化します。次に、全てのエフェクタクラスへの参照をeffecter_disabledに入れます。

次に、effecter_disabled内の全てのインスタンスに対して、needs_enable()を呼び出します。trueならそのインスタンスをeffecter_enabledにpush_back()して、effecter_disabled側のインスタンスをerase()します。ここの削除操作の時短のためにstd::listを使用しました。ここの処理でつまづきました……。

次に、effecter_enabled内のすべてのインスタンスに対して、needs_disable()を呼び出します。以下、察してください。

で、effecter_enabled内のすべてのインスタンスに対して、effect()を呼び出します。これによってエフェクトが掛かります。

なんか操作が重いのでチューンアップする必要がありそうです（思い当たる節があったので、そのうち更新します）。v0.1.0で修正できました

なんでこんなことをしたのか

こう実装することによって、effecter_enabledの中身が「昔に起動したエフェクタ」を先頭にして並びます。effect()もこの順番に呼び出されるので、あるエフェクトに別のエフェクトを重ねる事ができます。決まった順番で「起動しているか判定→エフェクト掛ける」という方法だと、命令の並び順によってエフェクトを掛ける順番が決まってしまうので……。

エフェクタの作り方

"Effecter.h"にこんな感じで追記。

class <ClassName> :public Effecter{

public:
    <ClassName>(CoreData&);
    bool needs_enable();
    bool needs_disable();
    void effect();
    //その他エフェクタ内で使う関数
}

適当なcppファイルに関数を実装する。

#include<Siv3D.hpp>
#include"CoreData.h"
#include"Effecter.h"

<ClassName>::<ClassName>(CoreData& input_data) :Effecter(input_data){};

bool <ClassName>::needs_enable(){
    //起動条件を満たしたらtrueをreturnするように実装
}

//その他もろもろの関数を実装

"Main.cpp"、void Main()内にこんな感じで追記。

<ClassName> <InstanceName>(core_data);
effect_ctrl.push_to_disabled(<InstanceName>);

割と面倒くさい

感想

初めてプログラミングに触れた(プチコンっていう、DSiで動くBASIC環境でした)小学生の頃は、ちょっとした入力や条件分岐はできても「このサンプルゲームどうやって動いてるの……」っていう感じでした。

で、それから5年ぐらい。なんかそれっぽい（これは罠で、実用性皆無）ものができました。素直に嬉しい。

どんなに複雑なプログラムでも「入力」「処理」「出力」しか無いんですよね。ここらへんの「できるだけシンプルに捉える」考え方を持てたのは競プロ効果かもしれないです。

また、実装を通してc++の機能をたくさん学習しました。c++機能多すぎ

エフェクタは割と簡単に追加できるように実装してみました（そのつもり）。ちょっとずつ機能追加していけたら良いなあ。

最後に、このソフトの開発を実現してくれたSiv3D開発チームの方々に感謝申し上げます。

では。

更新履歴

20180325 動作映像をv0.1.1仕様に変更

AtCoder Beginner Contest (ABC) 090 / AtCoder Regular Contest (ARC) 091 レビュー

AtCoder Beginner Contest (ABC) 090 / AtCoder Regular Contest (ARC) 091 の個人的解法解説とレビューです。

今回はABC/ARCのC問題＆D問題のみとなります。

問題はこちらのAtCoder公式からどうぞ。

C - Flip,Flip, and Flip......

とりあえず解いてみる

最大のカード枚数は10^18。全部シミュレートしてると間に合わない。

実際に操作してみる。

カードの置かれているマスの四隅は4回操作される。最終的には表になる。

カードの置かれているマスの辺上（四隅を除く）は6回操作される。最終的には表になりる。

その他のマスは9回操作される。最終的には裏になる。

ということで、カードの枚数-辺上（四隅含む）にあるカードの枚数、つまりN*M-(2*N+2*M-4)を出力すれば良さげ。

……ほんとかな？

カード1枚だけ、つまりN=1 && M=1の状況だとどうなるだろうか。「四隅」「辺」が定義されないので、答えが変わってきそうな気がする。同様に、N=1 && M≠1の場合も「四隅」が定義されないのでマズそう。

コーナーケースがありそうなので、順に調べていく。

N=1 && M=1 のとき(「四隅」「辺」の定義が不可能)

1回操作されるので、1枚だけ裏になる。上記の式に当てはめてみると……そのまま使えそう。

N=1 || M≠1 のとき(「四隅」の定義が不可能)

端の2枚は2回操作される。最終的には表。

その他は3回操作される。最終的には裏。

つまり、M-2を出力すれば良い。上の式に当てはめてみると……1*M-(2*1+2*M-4)=-M+2になってしまう。

修正する

コーナーケースがあるので、以下のように修正。

if(N==1 && M!=1){ //コーナーケース
    cout<<M-2<<endl;
}else{
    cout<<N*M-2*N-2*M+$<<endl;
}

自分のソースコードだと無駄な条件分岐が……。

こんな感じで解けた。計算量はO(1)。

D - Remainder Reminder

ソースコードはこちら。

とりあえず解いてみる

愚直解は「1<=a,b<=Nを満たす組(a,b)に対して、a%b>=Kであるかを確かめる」と言った感じだろうか。計算量はO(N^2)。Nは最大10^5なので間に合わない。

せめてO(N)ぐらいには落としたいところ。ということで、「組の一方の値が与えられたとき 、有り得るもう一方の値の個数をO(1)で求める」アルゴリズムを作ってみる(これなら、「与える一方の値」を1からNまで動かして和を取ることでO(1*N)で解ける)。

計算量を削っていこう

bを「与える」と上手く行ったので解説。

ARC091-D_解説

表は、N=10の設定で「aをbで割った余り」を示している。余りがK=2以上のところには色が塗ってある。

値には、長さbの周期が見られることが分かる（表の赤線を参照）。

また、b>Kを満たすbについてのみ考えれば良いことが分かる。

表の中で「周期」がいくつ見られるかを「sequence」に記載した。この値はマス数/周期の長さ、すなわち(1+N)/bで求められる。

「周期」に含まれるマスの中で、余りがK以上のマスがいくつ有るかを「sequenceによるanswer」とした。この値はsequenceの値*一周期に存在する余りK以上のマスの数、すなわちsequence*(b-K)で求められる。

また、「周期」に含まれないマスの中で、余りがK以上のマスがいくつ有るかを「remain」とした。この値は周期に含まれないマスの数-K、すなわち(1+N-sequence*b)-Kで求められる（負数になることがあるので、その場合は0扱い）。

以上の計算をすることで、「bの値が与えられたとき 、有り得るaの値の個数をO(1)で求める」ことができた。bをK+1からNまで動かして和をとれば、O(N)で解ける。

K=0のときがコーナーケース。この場合はN*Nを出力しておく。

まとめ

考察回&コーナーケース回避回だったなぁという印象。1WA吐きましたが、50分で二問解けました。

よっしゃよっしゃ
rate 899->986(Highest)
perf 1453(Highest) pic.twitter.com/EiznrbLePT

— Arc@競プロ (@arcslab123) March 11, 2018

最大パフォ更新。最近は調子がいい。

競技プログラミングを始めよう

追記: 2020年版を書き直しました

Arcです。今日はレビュー記事じゃない事を書きます。

新年度、なにか新しいことを始めたいと思っているそこのアナタに向けた布教記事です。

対象読者層

• 問わず

できるだけ専門用語を使わずに書いていこうと思います。

競技プログラミングって何それおいしいの？

人に説明するのが難しいんですが、僕が思うに競技プログラミング(以下「競プロ」)は「プログラミングをして様々な問題を解くスポーツ」です。食べ物ではありません。

競技性はもちろんあるし(競技プログラミングなんだからそれはそう)、生涯スポーツとしても有用です。

競プロには大きく分けて2つの楽しみ方があります。1つは「過去問を解く」こと。もう1つは「コンテストに参加する」ことです。

コンテストは「競プロの大会」。与えられた問題を解くプログラムを速く作る事が求められます。「解いた問題の難度」、「問題を解くのに掛かった時間」で順位が決められます。

また、過去にコンテストで出題された問題の多くは（全ては？）そのまま公開され続けるので、様々な問題を解きまくるのも楽しいです。

競プロの効果は？

C++が身につく

競プロではこのプログラミング言語が主流です。世界で幅広く使われています。

C++は「C言語」の上位互換言語なので、初めにC言語を学習してからC++へステップアップする、というやり方でもOK。僕はそうしました。C++はメチャクチャ複雑な言語なので、最初からC++だと言語習得で挫折しそう……。C言語はC++よりはシンプルです。

高度なプログラミング能力が身につく

競プロer(競プロをする人のこと)は世の中の平均的エンジニアと比べて相当高いプログラミング能力（特にアルゴリズム分野における能力）を持っているようです。ハイレベルな能力が自然と身につきます。

「競プロ界の『下の上』ぐらい」だと思っている自分がどこらへんのポジションにいるのかは分からない。

楽しい！！

最終的にはここに帰着します。高難度問題を解けたときの快感はたまらない。

どんな問題が出るの？

よしよし、ここまで読んでくれたということは興味を持ってくれたということですね？嬉しいです。具体的にどんなことをしているのか紹介します。

簡単な問題

たとえばこんな問題。

競プロの問題は、「時間制限・メモリ制限」「問題文」「入力」「出力」「制約条件」から成り立っています。

「問題文を読む」→「入力で与えられるデータを適切に処理して、形式通りに出力するプログラムを書く」→「書いたプログラムを提出する」というのが一連の流れです。

また、入力される値は「制約条件」に従っています。これが無いとメチャクチャ大きな値を入れられてしまうので……。

さらに、「時間制限」「メモリ制限」を守ったプログラムを書かなくてはなりません。

「時間制限2秒」の場合、プログラムを実行してから2秒以内に出力する必要があります。効率の悪いプログラムを書くと時間制限に引っかかってしまいます。競プロは効率化との戦い。

「メモリ制限128MB」の場合は、変数を格納する場所であるRAMメモリの使用量を128MB以内にする必要があります。専門用語が漏れてしまった。とりあえず理解できなくても大丈夫です（そのうち理解する必要はありますが）。

では、この問題について考えてみましょう。

入力Aと入力Bを受け取る

(A*B)の値と、(A*2+B*2)の値を出力する

というプログラムを書けば良さそうですね。

この処理を記述して、サーバーに提出すると、サーバーがプログラムを実行してくれます。しばらく待つと、正解したかどうかが通知されます。「AC」と通知されたら正解。やったね。

難しめの問題

こんな問題も出ます。

初見で解けたら才能あります。保証します。

ほとんどの人はわからないと思います。僕も全然解けませんでした。でも、なんだかんだ言って解けるようになります。解けます解けました。

難しい問題をあーだこーだ考察するのが競プロの醍醐味、だと個人的には思っています。

どこで競プロができるの？

ざっくり分けると「ウェブ」と「オンサイト」です。

ウェブ

ブラウザでアクセスする形式。有名なサイトを幾つか紹介します。

AtCoder （たぶん）日本最大手の競プロサイト。毎週末にコンテストが行われています。僕も参加しています。いくつかレビュー記事書いてるので読んでね（露骨な宣伝）

Aizu Online Judge 通称AOJ。会津大学が運営している競プロサイト。後述の学生向けオンサイトコンテストで出題された過去問が充実しています。いわゆる「典型問題」もたっぷり。

yukicoder 問題を「出題できる」ことが特徴。僕も何か作ってみたい。

オンサイト

参加者が会場に集まって行うタイプ。「ウェブ上で予選コンテスト」→「オンサイトで本選コンテスト」といったパターンが多いです。

学生向けオンサイトコンテストを紹介します。

日本情報オリンピック 通称JOI。日本の高校生以下競プロerが参加できるコンテスト。ウェブで予選を行った後、最大80人ぐらいが本選へ出場できます。本選上位20人は「春合宿」に参加できます。

国際情報オリンピック(リンクは2018年日本大会) 通称IOI。世界屈指の高校生以下競プロerが出場するコンテスト。日本からは、前述の「春合宿」でいい成績を収めた上位4人（2018年のみオープン参加枠4人追加）が出場できます。

ACM国際大学対抗プログラミングコンテスト 通称ACM-ICPC、もしくはICPC。大学生競プロerが参加できるコンテスト。チーム戦であることが特徴。こちらも多くの予選を突破しないと世界大会には出られない。出てみたいです。

この他にも、IT系企業がオンサイトコンテストを主催したりしています。

必要なものは？

最低限、インターネットに繋がるPC1台でOK。ソフトウェアはいろいろインストールしないといけませんが……。

あとは問題考察用に紙とペン、リフレッシュ用に飲み物とかお菓子とか。

競プロしてみたい！

やったぜ。

そんなあなたに僕のオススメ学習法を伝授します（あくまで個人の意見ですが）。

以下、Amazonへのリンクを張りまくりますが、アフィリエイトでは無いことを一応書いておきます。

プログラミングの環境を整える

まずはPCでC言語・C++を扱えるようにセットアップします。

……といっても、ここらへんについては「ググれ」としか言えません。使っているPCによってやり方が異なるので……。

流石にこれだと投げやりすぎるので、いくつかアドバイス。最低限必要なソフトウェアは

• ソースコードを編集する「テキストエディタ」
• ソースコードを機械語（PCが直接実行できる形)に変換する「コンパイラ」

です。以上2つが1つのソフトウェアとしてまとまっている「IDE（統合開発環境）」というのもあります。

使っているPCのOSとかにあわせて好きなものをインストールしてください。

とりあえずC言語を使えるようにする

前にも書きましたが、最初からC++を使おうとすると挫折する危険性があります。とりあえずCから始めましょう。

おすすめの教材はこちらの苦しんで覚えるC言語。だいぶ怪しげなタイトルですが、中身は非常に良いです。

よくあるC言語入門本だと「おまじない」とかいうファンタジーワードが羅列されているんですが、この本はそういった類の言葉を一切使わずにきちんと説明してくれることが特徴。「苦しい」と思うことはあっても、その後の理解度が半端じゃない。

「苦しんで覚えるC++」があったらC++から始めても問題ない、と言いたくなるぐらいの名著です。

簡単な問題を解いてみる

大体分かってきたな、と思ったら今度はアウトプットしましょう。全て理解してから、じゃなくても大丈夫。

基本的なことを学べば、簡単な問題は解けるようになります。

AtCoder Beginner Contest(通称ABC)にも出てみましょう。

(20180315 追記)

ここらへんのレベルまで辿り着いた方には、こちらのAtCoder に登録したら次にやること ～ これだけ解けば十分闘える！過去問精選 10 問 ～(drkenさん著)を読んでおくことをオススメします。AtCoder登録からABC参加の利点、重要過去問のピックアップ＆解説までサポートしてくれます。

(追記ここまで)

アルゴリズムに手を出す

解けない問題に直面し、解説を読んでも「幅優先探索」「累積和」「動的計画法」とかいう謎ワードが並んでいて分からない……。

そういった感じになってきたら、「アルゴリズム」「データ構造」について勉強する必要があります。ようこそ競プロの真髄へ。

「アルゴリズム」とは、「プログラミングで問題を解くための手段」の事です。

「データ構造」とは、「プログラミングで効率的にデータを処理するための形式」の事です。

とりあえずこちらのなっとく！ アルゴリズムを読んで雰囲気を掴みましょう。この本も名著だと思います。すげーわかりやすい。イラストがたくさんあるので視覚的にアルゴリズムを学べます。中身のソースコードはPythonという言語で書かれていますが、そこは分からなくてもなんとかなります。

今度はこちら、プログラミングコンテストチャレンジブック。通称「蟻本」。競プロerで持っていない人はいないんじゃないかと思うぐらいの「聖書」。主要アルゴリズムとデータ構造が網羅されています。

また、僕は持っていないのですが、プログラミングコンテスト攻略のためのアルゴリズムとデータ構造も良さげです。借りて読んでみた印象だと「なっとく！ アルゴリズム」の内容をもう少し深めた感じ。

C++に手を出す

アルゴリズムに手を出すと同時に、C++の習得も目指していきます。

でも、「Cを学んだ人向けのC++入門本」を見たことがないんですよね……。僕はオンライン資料を読みまくることで乗り切っちゃいました（嘘です）

(20180306 追記)

オンライン資料で乗り切ろうとしていますが、そもそもC++を完全に理解するのは不可能レベルだという話もちらほら。

使う機能だけ理解しておけばいいと思います。

(追記ここまで)

ちなみにC言語でもJOI予選は突破できますよ。僕がその一人です。C++の方が圧倒的に便利だということに気づいたのは突破後の話。

この後

あとはひたすらアルゴリズムとデータ構造とC++の勉強して、コンテストに出まくるだけです。

これ以上書けと言われても書けない(´・ω・｀)

どんどんコンテストに参加して実力を付けていきましょう。

まとめ

新年度の幕開けが近いということで、新生活のお供になるかもしれない記事を書いてみました。長文にお付き合い頂きありがとうございます。

以上で布教は終わり。この記事が、あなたが競プロの魔境に迷い込む世界に踏み出すきっかけになる事を祈ります。

更新情報

20180305/投稿

20180306/「プログラミングの環境を整える」追加、「C++に手を出す」追記、その他誤字修正

20180315/「簡単な問題を解いてみる」追記