Home / Python /

AtCoder Beginner Contest 322をPythonで解く

投稿日：　

Atcoder Python

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

こんにちは, Shinoryoです.

今回はAtCoder Beginner Contest 322を, Pythonで解いてみた結果を書き連ねていこうと思います.

AtCoder Beginner Contest 322 - AtCoder

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

A - First ABC 2

問題文にある条件を愚直に試していくことで実行できます. $i$番目から$i + 2$番目までの文字を調べるので, $i$としてループさせるべき数値の範囲に注意してください.

B - Prefix and Suffix

例えば, $S$が$T$の接頭辞であることは, 以下をすべて確かめることによって確かめられます.

  • $S$の$1$文字目が$T$の$1$文字目と一致する.
  • $S$の$2$文字目が$T$の$2$文字目と一致する.
  • ……
  • $S$の$N$文字目が$T$の$N$文字目と一致する.

同様に, $S$が$T$の接尾辞であることは, 以下をすべて確かめることによって確かめられます.

  • $S$の$1$文字目が$T$の$M - N + 1$文字目と一致する.
  • $S$の$2$文字目が$T$の$M - N + 2$$文字目と一致する.
  • ……
  • $S$の$N$文字目が$T$の$M$文字目と一致する.

C - Festival

最初に$x = 1$とします. 以下のようにすることで, この問題を解くことができます.

  • $i$日目に対する出力は, $A_x - i$となります. これを出力します.
  • $i = A_x$ならば, $x$に$1$を加えます.

あるいは, $i$日目に対してそれに近い$A_j$を二分探索する方法でも, (時間計算量はかかりますが)解くことができます.

D - Polyomino

$4 \times 4$のグリッドに対するポリオミノの貼り付け方を全探索すれば, 答えを得ることができます. そのあり得るポリオミノの貼り付け方を全列挙するのが難しいのです.

あるポリオミノの貼り付け方を全列挙したリストを作成するには, 例えば以下のようにします.

  1. あり得る全ての平行移動に対して, ポリオミノが$4 \times 4$の枠からはみ出ないものをリストに加える.
  2. ポリオミノを90度回転して, 1に戻る.

実際にグリッドにポリオミノを貼り付ける際には, 重ならないように, かつまんべんなく敷き詰められなければならないことに注意してください.

ポリオミノを扱う際は, 外側の空白地帯も含め, $4 \times 4$の2次元配列のまま扱うとスムーズです.

E以降

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

参考にしたサイト等