2023-05-21

AtCoder Beginner Contest 302 A問題 Attack

AtCoder ABC ABC302 A問題 100 pts

問題
提出解答
問題の概要
- 制約
解法

問題

atcoder.jp

提出解答

atcoder.jp

問題の概要

体力が $A$ のモンスターが居る.

このモンスターの体力を $0$ 以下にするためには, $1$ 回の攻撃で体力を $B$ 減らせる攻撃を最低何回する必要があるか?

制約

$1 \leq A \leq 10^{18}$
$1 \leq B \leq 10^{18}$

解法

求めるべき答えは $\left \lceil \dfrac{A}{B} \right \rceil$ である. しかし, これを求める場合, 次の違いにしなければならないことがたくさんある.

整数の型 (int 型, long 型)
整数を整数で割った商には実数の商と整数の商があること.
切り捨てと切り上げ

$\left \lceil \dfrac{A}{B} \right \rceil$ を切り捨てを用いて求める方法としては次のような方法がある.

(1)

$\left \lceil \dfrac{A}{B} \right \rceil=\left \lfloor \dfrac{A+B-1}{B} \right \rfloor$

(2)

$\left \lceil \dfrac{A}{B} \right \rceil=\begin{cases} \left \lfloor \dfrac{A}{B} \right \rfloor & (B \mid A) \\ \left \lfloor \dfrac{A}{B} \right \rfloor+1 & (B \not \mid A) \end{cases}$

ここで, $B \mid A, B \not \mid A$ はそれぞれ $B$ は $A$ の倍数である (倍数ではない) という意味である.

2023-05-14

AtCoder Beginner Contest 301 C問題 AtCoder Cards

AtCoder ABC ABC301 C問題 300 pts

問題
提出解答
問題の概要
- 制約
解法

問題

atcoder.jp

提出解答

atcoder.jp

問題の概要

英小文字と ${\tt @}$ からなる長さが等しい文字列 $S,T$ がある. この $S,T$ に対して, 以下の操作を順に行う.

$S,T$ にある ${\tt @}$ をそれぞれ ${\tt a}, {\tt t}, {\tt c}, {\tt o}, {\tt d}, {\tt e}, {\tt r}$ のどれかに置き換える.
$S,T$ を適用に並び替える.

$S=T$ にすることは可能か?

制約

$S,T$ は英小文字と ${\tt @}$ からなる長さ $1$ 以上 $2 \times 10^5$ 以下の文字列.

解法

文字列 $U$ に含まれる $c$ の数を $\chi_U(c)$ と書く. ここで, 並び替えが自由にできるので, 結局は $\chi_S(c), \chi_T(c)$ にのみ着目すれば良いことがわかる.

このとき, ${\tt a}, {\tt t}, {\tt c}, {\tt o}, {\tt d}, {\tt e}, {\tt r}$ ではない英小文字 ${\tt c}$ については $\chi_S(c)=\chi_T(c)$ でなくてはならない.

一方で, ${\tt a}, {\tt t}, {\tt c}, {\tt o}, {\tt d}, {\tt e}, {\tt r}$ のどれかである英小文字については, $\chi_S(c), \chi_T(c)$ を比較し, 小さい方の文字列における ${\tt @}$ をその差分だけ ${\tt c}$ に置き換えなければならず, 実際に, その差だけ置き換えれば良い.

この置き換えによって, ${\tt @}$ が不足してしまうと, 不可能であり, 不足しなければ可能である.

2023-05-14

AtCoder Beginner Contest 301 B問題 Fill the Gaps

AtCoder ABC ABC301 B問題 200 pts

問題
提出解答
問題の概要
- 制約
解法

問題

atcoder.jp

提出解答

atcoder.jp

問題の概要

長さ $N$ の整数列 $A=(A_1, \dots, A_N)$ がある. ここで, 隣り合う項は全て異なることが証明できる.

このとき, $A$ に対して, 以下の操作を行う.

$A$ の隣り合う項の差の絶対値が $1$ である場合は操作を終了する.
において, 隣り合う項の差の絶対値がでない最初の箇所をとする.
- $A_i \lt A_{i+1}$ ならば, $A_i, A_{i+1}$ の間に $A_i+1, A_i+2, \dots, A_{i+1}-1$ を挿入する.
- $A_i \gt A_{i+1}$ ならば, $A_i, A_{i+1}$ の間に $A_i-1, A_i-2, \dots, A_{i+1}+1$ を挿入する.

操作後の $A$ を求めよ.

制約

$1 \leq N \leq 100$ .
$1 \leq A_i \leq 100$ .
$A_i \neq A_{i+1}$ .

解法

次のようにして操作後の $A$ を求めることができる.

$B$ を空列とする.
$B$ に $A_1$ を挿入する.
に対して, 以下を行う.
- $A_i \lt A_{i+1}$ ならば, $B$ の末尾に $(A_i+1, A_i+2, \dots, A_{i+1}-1)$ を挿入する.
- $A_i \gt A_{i+1}$ ならば, $B$ の末尾に $(A_i-1, A_i-2, \dots, A_{i+1}+1)$ を挿入する.
$B$ が答え.

2023-05-14

AtCoder Beginner Contest 301 A問題 Overall Winner

AtCoder ABC ABC301 A問題 100 pts

問題
提出解答
問題の概要
- 制約
解法

問題

atcoder.jp

提出解答

atcoder.jp

問題の概要

高橋君と青木君が $N$ 回の試合を行った. この結果は長さ $N$ の文字列 $S$ で表され, $i$ 回目の試合の勝者は $S$ の $i$ 文字目が ${\tt T}$ ならば高橋君, ${\tt A}$ ならば青木君である.

この $N$ 回の試合から総合勝者を次のルールによって決定する.

勝利数の多い方が総合勝者である.
勝利数が同じであるならば, 先にその勝利数に達したほうが総合優勝である.

どっちが総合優勝か?

制約

$1 \leq N \leq 100$
$S$ は ${\tt T}, {\tt A}$ からなる長さ $N$ の文字列.

解法

$S$ に含まれる ${\tt T}, {\tt A}$ の数を $t,a$ としたとき, $t \lt a$ または $t \gt a$ であるならば直ちに総合優勝を決定できる.

一方で, $t=a$ の場合は for 文によって, どちらが先に $t$ 勝するかを求めることによって総合優勝を求めることができる.

なお, $t=a$ の場合は第 $N$ 試合で負けたほうが必ず総合優勝になるので, それを利用しても良い.

2023-04-29

AtCoder Beginner Contest 300 E問題 Dice Product 3

AtCoder ABC ABC300 E問題 500 pts

問題
提出解答
問題の概要
- 制約
解法

問題

atcoder.jp

提出解答

atcoder.jp

問題の概要

$6$ 面体の各目が同様に確からしく出るサイコロがある. 最初, $X=1$ である. 以下の行動を $X \lt N$ となる限り行う.

サイコロを降って出た目を $a$ とする. そして, $X$ を $a$ 倍する.

行動終了後, $X=N$ となる確率を求めよ.

制約

$2 \leq N \leq 10^{18}$

解法

正の有理数 $n$ に対して, $\operatorname{Prob}(n)$ で $X=n$ とできる確率とする.

まず, $\operatorname{Prob}(0)=1$ であり, $n$ が整数ではないならば, $\operatorname{Prob}(n)=0$ である.

$2$ 以上の整数 $n$ に対して, 各目で場合分けすることにより,

$\displaystyle \operatorname{Prob}(n)=\dfrac{1}{6} \sum_{a=1}^6 \operatorname{Prob} \left(\dfrac{N}{a} \right)$

となる.

ここで, 左辺と右辺に $f(n)$ が現れているが, 整理することによって,

$\displaystyle \operatorname{Prob}(n)=\dfrac{1}{5} \sum_{a=2}^6 \operatorname{Prob} \left(\dfrac{N}{a} \right)$

となる.

$1,2,3,4,5,6$ に現れる素因数は $2,3,5$ である. そして,

$\left \lceil \log_2 N \right \rceil \leq 60, \quad \left \lceil \log_3 N \right \rceil \leq 38, \quad \left \lceil \log_5 N \right \rceil \leq 26$

となるから, $\operatorname{Prob}(N)$ の計算に必要な引数のうち, 整数になるのは高々 $60 \times 38 \times 26=59280$ 個であり, 深さは高々 $60+38+26=104$ である.

よって, 整数でない $n$ における $\operatorname{Prob}(n)$ はすぐに $0$ を返すようにメモ化再起を計算することによって, $\operatorname{Prob}(N)$ を $O((\log N)^3)$ 時間で計算できる.

2023-04-29

AtCoder Beginner Contest 300 D問題 AABCC

AtCoder ABC ABC300 D問題 400 pts

問題
提出解答
問題の概要
- 制約
解法

問題

atcoder.jp

提出解答

atcoder.jp

問題の概要

次を見たす整数 $n$ の数を求めよ.

$1 \leq n \leq N$
$a \lt b \lt c$ なる素数 $a,b,c$ に対して, $n=a^2 b c^2$ となる.

制約

$1 \leq N \leq 10^{12}$

解法

$1$ 以上 $N$ 以下の整数 $n$ が $a \lt b \lt c$ となる素数 $a,b,c$ に対して, $n=a^2 b c^2$ と表されるとき,

$a^5 \leq a^2 b c^2=n \leq N, \quad b^3 \leq a^2 b c^2=n \leq N, c^2 \leq a^2 b c^2=n \leq N$

であるから, $a \leq \sqrt[5]{N}, b \leq \sqrt[3]{N}, c \leq \sqrt{N}$ となる.

よって, $a \leq \sqrt[5]{N}, b \leq \sqrt[3]{N}, a \lt b$ となる各素数の組 $(a,b)$ に対して, $\displaystyle b \lt c \leq \sqrt{\dfrac{N}{a^2 b}}=:K$ となる素数 $c$ の数を高速に計算できれば良い.

これは $P(n)$ を $n$ 以下の素数とすると,

$b \leq K$ ならば, $S(K)-S(b)$ 個
$b \lt K$ ならば, $0$ 個

である.

ここで, $S(n)$ は $n \leq \sqrt{N}$ の範囲まで求めれば良く, これはエラトステネスの篩を利用することで $O(\sqrt{N})$ 時間で求められる.

また, 調べるべき $(a,b)$ の数は高々 $\sqrt[5]{N} \times \sqrt[3]{N}=N^{8/15}$ 組である.

以上から, $O(N^{8/15})$ 時間で求めることができた

2023-04-29

AtCoder Beginner Contest 300 C問題 Cross

AtCoder ABC ABC300 C問題 300 pts

問題
提出解答
問題の概要
- 制約
解法

問題

atcoder.jp

提出解答

atcoder.jp

問題の概要

$H$ 行 $W$ 列のマス目がある. 上から $i$ 行目, 下から $j$ 列目のマス目を $(i,j)$ と書く.

各マスは ${\tt \#}, {\tt .}$ のどれかが書かれており, $(i,j)$ には $C_{i,j}$ が書かれている. また, $1 \leq i \leq H, 1 \leq j \leq W$ の少なくとも一方を満たさない場合は $C_{i,j}={\tt .}$ とする.

ここで, 正の整数 $a,b,n$ が以下の条件を全て満たすとき, $(a,b)$ を中心とするサイズ $n$ のバツ印という.

$C_{a,b}={\tt \#}$
$d=1,2, \dots, n$ に対して, $C_{a-d,b-d}, C_{a-d,b+d}, C_{a+d,b-d}, C_{a+d,b+d}$ は全て ${\tt \#}$ である.
$C_{a-(n+1),b-(n+1)}, C_{a-(n+1),b+(n+1)}, C_{a+(n+1),b-(n+1)}, C_{a+(n+1),b+(n+1)}$ のうち, 少なくとも $1$ つは ${\tt .}$ である.