目次
はじめに
AtCoder Beginner Contest（略称：ABC）とは、AtCoderが週末に開催している、競技プログラミングコンテストのことです。
A-D問題について、自身の復習も兼ねて説明できればと思います。誤った記述やより良い解法などあれば、コメントをいただけると幸いです。
ABC296
A – Alternately
問題
N人が一列に並んでいます。男女が交互に並んでいるかどうかを判断する問題です。
解説
問題文に「男性同士が隣り合う箇所も女性同士が隣り合う箇所も存在しないとき、かつ、そのときに限り、男女が交互に並んでいる」と定義するとあります。その定義に従いましょう。
男性同士が隣り合うのは文字列に”MM”が存在するときであり、女性同士が隣り合うのは文字列に”FF”が存在するときです。これらの場合にはNoを出力し、それ以外の場合にYesを出力しましょう。
コード
N = int(input())
S = input()
if "MM" in S or "FF" in S:
print("No")
else:
print("Yes")B – Chessboard
問題
チェス盤のどこにコマが置かれているかを答える問題です。入力は2次元配列で与えられ、a1といった形式で出力します。
解説
全探索でコマが置かれているマスのインデックスを調べ、出力形式に変換しましょう。
インデックス0, 1, 2,……をa,b,c,……に変換するには、下の解答のようにアスキーコードを用いた変換を行うか、アルファベットの配列[“a”, “b”, ……, “h”]を用いればよいでしょう。
また、インデックス0, 1, 2,……を8,7,6,……に変換するには、8 – i の計算を行えばよいです。
コード
from sys import stdin
S = [stdin.readline()[:-1] for _ in range(8)]
for i in range(8):
if "*" in S[i]:
idx = S[i].index("*")
print(f"{chr(idx + 97)}{8 - i}")C – Gap Existence
問題
長さNの数列が与えられます。この数列内に、差がXとなる2数が存在するかどうかを判定する問題です。
解説
Nは2×10^5までのため、数列をリストで管理し、2重で全探索するとTLEになります。
今回は存在判定をしたいだけですので、数列をリストではなく、集合（set）で管理しましょう。集合では、要素の存在検索を平均的にO(1)で行うことができます。
コード
N, X = map(int, input().split())
A = set(map(int, input().split()))
for num in A:
if num + X in A:
print("Yes")
exit()
print("No")D – M<=ab
問題
正整数N,Mが与えられます。次の条件をともにみたす最小の正整数Xを求める問題です。ただし、そのようなものが存在しない場合は-1を出力します。
- Xは1以上N以下の整数a,bの積として表される。
- XはM以上である。
解説
例として、N=8、M=17のケースを考えましょう。
\(a \leq b\) としても一般性は損なわれません。
\(\sqrt{17}\) を切り上げた数は 5 です。\(a=5\) とすると \(b \geq 5\) であり、この時点で既に \(ab \geq 17\) を満たします。そのため 6 以上の \(a\) については考える必要がありません。
\(a \leq 5\) の範囲のそれぞれの \(a\) に対して、\(ab \geq 17\) を満たす最小の \(b\) を求めればよいです。これは、Mをaで割った商を切り上げることで求めることができます。例えば \(a=3\) のときは、17÷3=5.66……を切り上げた数 6 が求めたい \(b\) です。
それぞれの \(a\) に対して17以上の最小の \(ab\) が求められたことになりますので、その中の最小値が \(X\) となります。（今回の場合、\(a=3, b=6\) のときの \(X=18\) が答え）
一般的に、\(a\) は約 \(\sqrt{M}\) 回分のループを回す必要であり、そのそれぞれに対する \(b\) の計算量はO(1)です。全体の計算量はO(\(\sqrt{10^{12}}\))となり、これは時間内に終わらせることができます。
この問題の一番のポイントは、\(a \leq b\) として \(a\) の範囲を絞り込むことでした。
コード
import math
N, M = map(int, input().split())
INF = 10 ** 24
ans = INF
a_max = min(N, math.ceil(M ** (1 / 2)))
for a in range(1, a_max + 1):
b = min(N, math.ceil(M / a))
if a * b >= M and a * b < ans:
ans = a * b
if ans < INF:
print(ans)
else:
print(-1)最後に
以上、ABC296のA-D問題の説明でした。
ではまた！
