A問題

問題

メル君は使わなくなったスマホをメルカリで出品しようとしています。メル君は、販売中のどのスマホよりも安く、売り切れのどのスマホよりも高い値段で出品しようと考えています。

メルカリにはスマホが $N$ 個出品されており、それぞれ $1$ から $N$ までの番号が割り当てられています。 $i$ 番目のスマホの値段 $C_i$ と、販売状況を表す文字列 $S_i$ が与えられます。 $S_i$ が sold_out ならそのスマホが売り切れであることを表し、on_sale ならそのスマホが販売中であることを表します。

メルくんが決めた値段 $P$ が、以下の条件を満たすかを判定してください。

条件:全ての整数 $i(1\leq i\leq N)$ について

$S_i$ が on_sale なら $P<C_i$
$S_i$ が sold_out なら $C_i<P$

解答

on_saleの最小値とsold_outの最大値を求めて条件を確認するとよいです。C++だと std::min_element や std::max_element を使うと楽です。

実装

B問題

問題

メルカリには、ユーザー $1$ からユーザー $10^9$ までの $10^9$ 人のユーザーがいます。また、メルカリには、商品 $1$ から商品 $10^9$ までの $10^9$ 個の商品が $1$ つずつ出品されています。

はじめ、すべてのユーザーの幸福度は $0$ です。

次のような形式の情報が $N$ 個与えられます。 $i$ 番目の情報は以下の通りです。

ユーザー $u_i$ が商品 $v_i$ を購入すると、そのユーザーの幸福度が $h_i$ 上昇する。

ユーザーが $N$ 個の情報にない方法で商品を購入することはできません。すべてのユーザーの幸福度の合計が最大となるような購入方法を求めてください。購入方法とは、商品 $v_j$ がユーザー $u_j$ によって購入されることを表す情報 $(v_j,u_j)$ の集合です。ただし、 $1$ つの商品は一度のみ購入することができます。

なお、与えられる入力では、幸福度の合計が最大となる購入方法が一意に定まることが保証されています。

解答

ユーザーは何個でも商品を買えるので、各商品に対して買われたときに幸福度が最も上昇するユーザーを求めればよいです。mapで各商品の幸福度を管理すると楽です。

実装

C問題

問題

高さ $H$ cm、幅 $W$ cmのディスプレイがあります。このディスプレイ内を点が動くスクリーンセーバーを開発しました。ディスプレイの左下の座標を $(0,0)$ とし、ディスプレイの左下から右に $x$ cm、上に $y$ cm移動した点の座標を $(x,y)$ と表します。

時刻 $0$ 秒に点は $(s_x,s_y)$ にあります。はじめ、点は $(s_x,s_y)$ から $(s_x+1,s_y+1)$ 方向に秒速 $\sqrt2$ cmで真っすぐ進み出します。そして、この点は普通の光と同じように真っすぐ進み、画面端に到達すると同じ速度で反射します。

初期座標 $(s_x,s_y)$ が与えられるので時刻 $T$ 秒での点の座標を求めてください。

解答

$x$ 成分と $y$ 成分は独立に考えられます。 $x$ 成分で考えると、往復しているようになっているので $s_x+T$ を $2W$ で割ったあまりを求めるとよいです。( $W$ より大きい場合は、 $2W$ から引きましょう)

実装

D問題

問題

メルカリには $N$ 個のレアシューズが存在し、 $i$ 番目 $(1\leq i\leq N)$ のレアシューズは、時刻 $x_i$ に出品され、時刻 $y_i$ に出品が終了します。また、 $M$ 人のユーザーがレアシューズを購入しようとしています。 $j$ 番目 $(1\leq j\leq M)$ のユーザーは、時刻 $z_j$ にレアシューズを購入することを希望しており、 $x_i\leq z_j\leq y_i$ を満たすとき、 $i$ 番目のレアシューズを購入することができます。ただし、各ユーザーは $1$ つしかレアシューズを購入せず、購入されたレアシューズは他のユーザーが購入することはできなくなります。

各レアシューズをどのユーザーが購入するかを自由に選択できるとき、最大で何人のユーザーがレアシューズを購入できるかを求めてください。

解答

$(x_i,y_i)$ を $x_i$ が小さい順にソートしておきます。 $z_i$ が小さいものから、 $x_j \leq z_j$ を満たす全ての $(x_j,y_j)$ に対して、 multiset や priority_queue に $y_i$ を突っ込んでシミュレーションします。この際、 $z_j \leq y_j$ を満たす $y_j$ が存在しない場合は購入せず、存在する場合は条件を満たす最小の $y_j$ を選ぶことで、最適解を達成できます。

実装

E問題以降

まだ見てません