はじめに
こんにちは。
このページはWCPCメンバーによるABC参加記、第一回目の記事です。編集者はCaffeineholicでお送りいたします。
この記事のコンテンツは以下の通りです。
- このシリーズの目的
- 今週の出題への言及、考察、解法、所感など
- これからの話
この記事の目的
サークル内で何か活動履歴を残せないかと考え、「毎週のABCへの参加について記録を残せたらいいよね」という話をしたことから生まれたのがこのシリーズ記事です。
ABCとは、競技プログラミングサイト AtCoderで毎週開催されるプログラミングコンテスト、AtCoder Beginner Contestの略称です。
Beginnerを冠してはいますが毎週高難度の問題が出題され、考察力とプログラミング力を両立させられなければ好成績は望めません。2026年4月18日に開催され私も参加したものが第454回、通称ABC454であるというわけです。
今週の出題
ABC454-A
問題文を表示
問題文
整数 L, R が与えられます。
L 以上 R 以下の整数がいくつあるか求めてください。
制約
- 1 ≤ L ≤ R ≤ 100
- 入力される値は全て整数
入力
L R
出力
答えを出力せよ。
いつも通り、プログラミング言語への理解さえあれば解けるレベルの問題であると言えます。 繰り返し文をLからRの範囲で記述し変数をそのたびにインクリメントする…という愚直な解法は、おそらく大多数の参加者は行っていないでしょう。 この問題設定の場合 R - L + 1 を出力するだけで十分ですね。
ABC454-B
問題文を表示
問題文
1 から N の番号が付いた N 人の人がいます。
また、1 から M の番号が付いた M 種類の服があります。人 i は服 F_i を着ています。
次の 2 個の質問に Yes か No で答えてください。
質問 1: N 人全員が異なる種類の服を着ていますか？
質問 2: M 種類の服全てについて、その服を着ている人が少なくとも 1 人ずついますか？
制約
- 1 ≤ N ≤ 100
- 1 ≤ M ≤ 100
- 1 ≤ F_i ≤ M
- 入力される値は全て整数
入力
N M
F_1 F_2 … F_N
出力
2 行出力せよ。
i 行目には質問 i の答えが Yes であれば Yes を、No であれば No を出力せよ。
B問題は今週もデータ構造の扱い方の知識が求められましたが、まだ初心者向けと言えます。 僕の解法は、連想配列（ハッシュテーブル）に ｛服の番号: それを着ている人数｝ の形で値を保存してゆき、その長さ（要素数）がNに等しいかどうかで質問1に解答しMに等しいかどうかで質問2に解答するというものでした。 公式解答にも同じような趣旨がありましたが、あちらはセット（ハッシュセット）を利用するやり方でした。よく考えれば、連想配列の中の値は利用していなかったのですからセットを利用するほうが適切だったかもしれませんね。
ABC454-C
問題文を表示
問題文
アイテム 1 からアイテム N までの N 種類のアイテムがあります。はじめ、高橋君はアイテム 1 のみ持っています。
高橋君には M 人の友達がいます。
i 人目 (1 ≤ i ≤ M) の友達にアイテム A_i を渡すと、アイテム B_i をもらうことができます。
高橋君が手に入れることのできるアイテムはアイテム 1 を含めて何種類あるか求めてください。
制約
- 2 ≤ N ≤ 3 × 10^5
- 1 ≤ M ≤ 3 × 10^5
- 1 ≤ A_i, B_i ≤ N
- A_i ≠ B_i
- 入力される値は全て整数
入力
N M
A_1 B_1
A_2 B_2
⋮
A_M B_M
出力
答えを出力せよ。
誤読報告も多かったC問題です。
高橋君が手に入れることのできるアイテムはアイテム1を含めて何種類あるか求めてください。 → 高橋君が一度に手に入れられるアイテムの数は最大で何種類になるか求めてください
と解釈できなくもない問題文だったのでしょうか。
各アイテムが「アイテムxがなければアイテムyを得られない」という関係をなしているため、「ノードx → ノードyの有向辺が存在している」というグラフ状の関係に読み替えられることが本質です。
手元で図に描きだすことで気づきやすくなるのかな、と編集時に考えたりもしましたが、初手でニュアンスを汲み取る力を鍛えることも必要だったかもしれません。
解釈をグラフの形に落とし込めれば、DFS（深さ優先探索）アルゴリズムに行きつくのは時間の問題であると思います。コーディング自体に応用力はそこまで要求されない問題であったかと思います（僕は書き間違いましたが！二回も！）。
ABC454-D
問題文を表示
問題文
(, x, ) からなる文字列 A が与えられます。
あなたは A に対して次の 2 種類の操作を自由な順番で自由な回数行うことが出来ます。
- A の部分文字列 (xx) を 1 カ所選び、xx に置換する。
- A の部分文字列 xx を 1 カ所選び、(xx) に置換する。
(, x, ) からなる文字列 B が与えられます。
A を B と一致させることが出来るか判定してください。
T 個のテストケースが与えられるので、それぞれに対して答えを求めてください。
部分文字列とは
S の 部分文字列 とは、S の先頭から 0 文字以上、末尾から 0 文字以上削除して得られる文字列のことをいいます。
例えば、ab は abc の部分文字列ですが、ac は abc の部分文字列ではありません。
制約
- 1 ≤ T ≤ 3 × 10^5
- A, B は (, x, ) からなる長さ 1 以上 2 × 10^6 以下の文字列
- 全てのテストケースに対する |A| + |B| の総和は 2 × 10^6 以下 (ここで |A| は A の長さを意味する)
- 入力される値は全て整数
入力
T
case1
case2
⋮
caseT
※各テストケースは以下の形式で与えられる
A
B
出力
T 行出力せよ。
i 行目には i 番目のテストケースの答えを出力せよ。
各テストケースでは、A を B と一致させることが出来る場合は Yes を、そうでない場合は No を出力せよ。
スピード勝負のD問題です。 stackを利用すればいいのではと最初に考えたのは、単に括弧列を管理するという問題で利用頻度の高いテクニックであったからという浅い知見からですが、この問題で気づくべき重要な点は以下になります。
- 問題文中の「操作」のうち、Aの部分文字列(xx)を１箇所選び、xxに置換する。 を二つの文字列に対してできる限り行った後に一致判定をしても、正誤が覆ることがない。
- 括弧列を消す操作はstackなどのデータ構造を利用することで楽に実装できる。
難しい証明をしてもしなくてもこれに気づくか、そしてstackという実装方法を見出すかがキモでした。
ABC454-E以降
（これ以降の問題文は割愛） E～Gについては、私は未回答です。E問題を考える時間がかなりあったにもかかわらず、一筆書き可能かの判定方法の調査と自身のスパゲティコーディング改善に無駄に時間を費やしました。 しかし上位陣の正答率が低く、D問題どまりの私としては得をした形でした。D問題までのタイムは遅いがそのペースのままE問題以降も正解する、といった実力の人が私より低いスコアとして扱われることになりますからね。
最後に
以上、ABC454の参加記でした。この記事を読んで競技プログラミングに興味を持った！解法について議論したい！など感じてくだされば幸いです。サークルとしても、お気軽にご連絡お待ちしております。また機会がありましたら筆を執りたいと思います。Caffeineholicでした。