Home / Python /

東京海上日動プログラミングコンテスト2023（AtCoder Beginner Contest 304）をPythonで解く

投稿日：　

Atcoder Python

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

こんにちは, Shinoryoです.

今回は東京海上日動プログラミングコンテスト2023（AtCoder Beginner Contest 304）を, Pythonで解いてみた結果を書き連ねていこうと思います.

Tokio Marine & Nichido Fire Insurance Programming Contest 2023（AtCoder Beginner Contest 304) - AtCoder

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

A - First Player

Aの最小値とそのインデックス(A_min_index)を取得し, A_min_index以降の要素を出力した後, A_min_indexより前の要素を出力すればよいです.

B - Subscribers

$N$を文字列まま入力を受け付けて, 4文字目以降をすべて$0$に置き換えればよいです.

C - Virus

下の図のように, 人の間の距離が$D$以内の人同士をくっつけていくことを考えます.

このようにくっついた人同士の集合というのを考えることができます.

もし$1$の人が感染したら, 最終的には$1$の人が含まれる集合に属する人は感染しますが, それ以外の人には感染しないことになります.

このような操作は例えば, Union Findを用いて実装することができます. 最初は1つひとつバラバラな要素(人)が用意されます. そして, 「2つのまとまり(人)をつなげる」という操作を繰り返し, 最終的にある要素がどの集合に属しているかを管理していくアルゴリズムです.

「2つのまとまり(人)をつなげる」という操作に時間計算量が$\mathcal{O}(N^2)$かかります. Python3.8だとTLEですが, PyPy3だとACです.

以下の例では, nkmk様による「PythonでのUnion-Find（素集合データ構造）の実装と使い方」(https://note.nkmk.me/python-union-find/)に掲載されているUnion Findのコードを使用しています.

Union Findは, 以下のAtCoder Beginner Contestでも登場しています.

AtCoder Beginner Contest 214をPythonで解く

こんにちは, Shinoryoです. 今回は AtCoder Beginner Contest 214 を, Pythonで解いてみた結果を書き連ねていこうと思います. AtCoder Beginner Contest 214 - AtCoder AtCoder is...

ユニークビジョンプログラミングコンテスト2023 春 (AtCoder Beginner Contest 300)をPythonで解く

こんにちは, Shinoryoです. 今回は ユニークビジョンプログラミングコンテスト2023 春 (AtCoder Beginner Contest 300) を, Pythonで解いてみた結果を書き連ねていこうと思います. ユニークビジョンプログラミングコンテスト...

D - A Piece of Cake

左から$X$列目, 下から$Y$行目にあるピースのIDを$(X,Y)$と定めます($X, Y$の取りうる数には$0$を含みます).

ある苺の座標を$(p, q)$, ケーキを通る$y$軸に並行な異なる直線の座標を$(a_1, a_2, \ldots, a_A, W)$, ケーキを通る$x$軸に並行な異なる直線の座標を$(b_1, b_2, \ldots, b_B, H)$とします(便宜上, $W$, $H$もくっつけておきます). すると, その苺が乗っているピースのIDの$X$の方は, $(a_1, a_2, \ldots, a_A, W)$の中に$p$を挿入する位置のインデックスとして得ることができます. 同様に, その苺が乗っているピースのIDの$Y$の方は, $(b_1, b_2, \ldots, b_B, H)$の中に$q$を挿入する位置のインデックスとして得ることができます.

その位置の情報をもとに, (ピースのID,そこに乗っている苺の数)のタプルを, 苺の数の多い順に出力することができます. $m$に関しては, 以下の2パターンが考えられます.

  • 苺の乗っているピースが$(A + 1) \times (B + 1)$(ピースの総数)よりも少ない場合
    $\Rightarrow$ $m = 0$となります.
  • 苺の乗っているピースが$(A + 1) \times (B + 1)$(ピースの総数)と等しい場合
    $\Rightarrow$ $m$としては先ほどのタプルのリストの最も後ろ側を参照します.

$M$に関しては, 先ほどのタプルのリストの最も前側を参照します.

二分探索にはbisectモジュールを, (ピースのID,そこに乗っている苺の数)のタプルを苺の数の多い順に出力するのにはCollectionsモジュールを使用することができます.

E以降

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

参考にしたサイト等