AtCoder Beginner Contest 188 備忘録

SDESTINY

AtCoder Beginner Contest 188 の備忘録です。

問題はこちら↓

今回はABCD4完でした。

・A問題:Three-Point Shot

バスケットボールの試合が行われており、現在の両チームの得点は X 対 Y です( X ≠ Y )。現在劣勢のチームが3ポイントシュートを1本成功させて相手よりも高い得点となるか判定する。
X と Y をのうち得点の低い方に3点追加し相手よりも多いか比較すれば良い。

解答例(Python)
https://atcoder.jp/contests/abc188/submissions/19355730

・B問題:Orthogonality

2つの N 次元ベクトル A = ( A1,A2,A3,...,An) , B = ( B1,B2,B3,...,Bn) が与えられる。A と B の内積が0かどうかを判定する。内積が 0 とは

A1*B1+A2*B2+A3*B3+…,An*Bn = 0

の事を言う。
N≦100000 程度なので愚直に計算していく事で求める事ができる。

解答例(Python)
https://atcoder.jp/contests/abc188/submissions/19356282

・C問題:ABC Tournament

選手 1 から選手 2^N 人の選手がトーナメント形式のプログラミング対決をする。選手 i のレートは Ai である。どの2選手のレートも異なり、2里の選手が対戦すると常にレートの高い方が勝つ。トーナメント表は完全二分木の形をしており、正確には以下の要領で行われる。

・i = 1,2,3,...N について順に、以下のことが行われる。
　・各整数 j ( 1 ≦ j ≦ 2^(N-i)) について、まだ負けたことのない選手のうち、
　　2j-1 番目に番号の小さい選手と 2j 番目に番号の小さい選手が対戦する。

準優勝する、すなわち最後に行われる対戦において負ける選手の番号を求める。
N≦16 と小さい為、全ての対戦を調べていく事で求めることができるが、トーナメントの構造上、決勝戦では前半分でレートのもっとも高い選手と後ろ半分でもっともレートの高い選手が対戦することになるので、それぞれ調べて比較することでも求めることができる。Pythonの場合は、リスト[ : 2**n//2 : ]のように記述することによりリストの特定の範囲内に絞って(スライス)取り出すことができる。

解答例(Python)
https://atcoder.jp/contests/abc188/submissions/19357702

・D問題:Snuke Prime

株式会社すぬけは様々なサービスを提供している。この会社は、すぬけプライムという支払いプランを用意しており、加入中は1日あたり C 円を支払うことで、提供される全てのサービスを追加料金の支払いなしに利用することができる。すぬけプライムへの加入および脱退は、それぞれ1日のはじめおよび終わりに自由に行うことができる。
高橋くんは、この会社のサービスのうち N 個を利用しようとしている。そのうち i 個目のサービスは、今日を1日目として、ai 日目の初めから bi 日目の終わりまで利用する予定である。
すぬけプライムに加入していない期間中は、i 個目のサービスを利用する際に1日あたり ci 円を支払う必要がある。
サービスを利用する為に高橋くんが支払う必要のある最小の合計金額を求める。
まずすぬけプライムに加入しない場合を考える。これは 全てのサービスを利用したとしても支払い金額がすぬけプライムの利用料よりも少なくなる場合である。この時は (bi - ai + 1) * ci で各サービスの利用料を求めて足すことで求めることができる。
問題は複数利用した場合にすぬけプライムの利用料を超える時がある場合で、愚直に求めようとすると利用する日数分だけかかるので O(max(b)) となるが、bi ≦ 10^9 と非常に大きい為間に合わない。そこで利用料の変化するタイミングだけを考えてみる。開始時と終了時だけを見ればよい為 2N 程度となり、N ≦ 2*10^5 からこの程度であれば十分間に合う。開始日と利用料、終了日と利用料をそれぞれ合わせて持つリストを作成し(①)、日にちでソートしておく。また、利用料は開始時は + 、終了時は - にして持っておくとあとで計算する際に処理を分ける必要がなくなり楽になる。次に開始時、終了時に変化した利用料の合計を求める為リストを用意する(②)。初期値は 0 とし、先に作成したリストを元に累積和で求めていく。先の処理時に終了日の利用料を - にしておくと開始日と同様に、直前までの利用料に足すことで計算できるようになる。最後に①のリストから次の変化するまでの日数を求めて、それに②のリストで得た利用料か C のうち少ない方を掛けたものを足していくことで求めることができる。

解答例(Python)
https://atcoder.jp/contests/abc188/submissions/19360172

この記事が気に入ったらサポートをしてみませんか？