Yuulis.log

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

【AtCoder】ABC 339 A - TLD | 茶コーダーが解くAtCoder

AtCoder ABC 灰Diff Diff: ~99 Easy プログラミング

atcoder.jp


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

問題概要

英小文字と.のみからなる文字列 S が与えられる。 S を.で分割したときの末尾の文字列を出力せよ。

制約

  • S の長さは2以上100以下
  • S の末尾は.ではない。

考察

問題文がちょっとわかりにくいが、要するに S の最も後ろにある.から後ろの文字列を出力すればよい。具体的には以下のようになる。

  1. S の最も後ろにある.のインデックスをidxとする。
  2. S[idx + 1]からS[S.size() - 1]を出力する。

コード

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

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

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

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

    int idx = 0;
    rep(i, 0, S.size())
    {
        if (S[i] == '.')
            idx = i;
    }

    rep(i, idx + 1, S.size())
    {
        cout << S[i];
    }
    cout << endl;

atcoder.jp


実装時間: 5分以内

【AtCoder】ABC 349 B - Commencement | 茶コーダーが解くAtCoder

AtCoder ABC 灰Diff Diff: ~99 map プログラミング

atcoder.jp

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

問題概要

英小文字からなる文字列が次の条件を満たすとき、その文字列は「良い文字列」であるとする。英小文字からなる文字列 S が与えられるので、 S が「良い文字列」であるかを判定せよ。

  • 条件 : i \geq 1 を満たす全ての整数 i について、文字列内でちょうど i 回現れる文字は、ちょうど0種類または2種類である。

制約

  • S の長さは1以上100以下。

考察

まず、 S 中の文字の種類とその個数を管理したいので、前者をkey、後者をvalueとしてmapに記録していく (ここでは変数名をmpとした) 。

次に、 i を i = 1, 2, 3, ... と増やしていく過程で、以下の判定を行う。

  • mpの全要素を走査し、mp.second == iならカウンターを増やす。その後、カウンターが0または2でないならば、「良い文字列」の条件を満たさないので即座にNoを出力してプログラムを終了する。そうでなければ、iを1増やす。

この判定全てを通過した場合はYesと出力すればよい。

最後に、 i はどこまで増やすかという点についてだが、これは「 S の長さが最大100」という制約から、同じ文字が最大100個続く文字列が入力されることを考えて、上限を100までにしておけば良いだろう。

コード

#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;
    cin >> S;
    map<char, int> mp;
    rep(i, 0, S.size()) mp[S[i]]++;

    rep(i, 1, 101)
    {
        int cnt = 0;
        for (auto &&m : mp)
        {
            if (m.second == i)
                cnt++;
        }

        if (!(cnt == 0 || cnt == 2))
        {
            cout << "No" << endl;
            return 0;
        }
    }

    cout << "Yes" << endl;
}

atcoder.jp

実装時間: 5分以内

【AtCoder】ABC 349 A - Zero Sum Game | 茶コーダーが解くAtCoder

AtCoder ABC 灰Diff Diff: ~99 Easy プログラミング

atcoder.jp

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

問題概要

1から [tex; N] の番号が付けられた [tex; N] 人の人がおり、この中で一対一の勝敗のつくゲームを何度か行った。 N 人は最初にそれぞれ持ち点として0を持っており、各ゲームでは勝者の持ち点が1増え、敗者の持ち点が1減る。なお、持ち点は途中で負になることもあり得る。最終的に人 i (1 \leq i \leq N - 1) の持ち点が A_i になったとき、人 N の持ち点を求めよ。

制約

  • 入力はすべて整数。
  • 2 \leq N \leq 100
  • -100 \leq A_i \leq 100

考察

A問題にしては長めの問題文である。

サンプルケース1を詳しく見てみよう。各ゲームごとの持ち点の推移を表にしてみた。

ここで注目すべきなのは、「全員の持ち点の総和」だ。上表において、各行ごとの4人の持ち点の総和を取ると全て0になる。

これは決して偶然ではない。各ゲームでは対戦した二人の持ち点が増減するものの、増分の絶対値は等しいため全員の持ち点の総和は変わらないからだ。開始時は全員の持ち点が0なので、無限回ゲームを行って途中どの二人を対戦させたとしても、 N - 1 人の最終的な持ち点が分かっていれば、残り一人の最終的な持ち点も一意に定まる。

具体的には、人 A_N の最終的な持ち点 A_N は A_N = - \displaystyle{\sum_{i=1}^{N-1}} A_i と計算できる。これをループなどを用いて求めていけばよい。

コード

#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()
{
    int N;
    cin >> N;

    int ans = 0;
    rep(i, 1, N)
    {
        int A;
        cin >> A;
        ans += A;
    }

    cout << ans * -1 << endl;
}

atcoder.jp

実装時間: 5分以内

【AtCoder】AtCoder Beginner Contest 349 - 参加記 | 茶コーダーが解くAtCoder

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

atcoder.jp

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

A - Zero Sum Game

Difficulty: ???
解答時間: 2:46

  • 勝者の持ち点が1増え、敗者の持ち点が1減る一対一のゲームを N 人が行うにあたって、人 1 から N - 1 の最終的な持ち点 A_1, A_2, ..., A_{N - 1} が与えられたとき、人 N の最終的な持ち点を求める問題。
  • N 人の持ち点の総和は 0 で常に変わらないことに気付けば、 - \sum_{i = 0}^{N - 1} A_i を出力すればよいことになる。これに気付けなくてもサンプルケースを見ればなんとなくわかったり...

B - Commencement

Difficulty: ???
解答時間: 4:01

  • 以上の整数 i について、「文字列 S にちょうど i 回現れる文字はちょうど0種類または2種類ある」が成り立つかどうかを判定する問題。
  • まず S に現れる文字の種類と個数を連想配列 (map) で管理する。そして、各 i (1 \leq i \leq 100) に対してmap.second == iを満たすならばカウンターを増やし、mapの要素を全走査後、カウンターが0または2はでないならばNoを即時に返して終わり。最後まで進めばYesを返す。 i の上限が100なのは、 S の長さが最大100であり最大100個の同じ文字が出現する可能性があるから。

C - Airport Code

Difficulty: ???
解答時間: 20:56 (2WA)

  • 与えられた文字列 T が、英小文字の文字列 S に対して2つの操作のうちいずれかを行ってできた文字列かどうかを判定する問題。
  1. S の長さ3の部分列をとり、それを英大文字に変換する。
  2. S の長さ2の部分列をとり、それを英大文字に変換したものの末尾にXを結合する。
  • まず、 T の末尾がXかであるかそうでないかで場合分けをする。
  • 前者ならS[0]とS[1]について、後者ならS[0]とS[1]とS[2]について、それぞれ S の各文字を全探索して存在するかをチェックする。...と言いたいところなのだが、 S の部分列を取り出してきている点を見落としており、各文字における探索開始地点がずれることを考慮していなかった。その対処の過程で2WAを踏んでしまった。

結果

Performance: 649
Rating: 578 → 585 (+7)

atcoder.jp

Bまでは本当に理想的だった。Cの2WAがなければ緑Perfが狙えそうだったが...

【AtCoder】ABC 340 D - Super Takahashi Bros. | 茶コーダーが解くAtCoder

AtCoder ABC 茶Diff プログラミング Diff: 600~799

atcoder.jp


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

問題概要

1, 2, ..., N の番号が付いた N 個のステージがあり、現在はステージ1のみが遊べる。各ステージ i (1 \leq i \leq N - 1) が遊べるとき、ステージ i では次の2つの行動のどちらかを行うことができる。各ステージをクリアするためにかかる時間以外は無視できるとき、ステージ N を遊べるようになるのは最短で何秒後か。

  • 行動 :
  1. A_i 秒かけてステージ i をクリアする。結果、ステージ i + 1 が遊べるようになる。
  2. B_i 秒かけてステージ i をクリアする。結果、ステージ X_i が遊べるようになる。

制約

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

考察

頂点をステージ、辺の重みをステージが遊べるようになるまでの時間として、サンプルケース1の様子をグラフで図示してみると以下のようになる。太線矢印の遷移が最短となる。

サンプルケース1

一般化して考えると、求めたいのは頂点1から頂点 N までの最短経路ということになる。重み付き有向グラフにおいてある頂点からの最短経路を求めるときに使えるアルゴリズムは、「ダイクストラ (Dijkstra) 法」だ。

ダイクストラ法は、「ある1つの始点から各点への最短経路を求めるアルゴリズム」である。辺の重みが負になるものがある場合は使えないが、今回は時間が辺の重みになるため負の辺は存在しない。

ダイクストラ法を使えばよいということが分かれば実装自体はシンプルで、 1 から N までの N - 1 個の各頂点からそれぞれ2本の辺を張っていけばよい。

コード

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

using ll = long long;

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

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

struct Edge
{
    ll to;
    ll cost;
};

using Graph = vector<vector<Edge>>;
using Pair = pair<ll, ll>;

void Dijkstra(const Graph &graph, vector<ll> &distances, ll startIndex)
{
    priority_queue<Pair, vector<Pair>, greater<Pair>> p_queue;
    p_queue.emplace((distances[startIndex] = 0), startIndex);

    while (!p_queue.empty())
    {
        const ll distance = p_queue.top().first;
        const ll from = p_queue.top().second;
        p_queue.pop();

        if (distances[from] < distance)
            continue;

        for (const auto &edge : graph[from])
        {
            const ll new_distance = (distances[from] + edge.cost);

            if (new_distance < distances[edge.to])
                p_queue.emplace((distances[edge.to] = new_distance), edge.to);
        }
    }
}

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

    Graph G(200020);
    rep(i, 1, N)
    {
        ll A, B, X;
        cin >> A >> B >> X;
        G[i].push_back(Edge{i + 1, A});
        G[i].push_back(Edge{X, B});
    }

    vector<ll> dist(N + 1, INFL);
    Dijkstra(G, dist, 1);

    cout << dist[N] << endl;
}

atcoder.jp

実装時間: 40分

最初に動的計画法で実装してしまい、サンプルケース2で落とされてしまった。時系列順の探索はダイクストラ法という認識で良いのかもしれない。