AtCoder Beginners Contest 345 (ABC345) をPythonで解きました。
見やすいコードを書く練習も兼ねてます。
A - Leftrightarrow
問題
< , = , > の$3$ 種類からなる文字列 $S$ が与えられます。
$S$ が以下の条件を満たしているかどうかを判定してください。
-
<を $1$ 個、=を $k$ 個、>を $1$ 個、この順に組み合わせた文字列である( $k$ は$1$ 以上の整数)
考察
文字列 $S$ の長さを $N$ とすると、「< を $1$ 個、 = を $N - 2$ 個、 > を $1$ 個、この順に組み合わせた文字列である」かどうかを判定すればよいです。
下のコードでは、新たに文字列 $T$ を< を $1$ 個、 = を $N - 2$ 個、 > を $1$ 個、この順に組み合わせた文字列として、$S$ と $T$ が一致しているかどうかを見ています。
コード
S = input()
N = len(S)
T = '<' + '=' * (N - 2) + '>'
if S == T:
print("Yes")
else:
print("No")
B - Integer Division Returns
問題
整数 $X$ が与えられます。 $\left\lceil \dfrac{X}{10} \right\rceil$ の値を求めてください。
($\left\lceil a \right\rceil$ は $a$ 以上の最小の整数を表します。)
考察
あまり見慣れない記号ですが、具体的な計算はこんな感じです。
- $\left\lceil 1.8 \right\rceil = 2$
- $\left\lceil 2 \right\rceil = 2$
- $\left\lceil 2.4 \right\rceil = 3$
小数点以下がなければ、$\left\lceil 2 \right\rceil = 2$ のようにそのまま記号を外していいです。
小数点以下があれば、$\left\lceil 2.4 \right\rceil = 3$ のように小数点以下は取り除き、整数部分に $1$ を加えた値を返します。
これをそのままコードに書き起こすと、下のようになります。
コード
X = int(input())
if X % 10 == 0:
print(X // 10)
else:
print(X // 10 + 1)
別解
実は、小数点以下切り上げの割り算$\left\lceil \dfrac{a}{b} \right\rceil$ は、小数点以下切り捨ての割り算である // を用いて、 (a + b - 1) // b と書けます。
そこそこの頻度で出てくる計算なので、知らなかった方はこの機に覚えてしまいましょう。
def div_ceil(a, b):
return (a + b - 1) // b
X = int(input())
ans = div_ceil(X, 10)
print(ans)
C - One Time Swap
問題
文字列 $S$ が与えられます。次の操作を $1$ 回だけ行って得られる文字列の種類の数を答えてください。
- $1 \leq i \lt j \leq |S|$ となる整数組 $(i, j)$ を選び、$S$ の $i$ 文字目と $j$ 文字目を入れかえる
考察
制約より、文字列の長さは最大で $10^6$ です。
なので、$(i,j)$ の組は全部でだいたい $10^{12}$ 通りくらいあり、 $(i,j)$ の組を全探索しているとTLEしてしまいます。
以下、「$i$ 文字目と $j$ 文字目をいれかえる」の操作のことを操作 $(i,j)$ とよび、それにより得られる文字列を $S_{i,j}$ とよびます。
いくつか実験してみると、$S$ の $i_1$ 文字目と $j_1$ 文字目が異なるとき、$S_{i_1, j_1}$ は操作 $(i_1, j_1)$ 以外では得られないことが分かります。
したがって、次の $2$ つを求めることになります。
- $i$ 文字目と $j$ 文字目が異なるような $(i, j)$ の個数
- $i$ 文字目と $j$ 文字目が等しい $(i, j)$ があるかどうか
基本的には1番目の $(i,j)$ の個数が答えになりますが、2番目の条件を満たす $(i,j)$ があれば答えに $1$ を足せばよいです。
これはどちらも、$j=0,1,2, \cdots ,|S|-1$ と探索していく中で、$\text{count_dic} [アルファベット]= \text{(そのアルファベットが登場した回数)}$ となる辞書を更新しながら進めると求められます。
詳しくは下のコードも参考にしてください。
コード
from collections import defaultdict
S = input()
count_dic = defaultdict(int)
diff, same = 0, 0
for j, ch in enumerate(S):
diff += j - count_dic[ch]
same += count_dic[ch]
count_dic[ch] += 1
if same > 0:
ans = diff + 1
print(ans)
else:
print(diff)
D - Tiling
問題
$H$ 行 $W$ 列のマス目と $N$ 枚のタイルがあります。
$i$ 枚目のタイルは縦 $A_i$ マス分、横 $B_i$ マス分の長方形の形をしています。
タイルのうち何枚かをつかってマス目をすべて埋めることはできますか？
タイルは回転させてもよく、タイル同士が重なるような配置はできないとします。
考察
タイルの枚数は $N\leq 7$ で、マス目についても $1 \leq H, W \leq 10$ なので、実装するのみです。
どのように実装してもだいたいぐちゃぐちゃになると思います、こればかりは気合いでがんばりましょう。
高速化の工夫として、下のコードでは座標 $(i,j)$ を1変数 $p=i \times W + j$ としています。
また2次元のマス目については、「$(i,j)$のマスにタイルがあるとき、2進数表記で下から $i\times W + j$ 桁目が1になっている」というマイルールで、2次元のマス目を1つの整数で表しています。
(高速化の工夫のところが分からなくても大丈夫です、時間をかけてでもいいのでいったん気合いでAC取ってみましょう。)
コード
from collections import deque
N, H, W = map(int, input().split())
tile = [tuple(map(int, input().split())) for _ in range(N)]
B = (1 << (H * W)) - 1
que = deque()
que.append((0, 0))
while que:
grid, state = que.popleft()
if grid == B:
print("Yes")
exit()
p = 0
while (grid >> p) & 1:
p += 1
si, sj = divmod(p, W)
for ti in range(N):
if (state >> ti) & 1:
continue
nex_state = state | (1 << ti)
x, y = tile[ti]
for a, b in [(x, y), (y, x)]:
ei, ej = si + a, sj + b
if ei > H or ej > W:
continue
nex_grid = grid
is_ok = True
for i in range(si, ei):
for j in range(sj, ej):
if (nex_grid >> (i * W + j)) & 1:
is_ok = False
nex_grid |= 1 << (i * W + j)
if is_ok:
que.append((nex_grid, nex_state))
print("No")