【競プロ日記】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;
}