Home / Python /

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

投稿日：　

Atcoder Python

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

こんにちは, Shinoryoです.

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

TOYOTA MOTOR CORPORATION Programming Contest 2023#1 (AtCoder Beginner Contest 298) - AtCoder

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

A - Job Interview

面接官の評価「良」の数を$A$, 面接官の評価「良」の不可の数を$B$とすると, Yesとなる条件は$A \geq 1$かつ$B = 0$となります.

B - Coloring Matrix

行列$A$を適切に回転したものと行列$B$とを比べる問題です. 行列$A$を回転することによりできる行列には, 以下の4つがあります.

  • 行列$A$
  • 行列$A$を反時計回りに${90}^\circ$回転させたもの
  • 行列$A$を反時計回りに${180}^\circ$回転させたもの
  • 行列$A$を反時計回りに${270}^\circ$回転させたもの

したがって, 上記4つの行列と行列$B$とをそれぞれ比べればよいことが分かります.

Pythonでは2次元配列の回転は, numpyのnp.rot90を用いることで簡単に実装できます. また, $A_{i,j} = 1$である全ての$(i,j)$に対して$B_{i,j} = 1$であるかどうかを確かめるには, 行列$B - A$の最小値が$0$以上であるかどうかを調べればよいことも分かります.

配列の回転を愚直に実装することもできます.

C - Cards Query Problem

実装手法自体はシンプルです. 配列$\mathrm{box}_i (1 \leq i \leq N)$を用意し, ここには箱$i$に入っているカードの番号を格納します. また, 配列$\mathrm{card}_j (1 \leq j \leq 200000)$を用意し, ここにはカード$j$が少なくとも1枚入っている箱の番号を格納します.

  • クエリ$1 \quad i \quad j$
    1. $\mathrm{box}_i$に$j$を格納する.
    2. $\mathrm{card}_j$に$i$が含まれていなければ, $\mathrm{card}_j$に$i$を格納する.
  • クエリ$2 \quad i$
    1. $\mathrm{box}_i$を昇順にソートしたものを出力する.
  • クエリ$3 \quad i$
    1. $\mathrm{card}_i$を昇順にソートしたものを出力する.

クエリ$1$のたびにソートを行ってしまうとTLEです.

D - Writing a Numeral

基本的には, 各クエリの処理に対して忠実になればよいです. 以下, 文字列$S$を整数型の配列として格納したものを$S$, 整数型として格納したものを$\mathrm{ans}$のようにします(例えば, $S$は[1,2,3,4,5], $\mathrm{ans}$は12345のようになります).

  • クエリ$1 \quad x$
    • $\mathrm{ans} = \mathrm{ans} \times 10 + x$
    • $S$の末尾に$x$を追加
  • クエリ$2$
    • $S$の要素数を取得し, これを$l$とする
    • $S$の先頭の要素を削除し, これを$y$とする
    • $\mathrm{ans} = \mathrm{ans} - y * 10^l$
  • クエリ$3$
    • $\mathrm{ans}$を出力する

$\mathrm{mod} = 998244353$で割った余りを求めることを忘れないようにすることに注意しましょう. あとは高速化のためにいくつかの点に注意するだけです.

  • 配列$S$は先頭または末尾にしかアクセスしないので, collectionsモジュールのdeque型を用いるとよい.
  • $10^l$を求める際に, これがあまりにも大きくなってしまうので, $\mathrm{mod}$で割った余りにしてとよい. これを効率よく求めるために, Pythonの組み込み関数のpow()を用いることができる.

なぜpow()の方が速いのか？

pow()の方が速いのは, 繰り返し2乗法と呼ばれる方法が実装されているからです. 例えば, $10^7$を

\begin{align} 10^7 &= 10 \times 10 \times 10 \times 10 \times 10 \times 10 \times 10 \end{align}

のようにしてしまうと, 指数を$N$として計算量が$\mathcal{O}(N)$になってしまいます. ここで, $7 = 2^2 + 2^1 + 2^0$であることに着目すると,

\begin{align} 10^{2^0} &= 10 , \\ 10^{2^1} &= 10 \times 10, \\ 10^{2^2} &= 10^{2^1} \times 10^{2^1}, \\ 10^{2^2 + 2^1 + 2^0} &= 10^{2^2} \times 10^{2^1} \times 10^{2^0} \end{align}

のよう計算することができます. このようにすることで, 指数を$N$として計算量を$\mathcal{O}(\log N)$に減らすことができます.

E以降

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

参考にしたサイト等