2023-07-03

AtCoder Beginner Contest 308に参加した

競プロアルゴAtCoder

ABC308の参加記．

7月1日に開催されたCodeQUEEN 2023 予選 (AtCoder Beginner Contest 308)に参加した．結果はABCDEFの6完，提出するのが遅く水パフォで1125位だった．

A - New Scheme

問題文

8個の整数 $S_1, \cdots, S_8$ が与えられ，特定の条件を満たすかどうかを判定する問題．

やるだけだが，「すべての $i$ について $S_i$ が条件 $P$ を満たす」かどうかを判定するよりも「 $S_i$ が条件 $P$ を満たさないような $i$ が存在する」かどうかを判定するほうが実装が楽．

提出：https://atcoder.jp/contests/abc308/submissions/43087977

B - Default Price

問題文

皿の色ごとに値段が決まっている料理を $N$ 個食べたとき，合計金額を求める問題．色をキーにして値段をDictionary型で保持すればよいが，価格リストにない色が来た場合ときだけ注意が必要．

提出：https://atcoder.jp/contests/abc308/submissions/43090499

C - Standings

問題文

人 $1, \cdots, N$ を $P_i\equiv A_i/(A_i+B_i)$ の降順でソートする問題． $P_i$ の値を小数でじかに持つと誤差の関係で落ちるので，まじめに比較関数を書いてやる必要がある．

落ちるだろうなーと思いながらとりあえず提出してペナを出すのをやめたい．

提出：https://atcoder.jp/contests/abc308/submissions/43099789

D - Snuke Maze

問題文

英小文字が書かれた $H\times W$ のグリッドがあり，"snuke"という文字列をたどるようにして左上から右下まで到達できるかを判定する問題．

隣のマスに遷移できるかどうかは「隣のマスに書かれている文字」のほかに「"snuke"の何文字目まで読んだか」で決まるので，「現在いるマス」と「"snuke"の何文字目まで読んだか」を状態に持ってBFSすればよい．

提出：https://atcoder.jp/contests/abc308/submissions/43107522

E - MEX

問題文

面白かった！

$0,1,2$ からなる長さ $N$ の数列 $A$ と，M, E, Xのみからなる長さ $N$ の文字列 $S$ が与えられるので，

\sum_{\substack{i<j<k\\ (S_iS_jS_k="{\rm MEX}")}}{\rm mex}(A_i, A_j, A_k)

を求める問題．

よく考えると， ${\rm mex}$ の値は $0,1,2,3$ の $4$ 通りしかない．だから， ${\rm mex}$ の値ごとに，その値が何回加算されるかが分かればよい（いわゆる「主客転倒」というテクニック）．

例えば， ${\rm mex}(A_i, A_j, A_k)=1$ になるのはどういうときかというと

$A_i, A_j, A_k$ のうち少なくとも1つが $0$ で，いずれも $1$ ではない

とき．だから， ${\rm mex}(A_i, A_j, A_k)=1$ となるような組 $(i, j, k)$ の個数を求めるには

文字列 $S$ の（連続するとは限らない） $3$ 文字の部分文字列 $T$ で， $T=$ "MEX"かつ対応する $A$ の値に $0$ が少なくとも1個含まれ， $1$ が含まれないようなものの個数

が分かればよく，これは

${\rm dp}[i][j][k]$ ： $i$ 番目の要素までみたとき，MEXの $j$ 文字目まで選んでいて，すでに登場した数の集合が $k$

という形のDPで求められる（ $k$ はbitDPの容量で2進数でもつ）．

${\rm mex}$ の値が他の値になる場合についても，このDPテーブルの値を使えば求められるので，全体として $O(N)$ で解くことができた．

提出：https://atcoder.jp/contests/abc308/submissions/43115620

F - Vouchers

問題文

こういう感じの，貪欲をひねり出す問題が苦手．

$N$ 個の商品があり，商品 $i$ の定価は $P_i$ と決まっている．実は $M$ 枚のクーポンを持っており，クーポン $j$ をある商品に適用すると，その商品が $D_j$ 円引きになる．ただし，クーポン $j$ は定価 $L_j$ 円以上の商品にしか使用できないし，クーポンと商品の対応は単射でないといけない．このとき，うまくクーポンを使って $N$ 個の商品を買うときの合計金額を最小化せよ，というのがこの問題の主旨．

クーポンに適用可能な定価の下限があるのがやっかいだ．

ひとまずこの制限がない場合を考えると，明らかに値引き額の大きいクーポンから順に使っていくのが最適である．また，最終的に使うクーポンの集合が同じであれば，どのクーポンをどの商品に使っても同じ（最終的な合計額のみが問題だから）．

次に制限がある場合を考える．この場合には，どのクーポンをどの商品に使うかが重要になってくる．定価の高い商品ほど，適用可能なクーポンの選択肢が減ることに気づくと，以下のような貪欲が回るように思える．

以下の操作を繰り返す：
- まだ使用していないクーポンのうち最も割引額が大きいものを選び，このクーポンが使用できる商品のうち最も定価が安いものにクーポンを適用する．

実際にこれは正しい（本番では正当性を証明せずに提出したが，ユーザ解説などに詳しい説明がある）．

実装する際には，まだクーポンを使用していない商品の集合を管理し，その都度，ある値以上の最小の要素を取得する必要がある．Pythonにはmultiset上の二分探索どころかmultisetすらないので，慣れないC++を書く羽目になりかなり時間を取られた．

提出：https://atcoder.jp/contests/abc308/submissions/43141628