【競プロ日記】ABC337

　今回もC問題までは解くことが出来た。前回と同様にD問題以降は見てすらいない。

コンテスト成績

　せめてパフォーマンスは500くらいは出したいものだ。

A - Scoreboard

　AC：5分12秒

　計算量：$O(N)$

　必要知識：-

　チーム毎の得点を単純に計算して比較すればいい。最初に得点の一覧を配列に保存してから計算しようと考えてしまい時間をロス。

#include <iostream>
using namespace std;

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

    int sum_x = 0;
    int sum_y = 0;
    for (int i = 0; i < N; i++)
    {
        int X, Y;
        cin >> X >> Y;
        sum_x += X;
        sum_y += Y;
    }

    string ans;
    if (sum_x == sum_y) 
        ans = "Draw";
    else if (sum_x > sum_y)
        ans = "Takahashi";
    else
        ans = "Aoki";

    cout << ans << endl;

    return 0;
}

B - Extended ABC

　AC：22分30秒

　計算量：?（正規表現のマッチング判定に要する計算時間を知らない）

　必要知識：正規表現

　拡張 ABC 文字列の定義に従って実装しようかと思ったけど、正規表現を使えば楽だなと思ったので正規表現を使用。C++でどう実装するのか分からなかったので、調べながら実装。

　正規表現の知識も不足していることを実感した。私の実装では「((A*)(B*)(C*))」と書いた、シンプルに「A*B*C*」でいいみたいだ。

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

int main()
{
    string S;
    cin >> S;

    regex reg(R"((A*)(B*)(C*))");
    string ans;
    if (regex_match(S, reg))
        ans = "Yes";
    else
        ans = "No";

    cout << ans << endl;

    return 0;
}

C - Lining Up 2

　AC：1時間0分

　計算量：$O(N)$

　必要知識：双方向リスト

　片方向リストの形で情報が与えられている。リストの方向を遡る形で繰り返し処理をすれば答えが得られそうだ、というわけでそれを実装しようとして時間が大いに掛かってしまった。

　構造体を使って人の値、直前/直後の人の値を管理する方針で実装。ふんわりとした理解だったけれど、のんびりする時間も無かったのでテスト値を入れながらデバッグ。

　どうすればいいか、ということは割と早めに分かっていたが実装に時間が掛かったパターン。変数名もよろしくなく、デバッグが面倒だった。しかしまあ、急ぐ中でも変数名の付け方くらいはちゃんとしとけばよかった。

　とりあえずACを通したいという思いで実装していた結果、プログラムは見れたものではなくなってしまった。

#define _GLIBCXX_DEBUG

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

struct PERSON {
    int number;
    int pre_num;
    int next_num;
};

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

    int first;
    vector<PERSON> A(N + 1); 
    vector<int> v(N + 1, 0);
    for (int i = 1; i <= N; i++) {
        int pre;
        cin >> pre;
        A[i].number = i;
        A[i].pre_num = pre;

        if (pre == -1)
            first = i;
        else
            v[pre] = 1;
    }

    int index;
    for (int i = 1; i <= N; i++) {
        if (v[i] == 0)
            index = i;
    }

    for (int i = 1; i <= N; i++) {
        int next_index = A[index].pre_num;
        if (next_index == -1)
            continue;
        A[next_index].next_num = index;
        index = next_index;
    }

    int idx = first;
    for (int i = 1; i <=N; i++) {
        cout << A[idx].number << " ";
        idx = A[idx].next_num;
    }

    cout << endl;

    return 0;
}

【競プロ日記】ABC336

　2023-11-04のABC327以来、久々に参加した。C++でプログラミングしているのだけど、久し振りにコーディングを始めたら色々と忘れている有様だ。

　さて、今回はC問題まで解くことが出来た。D問題以降は見てすらいない。C問題までの感想としては、今回は進数変換がテーマだったのかな。

コンテスト成績

　パフォーマンスは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;
}

いつまでも競プロ初心者

　AtCoderに初めて参加したのは、一体いつだったろう。初めて参加したのは2014～2016年のどこかだった筈。多分 2014 年だったような気がするけど、10年近くも昔のことだからろくに覚えていない。

　覚えているのは今も昔もABCのB問題、よくてC問題までしか解くことが出来てないということ。情けないことに、私は競プロに関して10年も成長していないようだ。典型問題を解くことも、よく使われるアルゴリズムも、データ構造も学ばなかったのだから仕方がない。

　最初に作ったアカウントは削除してしまった。その後も作っては消してを何度か繰り返した。IT業界の端くれに転職したので、いつまでもC問題までしか解くことが出来ないのも何だかなぁ、と思い去年の6月頃にまた登録した。

　茶色にまでは到達したのだけど、参加登録して参加しなかったらレーティングがだだ下がりしてしまった。とりあえず、今年は少し真面目に競プロに取り組んでみようと思った次第である。まあ、新年に抱いた志というのは、時間経過と共に消えていくものだけど。

　目標はもちろん赤色......などと妄言を吐ける程に自分を過信はしていない。とりあえず、今の目標はRating 1000で緑色になることかな。年内で達成できればいいけれど、どうなるかな。