AtCoder Beginner Contest 188をPythonで解く

こんにちは, Shinoryoです.

今回はAtCoder Beginner Contest 188を, Pythonで解いてみた結果を書き連ねていこうと思います.

AtCoder Beginner Contest 188 - AtCoder

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

A - Three-Point Shot

$X + 3 > Y$の判定を行えばよいです.

B - Orthogonality

内積を愚直に計算すればよいです.

C - ABC Tournament

トーナメントを実際に再現します. 生き残った人のリストはもちろんのこと, 生き残った人がもともと何番目だったかの情報も必要なので, その番号のリストも作成し管理します.

求めるのは準優勝した人なので, トーナメントを再現するのは準決勝までとなります.

D - Snuke Prime

$1 \leq a_i \leq b_i \leq 10^9$なので, 単純にいもす法を用いるのだとできません.

各々のサービス(サービス料金$1$日あたり$c_i$円)を$a_i$日目から$b_i$日目まで利用するという入力データがあるわけですが, これを

• $a_i - 1$日目と$a_i$日目の間に利用料金が$c_i$円増加するイベントが発生する
• $b_i$日目と$b_i + 1$日目の間に利用料金が$c_i$円減少するイベントが発生する

に分解して考え, これをまとめて

• $d_i$日目と$d_i + 1$日目の間に利用料金が$c_i$(マイナスもあり得る)円増加するイベントが発生する

と考え, データをまとめてソートします.

この料金増減イベントを再現していくことで求めます.

E以降

E以降は私の能力不足故に省略いたします.

参考にしたサイト等

• 「解説 - AtCoder Beginner Contest 188」
  Editorial - AtCoder Beginner Contest 188

  AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

• nkmk様による「Pythonでリスト（配列）の要素を削除するclear, pop, remove, del」
  Pythonでリスト（配列）の要素を削除するclear, pop, remove, del | note.nkmk.me

  Pythonでlist型のリスト（配列）の要素を削除するには, リストのメソッドclear(), pop(), remove()を使う. そのほか, インデックスやスライスで位置・範囲を指定してdel文で削除する方法もある. すべての要素を削除: clear() 指定した位置の要素を削除し, 値を取得: pop() 指定した値と同じ要素を検索し, 最初の要素を削除:...