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

こんにちは, Shinoryoです.

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

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

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

A - Weekly Records

組み込み関数sum()を用いて計算することができます.

B - racecar

「$S_1$～$S_N$から2個($S_i$, $S_j$)選んで並べる順列」の全てに対してループさせて, それぞれで$S_i$と$S_j$をこの順に連結した文字列が回文となるかを調べればよいです. そのような順列を順番に取り出していくのには, itertools.permutationを使うと便利です.

C - Ideal Sheet

ここでは, シート$X$を切り出す範囲をあらかじめ決めておくことにします. 具体的には, シート$C$の座標$(0, 0)$から$(H_X - 1, W_X - 1)$の範囲を切り出すことにします. この切り出す範囲に対して, シート$A$とシート$B$をどのように配置するかを考えるのです.

高橋君が目標を達成できるシート$A$とシート$B$の配置は, 以下の3つの条件をすべて満たせばよいことが分かります.

シート自体は大きくないので, これを愚直に実装すればACとなります. CPython 3.11.4だと, 適切にbreakしないとTLEになる場合があります.

あるいは, シート$X$に余計な黒いマスがあっては条件を満たせないことから, 上記の条件は次のように書き換えられます.

黒いマスの位置をキャッシュしておくことで, さらに高速にこの問題を解くことができます.

なお, 上記のコードでは, 多重ループの記述に多重ループitertools.product()を使用しています.

D - Mismatched Parentheses

解説にもあるように, 「先頭から順に見て, )を見つけるたびに, 直前の(までを削除する」を実行すればよいです. 直前の「(」を覚えておくスタックや, 出力する文字列を記録しておくスタックは, Pythonではcollectionsモジュールのdeque型を用いれば簡単に実装できます.

E以降

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

参考にしたサイト等

• 「解説 - 東京海上日動プログラミングコンテスト2023（AtCoder Beginner Contest 307）」
  Editorial - Tokio Marine & Nichido Fire Insurance Programming Contest 2023（AtCoder Beginner Contest 307)

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

• nkmk様による「Pythonで階乗, 順列・組み合わせを計算, 生成」
  Pythonで階乗, 順列・組み合わせを計算, 生成 | note.nkmk.me

  Pythonではmathモジュールを使って階乗や順列・組み合わせの総数を算出できる. SciPyでも順列・組み合わせの総数を算出する関数が提供されている. また, itertoolsモジュールを使ってリストなどから順列・組み合わせを生成して列挙することも可能. 階乗: math.factorial() 順列の総数を算出math.perm()scipy.special.perm()...

• nkmk様による「Pythonのfor文によるループ処理（range, enumerate, zipなど）」
  Pythonのfor文によるループ処理（range, enumerate, zipなど） | note.nkmk.me

  Pythonのfor文によるループ処理（繰り返し処理）について説明する. 基本的な文法と, for文とrange()やenumerate(), zip()などを組み合わせて使う例を紹介する. 8. 複合文 (compound statement) - for文 — Python 3.11.3 ドキュメント Pythonのfor文の基本的な書き方: for ... in ... :Pythonのfor文は他言語のforeach文と...

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

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