AtCoder ABC174
2020-08-02(日)に行われたAtCoderBeginnerContest174の問題をA問題から順に考察も踏まえてまとめたものとなります．
後半ではDEの問題を扱います．前半はこちら
問題は引用して記載していますが，詳しくはコンテストページの方で確認してください．
コンテストページはこちら
公式解説PDF
D問題 Alter Altar
問題文
祭壇に、左から右へと一列に並ぶ$N$個の石が祀られています。左から$i$個目$(1 \leqq i \leqq N)$の石の色は文字$c_i$として与えられ、$c_i$が'R'のとき赤、'W'のとき白です。
あなたは、以下の二種の操作を任意の順に何度でも行うことができます。
・石を$2$個選び (隣り合っていなくてもよい)、それらを入れ替える。
・石を$1$個選び、その石の色を変える (赤なら白に、白なら赤に)。
占い師によると、赤い石の左隣に置かれた白い石は災いを招きます。そのような白い石がない状態に至るには、最小で何回の操作が必要でしょうか。
問題を読んだときに「・石を$2$個選び (隣り合っていなくてもよい)、それらを入れ替える。」だけで解けそうだと思いました．
「・石を$1$個選び、その石の色を変える (赤なら白に、白なら赤に)。」を使わないことで，最終的な答えのない状態は一通りに定まります．
例えば，$N=9$で
'WRWWWRRWR'
の入力は
'RRRRWWWWW'
となるように操作を最小に行うことを考えれば答えを出すことができる．
これは，入力に含まれる赤い石の個数$N_r$とし，入力の$1$から$N_r$番目までの白い石の個数が必要な操作数であることがわかる．（例の場合，'WRWWWRRWR'の$1$から$4$番目の'WRWW'における白い石の数なので$3$が答えとなる．）
n = int(input())
mozi = input()
a_list = []
for i in range(n):
if mozi[i] == 'W':
a_list.append(0)
else:
a_list.append(1)
r_count = sum(a_list)
print(r_count - sum(a_list[0:r_count]))
E問題 Logs
問題文
丸太が$N$本あり、それぞれ長さは$A_1,A_2,⋯,A_N$です。
これらの丸太を合計$K$回まで切ることができます。 長さ$L$の丸太を片端から$t(0 < t < L)$の位置で切ると、長さ$t,L−t$の丸太に分かれます。
丸太を合計$K$回まで切った後最も長い丸太の長さが最小でいくつになるか求め、小数点以下を切り上げた値を出力してください。
二分探索に気がつけず，$x = 1$から貪欲に探索していたためコンテスト中に解けませんでした．
n, k = map(int, input().split())
a_list = list(map(int, input().split()))
a_list.sort(reverse=True)
if k == 0:
print(a_list[0])
else:
start = 1
end = a_list[0]
x = (start + end) // 2
while True:
k_count = 0
flag = 1
for a in a_list:
temp_k = 0
if a % x == 0:
temp_k = a // x - 1
else:
temp_k = a // x
if temp_k == 0:
flag = 1
break
k_count += temp_k
if k_count > k:
flag = 0
break
if flag == 1:
end = x
if flag == 0:
start = x
next_x = (start + end) // 2
if next_x == x:
if flag == 1:
print(x)
if flag == 0:
print(x + 1)
break
x = next_x
後半も最後まで読んでいただきありがとうございました．