コンテスト時間: 2024-06-15(土) 21:00 ~ 2024-06-15(土) 22:40 (100分)
A - Welcome to AtCoder Land
Difficulty: ???
解答時間: 1:36
- 文字列
が与えられる。
AtCoder、Landであるか判定せよ。
- これは
ifを書くだけ。瞬殺。
B - Ticket Counter
Difficulty: ???
解答時間: 5:23
- 1つのチケット売り場があり、来園客はこのチケット売り場の前に一列に並んで順にチケットを購入する。チケットの購入手続きには一人当たり
秒かかり、列の先頭の人がチケットを購入し終わると、 (存在すれば) 次の人がすぐさま購入手続きを開始する。現在チケット売り場に並んでいる人はおらず、今から
人の人が順にチケットを買いに来る。具体的には、
番目の人は今から
秒後にチケット売り場を訪れ、既に列が存在すればその最後尾に並び、存在しなければすぐさま購入手続きを開始する。各
- 問題文がちょっと複雑だが、冷静に考えれば難しくはない。
- 時間を記録する変数
timeを持っておき、各のとき (列が存在しているとき) のみ、
を
- 常に、
を加算する (手続き処理をする) 。
- このときの
timeを出力する。
とすればよい。
C - Popcorn
Difficulty: ???
解答時間: 9:28
から
までの
によって表され、
oであるとき売り場のポップコーンを売っていることを、
xであるとき売っていないことを示す。どの売り場も最低1種類の味のポップコーンを売っており、どの味のポップコーンも最低1つの売り場で売られている。すべての味のポップコーンを購入するためには最低何個の売り場を訪れる必要があるか求めよ。
- 制約を見ると
と非常に小さいので、各ポップコーン売り場について訪れるか訪れないかを
通りすべて試すことができる。これはお馴染みbit全探索の出番だ。
- bit全探索さえ分かっていれば特に難しいところはなく、あとは問題文の通りに実装していけばよい。
D - Souvenirs
Difficulty: ???
解答時間: 59:48 + WAx2
- お土産屋に
の番号が付いた
の名前が付いた
- 各
について、人
個以上のお菓子が入った箱を渡す。
- 各
1人に2個以上の箱を渡したり、同じ箱を複数人に渡したりすることはできない。これらの条件を満たしつつ適切に 個の箱を買うことができるか判定し、可能な場合は支払う金額の合計の最小値を出力せよ。そうでない場合は
-1を出力せよ。
- 私の実装は以下の通り。
- まず
を降順ソートする。
- 次に
Boxを作成し、お菓子の数で降順ソート。 - 各人の要求に応じて、条件を満たす箱を価格基準の
priority_queueにpushする。 - 先頭から
popしていき、合計金額を求める。
- 30分ほど考えて解説に近いコードを書いたものの、
vectorにeraseを掛けていたため TLE 。multisetが完全に頭から抜け落ちていて別方針で考え直したため、1時間も溶かしてしまった。
