0.はじめに
寒さ強まる今日後の頃のコンテスト
C問題までは順調に正答しましたが、Dでブレーキ。
苦手なDPを頑張りましたが、時間が足りずあえなく終了。
レートは-13で725とまた後退しました・・・。
1. A - Robot Balance
頭と胴のバランス問題。
基本的に頭の重さから胴の重さを引いた値が答えとなりますが
素直にそのままだと胴の方が重い時マイナスの値ごなってしまうので
max関数を使って０と頭の重さから胴の重さを引いた値の大きい方を
出力してACでした。
https://atcoder.jp/contests/abc431/submissions/70760766
2.B - Robot Weight
ロボットにパーツをつける問題。
パーツをつけているかどうかを管理するリストLを用意し
クエリーごとに
パーツがついてなければそのパーツ分を総重量に足す
パーツがついていればそのパーツ分を総重量から引く
総重量を出力
と素直に実装してACでした。
https://atcoder.jp/contests/abc431/submissions/70768495
3.C - Robot Factory
A問題の発展？問題。
【考え方】
・頭の軽い方（と胴体の重い方）からK個を使ってロボットがすべて作れればYes
・頭の軽い方からK個と、胴体パーツを重い順に組み合わせ頭＞胴となる組み合わせがなければ
Yesと出力し、頭＞胴となる組み合わせがあればNoを出力する
と、考えて雑に実装しましたがACとなりました。
https://atcoder.jp/contests/abc431/submissions/70779751
4.D - Robot Customize
どう考えてもdpだろうなーと思いつつ、始めは無駄に別方法であがいたため時間が足りなくなりました・・・。
【誤った考え方】
・パーツごとに頭の嬉しさから胴体の嬉しさを引いたものを重さで割った値を嬉し度とする
・最初すべてのパーツを胴につけた状態にする
・嬉し度の高い順にパーツを胴から頭に移して行き、移せなくなった時の状態が最善の状態として嬉しさ計を出力
上記実装で見事にWA23となり、方針転換。
【考え方】
・すべてのパーツを胴につけた状態の総重量、と胴総嬉しさを求める
・パーツごとに重さと頭の嬉しさから胴体の嬉しさを引いた値＝差分嬉しさをリストに格納
・パーツ数×総重量の半分のｄｐ表を作り、差分嬉しさ合計を最大になるようｄｐ計算する
・胴総嬉しさと最大差分嬉しさ合計を足した値が答えとなる
考え方は会っていましたが、ｄｐの更新がうまくいっておらず時間切れになりました。
ｄｐにもう少し慣れておかないとなと思いました。
https://atcoder.jp/contests/abc431/submissions/70807993
以上