Home / Python /

京セラプログラミングコンテスト2023(AtCoder Beginner Contest 305)をPythonで解く

投稿日：　

Atcoder Python

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

こんにちは, Shinoryoです.

今回は京セラプログラミングコンテスト2023(AtCoder Beginner Contest 305)を, Pythonで解いてみた結果を書き連ねていこうと思います.

KYOCERA Programming Contest 2023（AtCoder Beginner Contest 305） - AtCoder

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

A - Water Station

スタート地点にある給水所を$0$番目とし, それ以降も含めて$i$番目の給水所というようにナンバリングします. すると, $N \, \mathrm{km}$地点に一番近い給水所の番号は, $N / 5$を四捨五入することによって得られます. 最後にその番号を$5$倍すれば, その給水所が何$\mathrm{km}$地点にあるかを求められます.

Pythonでは組み込み関数round()を用いることで, 四捨五入を行うことができます.

あるいは, 正数に対する四捨五入は, 「$0.5$を足して切り捨てる」というアルゴリズムによって得ることができます. これを利用すれば, 浮動小数点数演算による誤差を全く気にしなくてよくなります.

B - ABCDEFG

今回の実装方針は, 以下のようになります.

  1. 隣り合う点同士の距離を格納した配列distanceを用意する.
  2. 配列distanceの$i$番目から$j$番目までのスライス, distance[i:j]を取得する.
    • $i$と$j$は, 入力したアルファベット$p$, $q$に応じて適切な値にする.
  3. distance[i:j]の合計を出力する.

$i$と$j$は, アルファベットA～Gを0～6に変換して取得すればよいです. 以下の例では, 文字列「ABCDEFG」からそのアルファベットを検索することによって取得しています.

C - Snuke the Cookie Picker

#の数の各行の行合計を考えてみます. すると, 「$0$」「$a$」「$a - 1$」の3パターンに分かれます(ただし, $a$は行合計の最大値). 問題文の条件より, 「$a - 1$」のパターンは1行しか存在せず, その1行のどこかにすぬけ君がクッキーを取ったマスが存在することになります. 列に対しても同様であり, これによりすぬけ君がクッキーを取ったマスを求めることができます.

D - Sleep Log

以下の関数$f(x)$を求めることがキーになります.

  • $f(x)$：睡眠記録を取り始めてから$x$分後までに何分寝たか

この関数$f(x)$を用いれば, 各クエリに対して求める数は$f(r_i) - f(l_i)$であることが分かります.

$f(A_i)$のリストは, $i = 0$から順々に計算していくことで求めることができます. そこから任意の$x$に対する$f(x)$は, 以下のようにして求めることができます.

  1. $A_{j - 1} \leq x < A_j$となる$j$を探す.
  2. $f(x)$を以下の式によって求める: \begin{align} f(x) = f(A_{j - 1}) + \left( f(A_j) - f(A_{j - 1}) \right) \times \frac{x - A_{j - 1}}{A_j - A_{j - 1}} . \label{eq_2023-09-2023atcoder-beginner-contest-305python-1} \end{align}

なお, $f(A_j) - f(A_{j - 1})$は$A_j - A_{j - 1}$または$0$のいずれかです. つまり, 式\eqref{eq_2023-09-2023atcoder-beginner-contest-305python-1}を以下のように書き換えることができます: \begin{align} f(x) &= \begin{cases} f(A_{j - 1}) + \left( x - A_{j - 1} \right) & \text{if $f(A_j) - f(A_{j - 1}) > 0$}, \\ f(A_{j - 1}) & \text{others}. \end{cases} \end{align}

E以降

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

参考にしたサイト等

Search

About Me

自分の写真
理系大学生でした. Bloggerを利用して発信を行っています.

Labels