CodeQUEEN 2023 予選 (AtCoder Beginner Contest 308)をPythonで解く-Shinoryo's Weblog

Daniel AgreloによるPixabay(https://pixabay.com/)からの画像

こんにちは, Shinoryoです.

今回はCodeQUEEN 2023 予選 (AtCoder Beginner Contest 308)を, Pythonで解いてみた結果を書き連ねていこうと思います.

A - New Scheme

問題文にある条件を愚直に判定すればよいです.

B - Default Price

皿の色$C_i$を順番に調べていって, 対応する金額の和を取っていけばよいです.

C - Standings

問題文のまま実装すると, 浮動小数点型の誤差によりWAとなります.

浮動小数点型の計算の精度を上げる

四倍精度浮動小数点形式を用いることで, この誤差を解消することができます.

整数の範囲で比較する

$A_i / (A_i + B_i) < A_j / (A_j + B_j)$の大小比較は, $A_i (A_j + B_j) < A_j (A_i + B_i)$の大小比較にすることで, 整数の範囲で比較することができます. 高速な安定ソート(e.g. マージソート)のロジックにこれを組み込むことで, 問題を解くことができます.

D - Snuke Maze

原点マス$(0, 0)$に対して, そのマスからどのマスに進めるかを調べて, 行くことができるマスを調べていくことを考えます. これを数え上げる有効な方法として, AtCoder Beginner Contest 177の「D - Friends」と同様に, 幅優先探索(breadth first search; BFS)と呼ばれる方法を用います.

幅優先探索は, 他にも以下で取り上げています.

E以降

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

参考にしたサイト等

「解説 - CodeQUEEN 2023 予選 (AtCoder Beginner Contest 308)」
Editorial - AtCoder Beginner Contest 308
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.
「ソート - Wikipedia」
ソート - Wikipedia
No description
takayg様の「Pythonでアルゴリズム（幅優先探索, bfs）」
Pythonでアルゴリズム（幅優先探索, bfs） - Qiita
#はじめに　pythonを使った幅優先探索の実装について解説していきます. （僕がいつも実装するやつを載せるだけです. ）　幅優先探索ではよく距離についての問題が出てくるので, 今回はある1頂点から各…
nkmk様の「Pythonのdequeでキュー, スタック, デック（両端キュー）を扱う」
Pythonのdequeでキュー, スタック, デック（両端キュー）を扱う | note.nkmk.me
Pythonの標準ライブラリcollectionsモジュールのdeque型を使うと, データをキューやスタック , デック（両端キュー）として効率的に扱うことができる. collections.deque --- コンテナデータ型 — Python 3.11.4 ドキュメント組み込みのリストlistをキューやスタック, デック（両端キュー）として使うことも可能だが, リス...

CodeQUEEN 2023 予選 (AtCoder Beginner Contest 308)をPythonで解く

A - New Scheme

B - Default Price

C - Standings

浮動小数点型の計算の精度を上げる

整数の範囲で比較する

D - Snuke Maze

E以降

参考にしたサイト等

0 件のコメント:

コメントを投稿 (Please feel free to ask me about your questions! You can use Japanese or English in the comments.)

Search

About Me

Labels

Blog Archives

Twitter