【競プロ精進ログ】【2021/03/08】ABC158: D ABC157: C

競技プログラミングのための精進履歴をブログ形式で残していきます。

目標は AtCoder 水色！
今のレートは茶色です。

本日の精進ツリーは以下のとおり。

精進ツリー

ABC158: D – String Formation
ABC157: C – Guess The Number
まとめ

ABC158: D – String Formation

ABC158 より、 ABC158: D – String Formationを解きました。
難易度は茶色。

解法自体は一瞬で導けた。
始めはstringに連結しようかと考えていたものの、末尾はともかく前方に文字を追加する時の計算量が O(N) になりそうだったので、連結リストを利用することに。

双方向リストを自力で実装しようとしたけど C++ のライブラリがあることを思い出したので、 std::list を利用する方針に変更。
ライブラリ便利。

list のイテレータの扱いで若干ミスったけど問題なく AC。

提出コードはこちら。

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define SIZE_OF_ARRAY(array) (sizeof(array) / sizeof(array[0]))
using namespace std;

#define MAX 100010
#define NIL -1

using lint = long long int;

/*************************************************************************************
NOTE: 

・前後反転もしくは文字列の先頭か末尾に文字を挿入する
・文字列の反転には、O(N)が必要なので、シンプルに実装するとO(N^2)になる 
・文字列の反転は2回で元に戻る
・実際に反転させるのは最後だけにするとよさそう
*************************************************************************************/

/*************************************************************************************
LOGIC: 
1. 文字列の反転状態をtoggleとして管理
2. 先頭に文字を挿入する場合、もしtoggleが0 なら先頭に挿入、
   → 文字列を先頭に挿入する場合、O(N)かかるので連結リストにする
*************************************************************************************/

list<char> lst;

void init(string S)
{
    for (lint i = 0; i < S.length(); i++)
    {
        lst.push_back(S[i]);
    }
    return;
}

int main()
{
    string S;
    int toggle = 0;
    cin >> S;

    lint Q, q;
    cin >> Q;
    int f;
    char c;

    init(S);

    for (lint i = 0; i < Q; i++)
    {
        cin >> q;
        if (q == 1)
        {
            toggle = toggle ^ 1;
        }
        else
        {
            cin >> f >> c;
            if (((f == 1) && (toggle == 1)) || ((f == 2) && (toggle == 0)))
            {
                lst.push_back(c);
            }
            else
            {
                lst.push_front(c);
            }
        }
    }

    if (toggle)
    {
        auto i = lst.end();
        i--;
        for (auto it = i; it != lst.begin(); it--)
        {
            cout << *it;
        }
        cout << *lst.begin();
    }
    else
    {
        for (auto i = lst.begin(); i != lst.end(); i++)
        {
            cout << *i;
        }
    }
    cout << endl;
    return 0;
}

ABC157: C – Guess The Number

ABC157 より、 ABC157: C – Guess The Numberを解きました。
難易度は茶色。

こちらも解法は一瞬だったものの、ちょっとした見落としで WA だしてしまいました。

「各桁の条件に異なる指定がされている」かつ「先頭が 0 になっている」条件が NG だと思っていたが、正確には、N が 1 の時は先頭が 0 でも問題ないことを失念していました。

条件修正したら AC。

提出コードはこちら。

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define SIZE_OF_ARRAY(array) (sizeof(array) / sizeof(array[0]))
using namespace std;

#define MAX 100010
#define NIL -1

using lint = long long int;

/*************************************************************************************
NOTE: 

・N桁の10進数で、左からs番目がcであるものの最小のもの
・Nの制約が3なので、各桁ごとに場合分けができる
・sの取りうる範囲も1~3なので、各範囲ごとに場合わけができる
・sが重複し、cが異なるものがある場合はNG
・指定のない場合は、ワイルドカードでその桁に入れうる最小の値を選ぶ
*************************************************************************************/

int main()
{
    lint N, M;
    cin >> N >> M;
    vector<lint> vec(N + 1, -1);
    vector<lint> check(4, 0);

    if (N == 1)
    {
        vec[1] = 0;
    }
    else if(N == 2)
    {
        vec[1] = 1;
        vec[2] = 0;
    }
    else
    {
        vec[1] = 1;
        vec[2] = 0;
        vec[3] = 0;
    }
    
    lint s, c;
    rep(i, M)
    {
        cin >> s >> c;
        if ((check[s] != 0) && (vec[s] != c))
        {
            cout << -1 << endl;
            return 0;
        }
        check[s] = 1;
        vec[s] = c;
    }

    if (N > 1)
    {
        if (vec[1] == 0)
        {
            cout << -1 << endl;
            return 0;
        }
    }

    for (int i = 1; i < N + 1; i++)
    {
        cout << vec[i];
    }
    cout << endl;
    return 0;
}