トヨタシステムズプログラミングコンテスト2025（AtCoder Beginner Contest 431） コンテストまとめ

コンテスト情報

TOYOTA SYSTEMS Programming Contest 2025（AtCoder Beginner Contest 431) - AtCoder

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

AtCoder

コンテスト時間: 2025-11-08(土) 21:00 ~ 2025-11-08(土) 22:40 (100 分)

前半の問題が「高橋君とロボット」シリーズで統一されている。

A 問題

• Difficulty: 10 / NoviSteps: 9Q / 解答時間: 1:26

問題概要

頭パーツと体パーツを $1$ 個ずつ組み合わせてロボットを $1$ 体作ることができる。 しかし、ロボットは頭パーツの重さが体パーツの重さより大きいと倒れてしまう。

高橋くんが持っている頭パーツの重さは $H$ グラム、体パーツの重さは $B$ グラムである。 ロボットが倒れないようにするためには、体パーツをあと何グラム重くする必要があるか求めよ。

解答方針

• $\max(0, H - B)$ を出力する。if 文で書いてもよい。

https://yuulisio.com/posts/review-abc431-a

yuulisio.com

B 問題

• Difficulty: 36 / NoviSteps: 6Q / 解答時間: 3:37

問題概要

あるロボットがあり、はじめの重さは $X$ である。

このロボットには、同時に取り付けられる部品が $N$ 種類あり、種類 $i$ の部品の重さは $W_i$ である。 はじめ、ロボットにはどの部品もついていない。

次の $Q$ 個のクエリを順に処理せよ。 $i$ 番目のクエリは以下の通り。

• 現在、ロボットに種類 $P_i$ の部品がついていない場合は取り付け、ついている場合は取り外す。その後、現在のロボットの重さを出力する。

解答方針

-ロボットに種類 $i$ の部品が付いているかどうかをフラグ配列で管理し、クエリごとにフラグの更新と部品の重さを加減算して出力すればよい。

https://yuulisio.com/posts/review-abc431-b

yuulisio.com

C 問題

• Difficulty: 172 / NoviSteps: 3Q / 解答時間: 6:44

問題概要

高橋くんは、頭パーツを $1$ 個と体パーツを $1$ 個組み合わせてロボットを $1$ 体作ることができる。 しかし、ロボットは頭パーツの重さが体パーツの重さより大きいと倒れてしまう。

現在、高橋くんは頭パーツを $N$ 個と体パーツを $M$ 個持っています。 高橋くんが持っている $i$ 番目の頭パーツの重さは $H_i$ グラム、$i$ 番目の体パーツの重さは $B_i$ グラムである。

高橋くんは、持っているパーツを適切に組み合わせることで、倒れないロボットを合計 $K$ 体作りたい。 これが達成可能か判定せよ。

解答方針

• 頭のパーツは軽い方から、体のパーツは重い方から$K$個を選び、その中から軽い順に貪欲に組み合わせていく。
• これで $K$ 個のロボットを作ることができるのならば、答えはYes、そうでなければNoである。

https://yuulisio.com/posts/review-abc431-c

yuulisio.com

D 問題

• Difficulty: 693 / NoviSteps: 2Q / 解答時間: 29:56

問題概要

頭と体からなるロボットがあり、同時に取り付けられる部品が $N$ 種類ある。 種類 $i$ の部品の重さは $W _ i$ で、それぞれの部品には、頭に取り付けたときと体に取り付けたときで異なる嬉しさがある。 種類 $i$ の部品を頭に取り付けたときの嬉しさは $H _ i$ 、体に取り付けたときの嬉しさは $B _ i$ である。

ただし、ロボットは頭の重さが体の重さより大きいと倒れてしまう。

$N$ 種類の部品をすべて $1$ 個ずつロボットに取り付けたい。 ロボットを倒さないように部品を取り付けたときの、すべての部品の嬉しさの合計としてありえる最大値を求めよ。

解答方針

• とりあえず、全ての部品を体に取り付けるとして、そこから頭に取り付けるものを選ぶことを考える。このとき、嬉しさの変化量は $H_i - B_i$ となる。
• ここで、重さ $W_i$, 価値が $H_i - B_i$ の品物があるとして、部品の重さの総和 $\sum W_i$ を $S$ とする。
• このとき、重さの合計が $\frac{S}{2}$ 以下という制約付きナップザック問題に帰着できる。

https://yuulisio.com/posts/review-abc431-d

yuulisio.com

成績

Contest Result - AtCoder

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

AtCoder

• 順位: 2329th / 10332
• Performance: 1068
• Rating: 1220 → 1206 (-14)

D 問題に時間をかけ過ぎなのと、E 問題をもう少し頑張りたかった。