Home / Python /

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

投稿日：　

Atcoder Python

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

こんにちは, Shinoryoです.

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

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

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

A - N-choice question

$A + B$を求めて, $C$の中にそれと一致するものが存在するかを調べればよいです. for文を用いて次のように実装できます.

あるいは, リストのメソッド.index()を用いて, リストの要素のインデックスを取得することもできます. インデックスと選択肢の番号は$1$ずれていることに注意してください.

B - Same Map in the RPG World

「$s$回縦方向シフトしたあとの$A$」と「$s + H$回縦方向シフトしたあとの$A$」が一致することや, 「$t$回横方向シフトしたあとの$A$」と「$t + W$回横方向シフトしたあとの$A$」が一致することから, $H$回以上の縦方向シフトや, $W$回以上の横方向シフトを考える必要はありません. 純粋に全シフトパターンを確かめても, 少ない計算量で済みます.

numpyのnp.roll()を用いれば, 配列をシフトさせたものを簡単に取得することができます.

あるいは, numpyを用いずに, 配列のシフトを実装しても良いです.

さらに, 配列のシフトを実装するのではなく, $A$と$B$が一致しているかを調べるところで, $A$の要素のインデックスをずらしていくだけで十分です. $s$回縦方向シフトして$t$回横方向シフトした$A$と$B$を比べるときは, A[(i + s) % H][(j + t) % W]とB[i][j]を比較すればよいのです.

C - Cross

一つひとつの#マスに対して, その周囲のマスが#であるかどうかを愚直に調べていくことで, 解くことができます.

あるいは, #マスがバツ印以外には使われていないことを利用して, #が何マス連結しているかを調べていくことでも, この問題を解くことができます.

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

Union Findは, AtCoder Beginner Contest 214をPythonで解くのD - Sum of Maximum Weightsでも登場しています.

AtCoder Beginner Contest 214をPythonで解く

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

D - AABCC

$N \leq 10^{12}$であるので, $c$の最大値は

\begin{align} 2^2 \times 3 \times c^2 &= 10^{12} \end{align}

を解いて$c = 288675$と得られます. ゆえに, $a$, $b$, $c$の取りうる数の一覧表として, まず$288675$までの素数のリストを取得する必要があります. これはEratosthenesの篩を用いることで得ることができます. Eratosthenesの篩は数学などでよく知られた手法ですが, 例えば以下のサイトをご覧ください(外部).

エラトステネスのふるいとその計算量 | 高校数学の美しい物語

エラトステネスのふるいのアルゴリズムと具体例を解説. 計算量を導出し，愚直な素数判定の方法と比較します.

Pythonでは例えば以下のように実装できます. 整数$n$を与えると, その整数以下の素数のリストを返す関数です.

後は, $a = 2$, $b = 3$, $c = 5$から順番に, 問題文の条件に適している個数をカウントしていくだけです. 三重ループになりますが, ループの途中で適切にbreakを挟むことで, TLEにならずにACすることができます. 公式解説では一番深いところのbreakだけで済むという記述がありますが, Pythonではおそらく全てのループで適切なbreakを挟まないとTLEになります(間違えていたら申し訳ございません).

E以降

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

参考にしたサイト等