コンテスト成績

　パフォーマンスは533で、レーティングは+23。とりあえず茶色に戻るまで順調に推移しても後5回くらいは掛かるかな。

A - Long Loong

　AC：2分30秒

　計算量：$O(N)$

　必要知識：繰り返し処理

　最初はstringの文字結合をしようと考えたけど、単純に標準出力に出した方が早いことに気が付いて軌道修正。

#include <iostream>
using namespace std;

int main() {
    int X = 0;

    cin >> X;
    cout << "L";

    for (int i = 0; i < X; i++) {
        cout << "o";
    }

    cout << "ng" << endl;

    return 0;
}

B - CTZ

　AC：22分30秒

　計算量：$O(\log N)$

　必要知識：繰り返し処理、2進数

　10進数を2進数に変換する方法を忘れていた。検索すればすぐに出るけど、自力で思い出したかったので時間が掛かった。公式の解説を見ると、シフト演算を利用した賢い方法をしていた。

　ああいった方法がパッと出るようになりたいものだ。その為には色々な問題を解いて知識の引き出しを増やさないと。

#include <iostream>
using namespace std;

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

    int count = 0;
    while (N % 2 == 0) {
        count++;
        N /= 2;
    }

    cout << count << endl;

    return 0;
}

C - Even Digits

　AC：1時間10分

　計算量：$O(\log N)$

　必要知識：繰り返し処理、分岐処理、進数変換

　最初の方針は、N番目の整数を表示するには何桁が必要かを求めた後、その桁の最小値から順に計算していくというものだった。

　1桁は5通り、2桁は25通り、3桁は125通りで......といった具合で考えたけど、最上位の数字は0以外でないといけない点を考慮する必要があったり、桁数が増えるにつれて計算量が膨大になりそうだったり、その方針では実装が難しそうだったからやめた。

　5進数に変換して処理すればいいじゃないか、ということに気が付いたのは最後の15分くらいで慌てて実装。細かいことを考える余裕が無かったので、とりあえず実装して入力例を試しながらデバッグ。

　N=1の場合がうまくいかないけど、それはもう固定的に実装してしまえという感じでコーディング。時間ギリギリでAC。

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

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

    if (N == 1) {
        cout << "0" << endl;
        return 0;
    }

    string str = "";
    N--;
    while (N != 0 ) {
        long long x = N % 5;
        if (x == 0)
            str += "0";
        else if (x == 1)
            str += "2";
        else if (x == 2)
            str += "4";
        else if (x == 3)
            str += "6";
        else if (x == 4)
            str += "8";

        N /= 5;
    }

    reverse(str.begin(), str.end());
    cout << str << endl;

    return 0;
}

夢は遠き赤色

【競プロ日記】ABC336

コンテスト成績

A - Long Loong

B - CTZ

C - Even Digits