ABC454を振り返る

プログラミング
2026.04.19

今回からABCやAHCが終わるたびに振り返りブログを書いていきたいなと思いまする

はじめに

始めに、何で急にそんなことするのかと、何で今までやってこなかったかについて説明しますね…
まず、「何で急にそんなことするのか」ですが、これはシンプルに「ネタ稼ぎ」ですねぇ。
はっきり言って、こういった振り返りで1記事が書けてしまうためネタとしてちょうどいいんです。しかも、自分が未来に読んで振り返りをすることもできて非常にいいと思ってます。
じゃあ次、「何で今までやってこなかったか」です。ちょっと長くなりますので、次のブロックへ行きましょうか。

何で今まで振り返り記事を書かなかったか

結論から言うと、「記事投稿システムがまだ出来上がってないから」です。
この記事なんですが、ネットに接続して書いています。ただ、やっぱりちょっと面倒くさいです。しかも、QiitaなどでおなじみMarkdownで書けた方が絶対ストレスフリーですよね？
そういうこともあり、長らく敬遠していました。しかし、このまま記事を出さないで居続けたら、AdSenseの審査も永遠に通らないし、SEO的にもよくない。なにより永遠にやらんぞ自分…とばるとーくさん思いました。
というわけで、ついに重い腰を上げたわけであります。

※Markdownで書けるシステムは今月中に構築してまた記事にします。これはお約束とさせてください…

ABC454振り返り

総評

結果は写真の通り、3完となりました。

A問題でチョンボしたのが痛いのと、C問題よく頑張ったな…という印象です。

レートに関してもちょっと伸びって感じです。でも頑張れば今月中の入茶は視野に入れられます。
って思ったけどあと1週しかないじゃん⁉
AC-Predictor によるとパフォ847が必要だそうです…　いけるんか自分⁉
ちなみに緑パフォを取ったことは未だないです…
C問題を速くACするか4完すれば届きそうですが、厳しそう…

A問題

問題はこちらでした

問題文

整数 L,R が与えられます。

L 以上 R 以下の整数がいくつあるか求めてください。

制約

  • 1≤L≤R≤100
  • 入力される値は全て整数
A - Closed interval
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.
AtCoder

ここで、まさかの1ペナを食ってしまいました。コードを見てみましょう。

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

// --- 初期設定（入出力の高速化と小数15桁出力） ---
struct Init {
  Init() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(15);
  }
} init;
// ------------------------------------------------

int main() {
  int l, r;
  cin >> l >> r;
  cout << l - r + 1 << endl;
  return 0;
}

問題はこの "cout << l - r + 1 << endl;" の部分でした。逆ですね…
本来なら、「大きいほうから小さいほうを引いて1を足す」が正解でした。
大焦りなばるとーくさん、ここにしっかりと気づいて修正できました…が勿体ない！

（2026/4/20 追記）
ところで、ここまで読んだあなたはこう思ったかもしれません。
「Easy Testやらんかったん？」って。
えーとこれに関してなんですが、「やらなかった」のではなく「できなかった」んですよね...
ABC開始直後、重たかったんですよね。それで実行されるまでに時間がかかってしまい、待ちきれずに提出してしまった結果、1ペナを食らうという...
※ローカル環境頑張って構築しますねぇ...

B問題

問題はこちらで～す！

問題文

1 から N の番号が付いた N 人の人がいます。
また、1 から M の番号が付いた M 種類の服があります。人 i は服 Fi​ を着ています。
次の 2 個の質問に Yes か No で答えてください。

  • 質問 1: N 人全員が異なる種類の服を着ていますか？
  • 質問 2: M 種類の服全てについて、その服を着ている人が少なくとも 1 人ずついますか？

制約

  • 1≤N≤100
  • 1≤M≤100
  • 1≤Fi​≤M
  • 入力される値は全て整数
B - Mapping
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.
AtCoder

こちらは1発ACでした。が、解説を読むととても頭の良い方法だったなと感じました。

書いたコードはこんな感じ

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

// --- 初期設定（入出力の高速化と小数15桁出力） ---
struct Init {
  Init() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(15);
  }
} init;
// ------------------------------------------------

int main() {
  int n, m;
  cin >> n >> m;
  vector<int> f(n);
  for (int i = 0; i < n; i++) {
    cin >> f[i];
  }

  sort(f.begin(), f.end());

  int bef = 0;
  bool q1 = true, q2 = true;
  for (int i = 0; i < n; i++) {
    if(f[i] == bef){
      q1 = false;
    }
    if(f[i] != bef && f[i] != bef + 1){
      q2 = false;
    }
    if(!q1 && !q2){
      break;
    }
    bef = f[i];
  }

  if(bef != m){
    q2 = false;
  }

  if (q1) {
    cout << "Yes" << "\n";
  } else {
    cout << "No" << "\n";
  }

  if (q2) {
    cout << "Yes" << "\n";
  } else {
    cout << "No" << "\n";
  }

  return 0;
}

真偽値2つとsortを使って、愚直に探索するだけのコードです。

  1. F_1からF_Nまでのすべてをvectorに入れて昇順ソート
  2. 1つ前の数字を記憶する変数befを定義する(初期値=0)
  3. もしF[i]がbefと同じなら、質問1の条件を満たさなくなるためq1をfalseにする
    ※F[i] == befになってしまうと、「全員が異なる服を着ている」ことにならない
  4. もしF[i]がbefと同じでないかつ、F[i]がbef + 1でないなら、質問2の条件を満たさなくなるためq2をfalseにする
    ※増加する際は1つずつ増加しないと空きが生まれてしまい、「誰にも着られてない種類の服」が出来てしまうから

しかし、setを使うって考えはなかったです…履修してきます！

C問題

こんな問題でした

問題文

アイテム 1 からアイテム N までの N 種類のアイテムがあります。はじめ、高橋君はアイテム 1 のみ持っています。

高橋君には M 人の友達がいます。i 人目 (1≤i≤M) の友達にアイテム Ai​ を渡すと、アイテム Bi​ をもらうことができます。

高橋君が手に入れることのできるアイテムはアイテム 1 を含めて何種類あるか求めてください。

制約

  • 2≤N≤3×105
  • 1≤M≤3×105
  • 1≤Ai​,Bi​≤N
  • Ai​ != Bi​
  • 入力される値は全て整数
C - Straw Millionaire
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.
AtCoder

はじめ、このように考えていました。

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

// グラフ型
//  main関数内などで（全体の大きさ + 1）のサイズを確保すること
using Graph = vector<vector<int>>;

// 連結リスト表現での代入
void insert(Graph& G, int V, int ins) {
  G[V].push_back(ins);
}

// --- 初期設定（入出力の高速化と小数15桁出力） ---
struct Init {
  Init() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(15);
  }
} init;
// ------------------------------------------------

int main() {
  int n, m;
  cin >> n >> m;

  vector<bool> get(n + 1, false);
  get[1] = true;
  vector<pair<int, int>> ab(m);  // first:a, second:b

  for (int i = 0; i < m; i++) {
    cin >> ab[i].first >> ab[i].second;
  }

  sort(ab.begin(), ab.end());

  for (int i = 0; i < m; i++) {
    cerr << ab[i].first << ab[i].second << endl;
  }

  for (int i = 0; i < m; i++) {
    if (get[ab[i].first]) {
      cerr << "ok" << endl;
      get[ab[i].second] = true;
    }else{
      cerr << "ng" << endl;
    }
  }

  ll ans = 0;
  for (int i = 1; i <= n; i++) {
    if(get[i]){
      ++ans;
    }
  }

  cout << ans << "\n";
  return 0;
}

簡単に言うと、「もしそのアイテムをすでに持っていれば、交換後のアイテムも手に入れたことにする」という意図で書いたコードです。しかしこれはWAとなってしまいました…

その後、これがグラフ探索であることに気づき…
死に物狂いでグラフとBFSについて調べましたぁ。（あほかな？）

その結果ACしたコードがこちら

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N, M;
    if (!(cin >> N >> M)) return 0;

    vector<vector<int>> G(N + 1);
    for (int i = 0; i < M; ++i) {
        int u, v;
        cin >> u >> v;
        G[u].push_back(v);
    }

    vector<bool> visited(N + 1, false);
    queue<int> q;

    q.push(1);
    visited[1] = true;

    int ans = 0;

    // BFSによる探索
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        ans++;

        for (int v : G[u]) {
            if (!visited[v]) {
                visited[v] = true;
                q.push(v);
            }
        }
    }

    // 結果の出力
    cout << ans << "\n";

    return 0;
}

いや、我ながらよく頑張ったでこれはさぁ！

今後の課題

データ構造をまだまだ知らんなと思いました…
精進が全然足らないです。今週どれだけ新しい典型を学べるかに期待です。

あとはよグラフ関係おぼえろ！

コメント

タイトルとURLをコピーしました