【AtCoder】サントリープログラミングコンテスト2024（AtCoder Beginner Contest 357） - 参加記

atcoder.jp

コンテスト時間: 2024-06-08(土) 21:00 ~ 2024-06-08(土) 22:40 (100分)

A - Sanitize Hands

Difficulty: ???
解答時間: 2:32

$M$ 本の手をちょうど消毒できる消毒液がある。 $N$ 人が順番に手の消毒をするが、 $i$ 人目は $H_i$ 本の手を持っており自身のすべての手を1回ずつ消毒する。何人目の宇宙人までがすべての手を消毒できるか求めよ。

$M$ から $H_i$ を順次引いていき、 $M \geq 0$ である回数を数えればよい。

B - Uppercase and Lowercase

Difficulty: ???
解答時間: 2:14

長さが奇数で英小文字と英大文字からなる文字列 $S$ が与えられる。 $S$ に含まれる大文字の個数が小文字の個数よりも多ければ、 $S$ に含まれる全ての小文字を大文字に変換せよ。そうでない場合、 $S$ に含まれる全ての大文字を小文字に変換せよ。

C++ では大文字か小文字かの判定にisupper()、islower()が、大文字や小文字への変換にtoupper()、tolower()が用意されているので、これを使って問題文の通りに実装していけばよい。

C - Sierpinski carpet

Difficulty: ???
解答時間: 10:59

非負整数 $K$ に対して、以下のように「レベル $K$ のカーペット」を定義する。
定義 :
1. $K = 0$ のとき、カーペットは黒いマス1個からなる $1 \times 1$ のグリッドである。
2. $K > 0$ のとき、カーペットは $3^K \times 3^K$ のグリッドである。このグリッドを $3^{K-1} \times 3^{K-1}$ の9個のブロックに分割したとき、
- 中央のブロックは全て白いマスである。
- 他の8個のブロックは、レベル $(K-1)$ のブロックである。
黒いカーペットを#、白いカーペットを.として、非負整数 $N \: (0 \leq N \leq 6)$ に対してレベル $N$ のカーペットを出力せよ。

サンプルケースの出力例を見ると想像がつくように、これは「シェルピンスキーのギャスケット」というフラクタル図形に関する問題である。したがって、再帰関数を用いて実装するとうまくいきそうである。
今考えているカーペットのレベルとグリッドの1辺のマスの数を引数に持つ関数を用意し、レベルが $0$ のときは全てのマスを#にする。それ以外の時はサイズを3で割って2重ループ。中央のブロックは全て白いマスであることに注意する。

D - 88888888

Difficulty: ???

正整数 $N$ に対し、 $N$ を $N$ 個つなげた整数を $V_N$ とする。 $V_N$ を $998244353$ で割った余りを求めよ。

$N$ は最大 $10^{18}$ なので、普通に計算するのは不可能。そこで、 $V_N$ を式を用いて表してみると、 $l$ を $N$ の桁数として、

$\begin{align*} V_N & = N \displaystyle \sum_{i=0}^{N-1} 10^{il} \\ & = N \cdot \dfrac{10^{Nl} -1}{10^l - 1} \end{align*}$
と書ける。これを $\mod 998244353$ すればよいが、除算の $\textrm{mod}$ は逆元を取らなければならないことや、 $\textrm{mod}$ の累乗には繰り返し二乗法を用いる必要があることに注意。