0.はじめに
ドライブ旅行から帰ってきた今日この頃。
今回は２問目までは順調だったもののC問題でブレーキ。
DP使ってTLEを連発して悩んでましたが、その後解法を変えたら
あっさりクリア。
とはいえ時間を使い過ぎDは間に合わず終了。
TLEを連発したためC問題を解くのも遅くなり惨憺たる成績でした
レートは-27で742と大幅減。
また下降気味になってまいりました。。
1. A - Feet
単純にAとBを入力しAに12を掛けた値にBを足して出力してACとなりました。
https://atcoder.jp/contests/abc437/submissions/71829371
2.B - Tombola
Bにしてはちょっとめんどくさい問題。
【考え方】
・行ごと入力したリストの数字を辞書Dへ格納
→キー：リストの数字、値：行数
・行ごとの数字を呼ばれた回数記憶用リストansを用意
・入力したB毎に以下の処理
→辞書Dにある場合、DからBの行を取得しansの対象行に1加算
・ansの中の最大値を出力して終了
あんまりスムーズな感じではありませんが、上記実装でACとなりました。
ちょっと躓いたのは。Bの中にAのリストにない数字がある点でした。
https://atcoder.jp/contests/abc437/submissions/71837962
3.C - Reindeer and Sleigh 2
問題を読み「こ、これはbitDP？」と思いましたがC問題でそれはないか・・・
となるとDPか・・・と、勝手な決めつけ。
【考え方（TLE）】
・初期値を全トナカイがそりを引いている状態とする
・DPを何匹目のトナカイで、何匹のトナカイをそりにのせられるかの表で
値を牽引力とそりに乗っている重量で保持する
上記で作ったところTLEやMLEが出てしまう。
色々試行錯誤するも上手くいきませんでしたが
その過程で、以下の考え方に気づきました。
【考え方】
・そりを引いている馬のパワー合計からそりに乗っている馬の重さの合計を引いた値を
余剰牽引力とした場合、余剰牽引力はプラスでなければいけない
・ある馬がそりを引く状態からそりに乗る状態に変化する場合
変更前の余剰牽引力から、対象の馬のP+W(以下牽引影響力)をマイナスすることで余剰牽引力を示せる
・ケースごとに全トナカイをそりを引いている状態として余剰牽引力を求め
牽引影響力の昇順でトナカイをそりに乗せていき、余剰牽引力が
0より下になる一匹前までがトナカイをそりに乗せられる上限となる
上記考え方で実装したらあっさりACを頂きました。
最初の方向性を間違えたせいでだいぶ順位を落とした気がします・・・。
https://atcoder.jp/contests/abc437/submissions/71871344
以上