0.はじめに
先週はまさかの金曜開催で参加できず、１週ぶりの参戦。
さらに二泊三日の旅行から帰宅して２時間後の参戦と
ヘロヘロの状態。
と、言い訳しながらで、ABC問題を解くのがやっとでした。
C問題も解けたとはいえ、ダメもとで時間かかりそうな手法を取ったり
２分探索の大小比較を誤ったりして３回失敗し、タイムロス。
レートは-8と下がってしまいました。
1.A - Daily Cookie
制約により、@がD以上ある事がわかっているので
S内の”.”を数え、そこにDを加えることで空き箱の数がわかりました。
https://atcoder.jp/contests/abc382/submissions/60303224
2.B - Daily Cookie 2
Aよりちょっと難易度の高い問題。
とはいえ、B問題。
Sをリスト化して読み込み、後ろから見ていき、D枚分”@”を”.”に
変換し、最後にSを結合して出力。
https://atcoder.jp/contests/abc382/submissions/60308872
3.C - Kaiten Sushi
なかなかてこずった問題。
単純にBの寿司をAの人の頭から食べられるか
シミュレーションした場合、TLE18と半分以上時間切れ。
いい感じの表を作り、食べられる人を二分探索する方針を決める。
【考え方】
・美食度１の人が先頭にいたら全部この人が食べる
・同じ美食度の人がいたら前に座っている人が食べる
といったことから、以下の方針を取る。
1)Aのリストを元に、美食度毎の先頭の人を辞書D(キー：美食度、値：順番)に格納
2)Dを元に、リストL（L[i]＝[美食度,順番]、美食度の昇順)
3)Lを先頭から見ていき、L[i][1]に、L[i][1]とL[i-1][1]の小さいほうをセットする
（美食度5の前に、美食度1の人がいた場合、先に食べられてしまう為）
リストLには、美食度毎に何番目の人が食べるかがセットされる
4)リストBを先頭から見ていき、2分探索で、B[i]以上の美食度の料理を食べる人を
検索し、その値を出力
2分探索による時間短縮のお手本のような問題でした。
と思ったら、解説を見たらリストLを美食度毎につくれば2分探索いらない事に気づき
たしかにーとなりました。
https://atcoder.jp/contests/abc382/submissions/60342216
以上