ABC227のA-D問題の解説。
目次
A - Last Card
B - KEYENCE building
C - ABC conjecture
D - Project Planning
A - Last Card
解説
A番目の人からN人にK枚のカードを配るとき、最後のカードは誰に配れるかという問題。
回答としては、A番目とK枚のカードの和から1を引いた値をNで割ったあまりを出力すれば良い。このとき、あまりが0になったとき、これはカードを配りきれたということなので、Nを出力させるようにする。
コード
def main():
n, k, a = map(int, input().split())
ans = (a + k - 1) % n
if ans == 0:
ans = n
print(ans)
if __name__ == '__main__':
main()
B - KEYENCE building
解説
この問題を簡単に言うと、任意の非負整数(1, 2, ...)$a, b$を用いて、式$4ab + 3a + 3b$で求められる解がある。入力された$S_i$について、この解に当てはまらないものはいくつあるかを求める問題。
解き方については以下の通りである。
コード
def main():
n = int(input())
slist = list(map(int, input().split()))
check = set() # 4*i*j + 3*i + 3*jの解の保存場所
for i in range(1, 1001):
for j in range(1, 1001):
test = 4*i*j + 3*i + 3*j
if test > 1000: # 値が1000を超えたらループを抜ける
break
check.add(test) # 値をチェックリストに追加
cnt = 0
for s in slist:
if s not in check: # S_iの中からチェックリストに含まれないものを数える
cnt += 1
print(cnt)
if __name__ == '__main__':
main()
C - ABC conjecture
解説
正の整数Nに対し、$A \leq B \leq C$かつ$ABC \leq N$であるような整数の組$(A, B, C)$を求める問題。
全探索してすべてのデータに触れようと思うと、実行時間にあてはまらない。したがって、計算量を工夫する必要がある。
1つ目のループでは、Nまで探索しているが、Aの値の3乗、つまり、A, B, Cがすべて同じ値のとき、これがNを超えると条件を満たさないので、これ以上組み合わせを調べる必要がないので、breakでループを終了させる。
また、2つ目のループでもNまで探索しているが、B, Cが同じ値のとき、計算結果がNを超えると、これ以上の数の組み合わせを求める必要はないので、breakでループ処理を終了する。
答えの出し方だが、n//a//bでCの値を求めて、$B \leq C$なので、CからBの値を引いてあげることで、条件に当てはまる整数の組の個数を求めることができる。
コード
def main():
n = int(input())
ans = 0
for a in range(1, n+1):
if a*a*a > n:
break
for b in range(a, n+1):
if a*b*b > n:
break
ans += n // a // b - b + 1
print(ans)
if __name__ == '__main__':
main()
D - Project Planning
解説
N個の部署があり、それぞれの部署には$A_1, A_2, ..., A_i$人いる。
K個の部署から1人ずつ選び、K人構成のプロジェクトを作りたい。
このときできるプロジェクトの最大数を求める問題。
それぞれの例題を図式化したものは、次のようになる。
最大数を求めるこの問題は、単調性を持つので、二分探索を使用することができる。
例2のように、二分探索における中心の値を2と推測すると、$A_3, A_4$はそれぞれ2人いればプロジェクトを作成できる。このように$A_i$か$X$のどちらか最小の方をとり、これらの和を求める。この数値が$K \times X$の値になっているか、つまり、人数が条件を超えていないかを確認する。ここでは、$6 \geq 4 = k \times X$となり、条件を満たすので、ok側の変数に値を代入するようにする。
これを繰り返していくと、いずれXの値の境界線となる値、okとngがそれぞれ求まる。今回求めたいのは最大値なので、okを出力してあげれば答えとなる。
また、今回書いた二分探索のコードは、「めぐる式二分探索」というものである。こちらの詳細については、以前、競技プログラミングでの二分探索について記事を作成しているので、よかったら参考にしていただきたい。
コード1（めぐる式二分探索）
def main():
def is_ok(pjt):
total = 0
for x in xlist:
total += min(x, pjt)
return total >= k * pjt
def meguru_bisect(ng, ok):
while (abs(ok - ng) > 1):
mid = (ok + ng) // 2
if is_ok(mid):
ok = mid
else:
ng = mid
return ok
n, k = map(int, input().split())
xlist = list(map(int, input().split()))
ok = 0
ng = 10**18 // k
print(meguru_bisect(ng, ok))
if __name__ == '__main__':
main()
コード2（関数なし）
def main():
n, k = map(int, input().split())
xlist = list(map(int, input().split()))
ok = 0
ng = (10**18) // k
while ng - ok > 1:
md = (ok + ng) // 2
total = 0
for x in xlist:
total += min(x, md)
if total >= k * md:
ok = md
else:
ng = md
print(ok)
if __name__ == '__main__':
main()
編集後記
二分探索は学習済みだったので、いくら青問題とはいえ、ときたかった...