AAL Contest 001: Let's use segtree!
参加対象: All Rated対象: - ペナルティ: 5分
コンテスト情報
- AAL Contest 001: Let's use segtree! は、セグメント木をテーマとした教育目的の公式コンテストです。
- コンテスト時間は 2026/10/12(祝) 13:00~18:00 の 5 時間で、問題数は 24 問です。
- 問題文は日本語と英語で提供されます。
- このコンテストは unrated です。レーティングの更新はありません。
- writer :
Nyaan
,
maspy
- tester :
Nachia
AAL Contest とは
AtCoder Algorithm Lectures では、解説記事・解説動画の形式の講座に加えて、 特定のトピックについてより詳しく学び、実践練習を積むための教材として、AAL Contest を開催することになりました。
コンテスト当日は実力試しとして、コンテスト後には学習用教材として利用して、Algorithm Lectures の講座とあわせてご利用ください。
今回のトピック
第 1 回のトピックはセグメント木です。セグメント木は、配列のような組み込みでないデータ構造の中で最も使用頻度が高いデータ構造として知られています。値の集約クエリを対数オーダーで行うことが出来て、かつ載せるモノイドを工夫すれば様々な情報を載せることが出来ます。
このコンテストでは、セグメント木に様々な種類の情報を載せる問題を集めました。セグメント木を使い慣れていない人は是非問題を解き進めてセグメント木に情報を載せるコツをつかんでみてください。
また、このコンテストでは、全ての問題が AtCoder Library のセグメント木・遅延セグメント木を利用して解くことが出来ます。つまり、セグメント木を拡張したデータ構造、例えば永続セグメント木や Segment Tree Beats! に関しては今回は対象外となっています。セグメント木のライブラリを持っていない人は公式ライブラリを使用してみてください。
また、R 問題以降は知識だけでなく考察も必要な問題を集めています。上級者の方も是非コンテストに挑戦してみてください！
配点
A 問題から X 問題で 100 点満点になっています。
| 問題 | A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 点数 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 4 | 4 | 4 | 4 | 4 | 4 | 4 | 4 | 4 | 5 | 5 | 5 | 5 | 5 | 6 | 6 | 6 |
目安としては、各人のレベルに応じておおよそ次の得点を目指すとよいでしょう。
- セグメント木の使い方に慣れていない人：まずははじめの 4 問を解くことを目指しましょう。
- ABC 500 点程度・中難度のセグメント木問題を解ける人: 25 点
- ABC 600 点程度・高難度のセグメント木問題を解ける人: 50 点
- セグメント木が非常に得意な人: 70 点
- セグメント木完全理解者: 85 点
ルール
- コンテスト中に問題に正解すると点数を獲得できます。
- 順位は総合得点で決定します。
- 同点の場合は提出時間の早い人が上の順位になります。
- 誤答を提出するたびにペナルティが加算されます。このコンテストのペナルティは5分です。詳細は画面下部の「ルール」をご覧ください。
このコンテストは full-feedback 形式のコンテストです。コンテスト中に提出された結果だけで順位が決定します。
便利情報
Contest Information
- AAL Contest 001: Let's use segtree! is an official educational contest focused on segment trees.
- The contest will be held for five hours, from 13:00 to 18:00 on October 12, 2026 (a public holiday), and will consist of 24 problems.
- Problem statements will be provided in both Japanese and English.
- This contest is unrated. There will be no rating updates.
- writers:
Nyaan
,
maspy
- tester:
Nachia
What Is the AAL Contest?
In addition to courses in the form of explanatory articles and videos, AtCoder Algorithm Lectures will host AAL Contests as educational resources that allow participants to study specific topics in greater depth and gain practical experience.
We hope that you will use these contests to test your skills on the day of the contest and as learning materials afterward, together with the Algorithm Lectures courses.
This Contest's Topic
The topic of the first contest is segment trees.Segment trees are known as one of the most frequently used data structures among those that are not built into programming languages. They can process aggregate queries in logarithmic time, and by carefully choosing the monoid they store, they can maintain many different kinds of information.
This contest features problems involving many different kinds of information stored in segment trees. Those who are not yet familiar with segment trees are encouraged to work through the problems and learn the techniques for designing the information maintained by a segment tree.
In addition, every problem in this contest can be solved using the segment tree or lazy segment tree provided by AtCoder Library. In other words, extended segment-tree data structures, such as persistent segment trees and Segment Tree Beats!, are outside the scope of this contest. Those who do not have their own segment tree library are encouraged to use the official library.
The problems from Problem R onward require not only knowledge but also substantial problem-solving insight. Advanced participants are also encouraged to take on the contest!
Scoring
Problems A through X are worth a total of 100 points.
| 問題 | A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 点数 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 4 | 4 | 4 | 4 | 4 | 4 | 4 | 4 | 4 | 5 | 5 | 5 | 5 | 5 | 6 | 6 | 6 |
As a general guideline, participants may aim for approximately the following scores according to their skill level.
- Those who are not yet familiar with using segment trees: First, aim to solve the first four problems.
- Those who can solve medium-difficulty segment tree problems at around the ABC 500-point level: 25 points
- Those who can solve difficult segment tree problems at around the ABC 600-point level: 50 points
- Those who are highly proficient with segment trees: 70 points
- Those who have completely mastered segment trees: 85 points
Contest Rules
This contest is full-feedback (solutions are judged during the contest).When you solve a problem, you get a score assigned to it. Competitors are ranked first by total scores, then by penalties. The penalties are computed as (the time you spend to get your current score) + (5 minutes) * (the number of incorrect attempts).