Home / Python /

トヨタ自動車プログラミングコンテスト2024#3（AtCoder Beginner Contest 344）をPythonで解く

投稿日：　

Atcoder Python

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

こんにちは, Shinoryoです.

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

Toyota Programming Contest 2024#3（AtCoder Beginner Contest 344） - AtCoder

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

A - Spoiler

|の位置を探して求める

1つ目の|の位置$i$と2つ目の|の位置$j$を求めます. 文字列$S$の$i$文字目より前と$j$文字目より後を連結したものを出力すればよいです.

正規表現を用いる

正規表現を用いて, 「|と|で囲まれた文字列」を空白で置換します.

B - Delimiter

$A_i$を順番に読み込み, 記憶していきます. $0$が入力されたら, 記憶していたそれまでの入力を逆順に出力すればよいです. $A_N = 0$であることが保証されていることに注意してください.

C - A+B+C

$A$, $B$, $C$から1つずつ要素を選んで和を取ることによって得られる数字の全パターンを計算しておきます. これに$X_i$が含まれているかによって, Yesを出力するかNoを出力するかを判定します.

全パターン計算に$O(NML)$, 各問題を解くのに$O(1)$, 合計で$O(NML + Q)$でこの問題を解くことができます.

D - String Bags

次の2次元配列を順に埋めていく動的計画法によって, この問題を解くことができます.

  • dp[i][j]: $i$個目の袋まで処理した結果, $T$の最初から$j$文字目まで一致させるのにかかる最小金額

$i$個目の袋まで処理した結果, $T$の最初から$j$文字目まで一致させることができたとします. このとき, 次のようにdpを更新していきます.

  • $i + 1$個目の袋から何も取り出さなかった場合, dp[i + 1][j] = dp[i][j].
  • $i + 1$個目の袋から文字列$x$を取り出し, $T$の最初から$j + \mathrm{len}(x)$文字目まで一致させることできた場合, dp[i + 1][j + len(x)] = dp[i][j] + 1.

最終的に, dp[N][len(T)]を出力します.

本ブログでも, 過去に以下のような動的計画法を用いる問題を取り扱っています.

E - Insert or Erase

リストに対する挿入・削除を素早く行うには, 双方向連結リスト(doubly-linked list)というデータ構造を用いるのが良いです. 各ノードが1つ前・1つ後のノードへの参照を有します.

Doubly-linked-list
Lasindi, Public domain, via Wikimedia Commons

実際, 挿入・削除を行うには, 関係するノードのデータを変更するだけでよいです.

CPT-LinkedLists-addingnode
Singly_linked_list_insert_after.png: Derrick Coetzeederivative work: Pluke, Public domain, via Wikimedia Commons
CPT-LinkedLists-deletingnode
Pluke, Public domain, via Wikimedia Commons

典型的な双方向連結リストの場合, ある値に対応するノードを探すには, リストの先頭からノードをたどっていく必要があります. そのため, ある値に対応するノードを効率的に探す手法を用意することで, 計算時間を短縮する必要があります. Pythonでは辞書(dict型)を用いることができます.

私用したIntLinkedListは, GitHubにも投稿してあります.

GitHub - Shinoryo/IntLinkedList: Double-linked list in Python for storing integers.

Double-linked list in Python for storing integers. - Shinoryo/IntLinkedList

F以降

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

参考にしたサイト等