競技プログラミング用知識集積所

ABC431C - Robot Factory

最終更新：2025年11月11日 22:41

sport_programming

- view

管理者のみ編集可

問題
必要知識
考え方
解答例
注意点
別解

問題

ABC431C

必要知識

B以下レベルの内容は省略

貪欲法（アルゴリズム系）※

考え方

3つの貪欲法※を用いて、考える選択肢を減らす。

まず、使用する頭パーツについて。
重さh1の頭パーツを使い、重さh2(<h1)の頭パーツを使っていない場合、h1のをh2のに変えても条件は崩れない。
よって、全組み立て方のうち、頭パーツは軽い方からk個を使うものだけ考えればよい。

次に、使用する体パーツについて。
重さb1の体パーツを使い、重さb2(>b1)の体パーツを使っていない場合、b1のをb2のに変えても条件は崩れない。
よって、全組み立て方のうち、体パーツは重い方からk個を使うものだけ考えればよい。

最後に、頭と体の組み合わせ方について。
重さb1の体に重さh1の頭を乗せていて、重さb2(>b1)の体に重さh2(<h1)の頭を乗せている場合、頭を交換しても条件は崩れない。
よって、重い体ほど重い頭を、軽い体ほど軽い頭を載せているものだけ考えればよい。

これらを組み合わせると、結局調べるべきパターンは1つだけ。
これがうまくいくなら"Yes"、これがダメなら他のパターンは何をやってもダメなこともわかるので"No"が答え。
入力データをdeque※に入れて、ソートした後pop_front()やpop_back()を使ってパーツを捨てると実装しやすい。