Yuulis.log

トンネルを抜けるとそこは参照エラーであった。

【AtCoder】ABC 350 A - Past ABCs | 茶コーダーが解くAtCoder

AtCoder ABC 灰Diff Diff: ~99 キャスト プログラミング

atcoder.jp

実行時間制限: 2 sec / メモリ制限: 1024 MB / Difficulty: 32

問題概要

長さが6で、先頭3文字がABC、後ろ3文字が数字の文字列 S が与えられる。 S が以下の348個の文字列 :

ABC001, ABC002, ..., ABC314, ABC315, ABC317, ABC318, ..., ABC348, ABC349

のいずれかに等しいかどうかを判定せよ。

制約

  • 問題文の通り。

考察

まずは S の後ろ3文字を分割して数字に直そう。S.substr(3)で S の3文字目以降の連続部分文字列を取得し、stoi()でint型変数 (ここではxとした) へキャストしている。このとき0埋めは無視されるので、文字列の003は数字の3となる。

続いて、 1 \leq x \leq 349 (ただし, x \neq 316) であるかを判定する。なお、0は条件を満たさないので注意。

コード

#include <bits/stdc++.h>
using namespace std;

// ======================================== //

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

    int x = stoi(S.substr(3));
    if (x != 316 && 1 <= x && x <= 349)
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
}

atcoder.jp

実装時間: 5分以内

【AtCoder】AtCoder Beginner Contest 350（Promotion of AtCoderJobs） - 参加記 | 茶コーダーが解くAtCoder

AtCoder コンテストまとめ ABC プログラミング

atcoder.jp

コンテスト時間: 2024-04-20(土) 21:00 ~ 2024-04-20(土) 22:40 (100分)

A - Past ABCs

Difficulty: ???
解答時間: 5:48 (1WA)

  • ABCxxxという形式の文字列 S が与えられる。xxxの部分が001, 002, ..., 315, 317, ..., 349のいずれかであるかを判定せよ。
  • xxxの部分を整数型変数 x に変換し、 1 \leq x \leq 349 (x \neq 316) であるかを判定するだけ

...声を大にして言う。ABC000は存在しない。

yuulis.hatenablog.com

B - Dentist Aoki

Difficulty: ???
解答時間: 3:03

  • N 個の穴に一本ずつ歯が生えている。「穴 T_i に歯が生えていたら抜き、生えていなければ生やす」という治療を Q0 回行ったあとに生えている歯の本数を求めよ。
  • 歯が生えているか否かをbool配列で保持し、シュミレーションを行うだけ。

yuulis.hatenablog.com

C - Sort

Difficulty: ???

  • 数列 \{1, 2, ..., N\} を並べ替えてできる数列 A が与えられる。「 A の任意の二つの要素を選んで位置を入れ替える」という操作を行って A を昇順ソートするときの手順を出力せよ。
  • 操作自体はバブルソートっぽいのだが、バブルソートの計算量は O(N^2) であり、 2 \leq N \leq 2 \times 10^5 という制約上間に合わない。これより計算量の小さいソートアルゴリズムはクイックソートやマージソートなどが挙げられるが、今回のような操作手順を踏みながらソートを行うコードが書けず撃沈。

yuulis.hatenablog.com

結果

Performance: 438
Rating: 585 → 572 (-13)

atcoder.jp

AとCで地獄を見た。

【AtCoder】ABC 339 C - Perfect Bus | 茶コーダーが解くAtCoder

AtCoder ABC 灰Diff Diff: 100~299 シュミレーション プログラミング

atcoder.jp

実行時間制限: 2 sec / メモリ制限: 1024 MB / Difficulty: 174

問題概要

一台のバスが走っており、乗客は常に非負整数である。このバスにはある時点において0人以上の乗客が乗っており、その時点から現在まで計 N 回停車した。 i 回目の停車では乗客が差引 A_i 人増加し、停車時以外では乗客の増減はなかった。ただし、 A_i < 0 の場合もあり得る。与えられた情報に矛盾しない現在のバスの乗客の数として考えられる最小値を求めよ。

制約

  • 入力はすべて整数。
  • 1 \leq N \leq 2 \times 10^5
  • -10^9 \leq A_i \leq 10^9

考察

まずは最初に乗客が0人だったとしてシュミレーションしていく。途中で乗客数が負になったら、0にリセットしてシュミレーションを続ける。これを最後まで行ったときの乗客数が答えになる。

この人数より乗客数を減らすと、どこかで乗客数は負になり設定と矛盾する。

コード

#include <bits/stdc++.h>
using namespace std;

#define rep(i, start, end) for (ll i = (start); i < (ll)(end); i++)

// ======================================== //

int main()
{
    int N;
    cin >> N;
    ll ans = 0;
    rep(i, 0, N)
    {
        int A;
        cin >> A;

        ans += A;
        if (ans < 0)
            ans = 0;
    }

    cout << ans << endl;
}

atcoder.jp

実装時間: 10分

【AtCoder】ABC 339 B - Langton's Takahash | 茶コーダーが解くAtCoder

AtCoder ABC 灰Diff Diff: 100~299 grid シュミレーション プログラミング

atcoder.jp


実行時間制限: 2 sec / メモリ制限: 1024 MB / Difficulty: 202

問題概要

H 行 W 列のトーラス状のグリッドがあり、初めは全てのマスが白で塗られている。今、マス (1, 1) において上を向いている。以下の操作を N 回繰り返した後、グリッドの各マスがどの色で塗られているかを出力せよ。ただし、白のマスは.、黒のマスは#で表せ。

  • 操作 : 現在いるマスが白で塗られている場合は、現在いるマスを黒に塗り替え、時計回りに 90^\circ 回転し、向いている方向に1マス進む。そうでない場合は、現在いるマスを白に塗り替え、反時計回りに 90^\circ 回転し、向いている方向に1マス進む。

制約

  • 入力はすべて整数。
  • 1 \leq H, W \leq 100
  • 1 \leq N \leq 1000

考察

グリッド上を移動する問題は、グリッドの情報を2次元配列で保持しておき、現在の位置の行インデックスと列インデックスをそれぞれ変数としてそれを更新していくのが一般的だ。本問では向きの概念があるため、現在の向きを変数としておき、その向きで移動する距離を管理する配列 (ここではdx, dyとした) を作っておくと実装が楽になる。

また、このグリッドはトーラス状になっているので、例えばマス (1, 1) から上に移動するとマス (H, 1) になる。これは、上下方向は H 、左右方向は W の剰余をとることで解決できる。このあたりは有名な「ライフゲーム」あたりを実装したことがあれば容易に思いつくのではないだろうか。ただし、 C++ の負の数に対する剰余の挙動に注意。

あとは問題文の通りにシュミレーションをして、結果を出力すればよい。

コード

#include <bits/stdc++.h>
using namespace std;

#define rep(i, start, end) for (ll i = (start); i < (ll)(end); i++)

// ======================================== //

int main()
{
    int H, W, N;
    cin >> H >> W >> N;

    vector<vector<char>> v(H, vector<char>(W, '.'));
    int pos_x = 0, pos_y = 0, dir = 0;
    int dx[4] = {0, 1, 0, -1};
    int dy[4] = {-1, 0, 1, 0};

    rep(i, 0, N)
    {
        if (v[pos_y][pos_x] == '.')
        {
            v[pos_y][pos_x] = '#';
            dir++;
        }
        else
        {
            v[pos_y][pos_x] = '.';
            dir--;
        }

        dir = ((dir % 4) + 4) % 4;

        pos_x += dx[dir];
        pos_y += dy[dir];

        pos_x = ((pos_x % W) + W) % W;
        pos_y = ((pos_y % H) + H) % H;
    }

    for (auto &&h : v)
    {
        for (auto &&w : h)
        {
            cout << w;
        }
        cout << endl;
    }

atcoder.jp

実装時間: 10分

【AtCoder】ABC 349 C - Airport Code | 茶コーダーが解くAtCoder

AtCoder ABC 灰Diff Diff: 100~299 プログラミング

atcoder.jp

実行時間制限: 2 sec / メモリ制限: 1024 MB / Difficulty: 219

問題概要

英小文字からなる文字列 S から、英小文字からなる長さ3の文字列 T を次の2つのうちいずれかの方法で得られるとき、 T は S の「空港コード」であるとする。与えられた文字列 S, T に対して、 T が S の空港コードであるかを判定せよ。

  • 方法1 : S の長さ3の部分列をとり、それを英大文字に変換したものを T とする。
  • 方法2 : S の長さ2の部分列をとり、それを英大文字に変換したものの末尾にXを追加したものを T とする。

制約

  • S は英小文字からなり、その長さは 3 以上 10 ^5 以下。
  • T は英大文字からなり、その長さは 3 。

考察

基本的には T の生成方法を逆にたどり、条件に合うかを確認していけばよい。 T の末尾がXであるかそうでないかで処理が若干異なるので、場合分けを行う。

T の末尾がXであるとき

c1を T の1文字目を小文字化したもの、c2を T の2文字目を小文字化したものとして、c1, c2がこの順に S に含まれているかをチェックすればよい。 S の長さは最大でも 10^5 なので、愚直にループを回していくだけで解決できる。

T の末尾がXでないとき

c1を T の1文字目を小文字化したもの、c2を T の2文字目を小文字化したもの、c3を T の3文字目を小文字化したものとして、c1, c2, c3がこの順に S に含まれているかをチェックすればよい。処理は前項とほぼ同じ。

コード

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

#define rep(i, start, end) for (ll i = (start); i < (ll)(end); i++)

// ======================================== //

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

    if (T[2] == 'X')
    {
        char c1 = tolower(T[0]);
        char c2 = tolower(T[1]);

        bool flag = false;
        int idx1 = 0;
        rep(i, 0, S.size()) if (S[i] == c1)
        {
            flag = true;
            idx1 = i;
            break;
        }
        if (!flag)
        {
            cout << "No" << endl;
            return 0;
        }

        flag = false;
        rep(i, idx1 + 1, S.size()) if (S[i] == c2)
        {
            flag = true;
            break;
        }
        if (!flag)
        {
            cout << "No" << endl;
            return 0;
        }
        else
        {
            cout << "Yes" << endl;
            return 0;
        }
    }

    else
    {
        char c1 = tolower(T[0]);
        char c2 = tolower(T[1]);
        char c3 = tolower(T[2]);

        bool flag = false;
        int idx1 = 0, idx2 = 0;
        rep(i, 0, S.size()) if (S[i] == c1)
        {
            flag = true;
            idx1 = i;
            break;
        }
        if (!flag)
        {
            cout << "No" << endl;
            return 0;
        }

        flag = false;
        rep(i, idx1 + 1, S.size()) if (S[i] == c2)
        {
            flag = true;
            idx2 = i;
            break;
        }
        if (!flag)
        {
            cout << "No" << endl;
            return 0;
        }

        flag = false;
        rep(i, idx2 + 1, S.size()) if (S[i] == c3)
        {
            flag = true;
            break;
        }
        if (!flag)
        {
            cout << "No" << endl;
            return 0;
        }
        else
        {
            cout << "Yes" << endl;
            return 0;
        }
    }
}

atcoder.jp

実装時間: 15分

かなり冗長なコードになってしまったが、AC であれば正義。