トヨタ自動車プログラミングコンテスト2023#2(AtCoder Beginner Contest 302)をPythonで解く

こんにちは, Shinoryoです.

今回はトヨタ自動車プログラミングコンテスト2023#2(AtCoder Beginner Contest 302)を, Pythonで解いてみた結果を書き連ねていこうと思います.

TOYOTA MOTOR CORPORATION Programming Contest 2023#2 (AtCoder Beginner Contest 302) - AtCoder

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

A - Attack

$1 \leq A, B \leq 10^{18}$のため, 通常のPythonで用いられているfloat型だと精度が足りずWAになってしまいます. (ここでは, 切り上げにはmath.ceil()を用いています. )

解決方法としては, あくまでも整数の範囲で計算をする方法です. 例えば, $A$が$B$で割り切れれば$A / B$の切り捨て, 割り切れなければ$(A / B)$の切り捨てに$+1$したものを出力すればよいことが分かります.

あるいは, numpyを用いて浮動小数点型の精度を高める方法もあります. 四倍精度浮動小数点型だと仮数部が112ビットありますので, 十分に対応することができます.

B - Find snuke

B問題にしては面食らう感じにはなりますが, 結局は全ての文字列のパターンを調べることになるようです.

あるマス$(i, j)$に焦点を当てます. そのマスを1文字目とする調べるべき文字列は, そのマスから縦・横・斜めに伸びる5文字の文字列になります. それらの文字列が「snuke」に一致するかどうかを順番に調べていくのです.

これを全てのマスに対して繰り返していけばよいです. 縦・横・斜めに伸びる5文字の文字列を調べる際にインデックスエラーを起こさないように注意しましょう.

C - Almost Equal

${S_i}$を並べ替えた全てのパターンに対して, 条件を満たすかを確かめていけばよいです.

${S_i}$を並べ替えたものを${T_i}$として, $T_1$と$T_2$, $T_2$と$T_3$, ……を比較していって, 2箇所以上異なっている組み合わせがある場合には条件を満たさないことが分かるので, それを実装します.

D - Impartial Gift

公式解説の通りに実装すればよいです.

基本的には, なるべく$A$と$B$のそれぞれ最大値をとりたいのですが, それで差が$D$以内にならない場合には, $A$の最大値と$B$の最大値のどちらか大きい方を削除することで, 次の可能性を探ります. ($A$の最大値と$B$の最大値のどちらか小さい方を削除してしまうと, それらの差はますます広まってしまいます. )

Pythonで実装する際には, リストからの削除を.pop()などで実装すると, 時間計算量が多くTLEとなってしまいます.

例えば, 以下の対応が必要になります.

• collectionsモジュールのdeque型を用いて, 先頭・末尾の要素を追加・削除するのにかかる時間計算量を減らす.
• 先頭の要素を削除する代わりに, 注目する要素を一つ後ろにずらす.

1番目の方法を用いたコードです.

2番目の方法を用いたコードです.

E以降

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

参考にしたサイト等

• 「解説 - トヨタ自動車プログラミングコンテスト2023#2(AtCoder Beginner Contest 302)」
  Editorial - TOYOTA MOTOR CORPORATION Programming Contest 2023#2 (AtCoder Beginner Contest 302)

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

• nkmk様による「NumPyのデータ型dtype一覧とastypeによる変換（キャスト）」
  NumPyのデータ型dtype一覧とastypeによる変換（キャスト） | note.nkmk.me

  NumPy配列ndarrayはデータ型dtypeを保持しており, np.array()でndarrayオブジェクトを生成する際に指定したり, astype()メソッドで変更したりすることができる. Data type objects (dtype) — NumPy v1.21 Manual numpy.ndarray.astype — NumPy v1.21 Manual 基本的には一つのndarrayオブジェクトに対して一つのdtypeが設...

• nkmk様による「Pythonのdequeでキュー, スタック, デック（両端キュー）を扱う」
  Pythonのdequeでキュー, スタック, デック（両端キュー）を扱う | note.nkmk.me

  Pythonの標準ライブラリcollectionsモジュールのdeque型を使うと, データをキューやスタック, デック（両端キュー）として効率的に扱うことができる. collections.deque --- コンテナデータ型 — Python 3.7.3 ドキュメント 組み込みのリストlistをキューやスタック, デック（両端キュー）として使うことも可能だが, リスト...