AtCoder Regular Contest 197 (Div. 2)の解説記事です。
ARC197 A – Union of Grid Paths
問題
問題文の要約は以下の通りです。
問題の要約
縦 \(H\) 行、横 \(W\) 列のマス目があります。各マスは最初は白く塗られています。長さ \(H+W−2\) の文字列 \(S\) が与えられます。\(S\) は次の文字のみから成ります。
D：下に進むR：右に進む?：DまたはRを選べる
あなたは次の操作を何度でも繰り返すことができます。
- \(S\) の
?をDまたはRに置き換えて、Dがちょうど \(H−1\) 個、Rがちょうど \(W−1\) 個の文字列 \(X\) を作る。ただし \(S_i\) がDのときは \(X_i\) もD、Rのときは \(X_i\) もRでなければならない。 - \((1,1)\) から \(X\) に従って右または下に移動し、通ったマスをすべて黒く塗る。
この操作を何度でも繰り返して、最終的に黒く塗られるマスの個数の最大値を求めよ。\(T\) 個のテストケースが与えられるのでそれぞれ解け。
解説
\(S_i\) のそれぞれの時点で、そこまでに選べる D の個数の範囲を計算します。各位置で可能な D の数の 最小値と最大値の差 + 1 が「その位置で通り得る異なるマス数」になるのでそれらを累積して、最終的に黒く塗れるマスの総数を導く。
解説
入力を受け取ります。
# 入力
T=int(input())テストケース分繰り返し、入力を受け取ります。
# テストケース分繰り返す
for _ in range(T):
# 入力
H,W= map(int,input().split())
S=input()黒色で塗ることができるマスの個数ansの初期値を 最初のマスは常に黒のため、\(1\) とします。、
# 黒色で塗ることができるマスの個数（最初のマスは常に黒）
ans=1\(S\) のそれぞれの文字の総数を計算します。
# S のそれぞれの文字の総数
sum_d=S.count('D')
sum_r=S.count('R')
sum_q=S.count('?')累積和の初期値を \(0\) で用意します。
# 累積和
cumsum_d=0
cumsum_r=0
cumsum_q=0文字の \(i\) 番目を順番に確認します。まず、累積和に加算を行います。
# 文字のi番目を順にみる
for i in range(H+W-2):
# 累積和に加える
if S[i]=='D':
cumsum_d+=1
if S[i]=='R':
cumsum_r+= 1
if S[i]=='?':
cumsum_q+=1\(S_i\) のそれぞれの時点で、そこまでに選べる D の個数の範囲を計算します。各位置で可能な D の数の 最小値と最大値の差 + 1 が「その位置で通り得る異なるマス数」になるのでそれらを累積して、最終的に黒く塗れるマスの総数を導く。
Dの数の最大値をmax_dとします。?をできるだけDに使いますが、全体でDは最大H-1個までなので、Dとして使えるのは(H-1)-sum_d個になります。よって、cumsum_d（これまでの Dの累積和）に加えられる Dの数はmin(cumsum_q,(H-1)-sum_d)になります。
# D の最大値: ? を 可能な限り D にする
max_d=cumsum_d+min(cumsum_q,(H-1)-sum_d)D の数の最小値をmin_dとします。? をできるだけ R に使いますが、全体で R は最大 W-1 個までなので、Rとして使えるのは (R-1) - sum_r 個になります。それ以外の ? は D に使うしかありません。よって、cumsum_d（これまでの Dの累積和）に加えられる D の数は (cumsum_q-min(cumsum_q,(W-1)-sum_r))になります。
# D の最小値: ? を 可能な限り R にして残りが D
min_d=cumsum_d+(cumsum_q-min(cumsum_q,(W-1)-sum_r))最小値と最大値の差 + 1 を「その位置で通り得る異なるマス数」として足し合わせます。
# 到達可能な D の数の範囲分だけ異なるマスに行ける
ans+=max_d-min_d+1最後に答えを出力します。
# 黒マスの総数を出力
print(ans)解答
# 入力
T=int(input())
# テストケース分繰り返す
for _ in range(T):
# 入力
H,W= map(int,input().split())
S=input()
# 黒色で塗ることができるマスの個数（最初のマスは常に黒）
ans=1
# S のそれぞれの文字の総数
sum_d=S.count('D')
sum_r=S.count('R')
sum_q=S.count('?')
# 累積和
cumsum_d=0
cumsum_r=0
cumsum_q=0
# 文字のi番目を順にみる
for i in range(H+W-2):
# 累積和に加える
if S[i]=='D':
cumsum_d+=1
if S[i]=='R':
cumsum_r+= 1
if S[i]=='?':
cumsum_q+=1
# D の最大値: ? を 可能な限り D にする
max_d=cumsum_d+min(cumsum_q,(H-1)-sum_d)
# D の最小値: ? を 可能な限り R にして残りが D
min_d=cumsum_d+(cumsum_q-min(cumsum_q,(W-1)-sum_r))
# 到達可能な D の数の範囲分だけ異なるマスに行ける
ans+=max_d-min_d+1
# 黒マスの総数を出力
print(ans)ARC197 B – Greater Than Average
問題
問題文の要約は以下の通りです。
問題の要約
整数列 \(x = (x_1, x_2, \ldots, x_n)\) に対して、スコアを平均値より大きい要素の個数として定義する。
$$ \text{score}(x) = \#\left\{ i \mid x_i > \frac{1}{n} \sum_{j=1}^{n} x_j \right\}$$
長さ \(N\) の整数列 \(A = (A_1, A_2, \ldots, A_N)\) が与えられる。\(A\) の空でない部分列の中で、スコアの最大値を求めよという \(T\) 個のテストケースについて解け。
解説
スコアを平均値より大きい要素の個数であるため、スコアを大きくするには平均点をできるだけ低くする必要がある。そのためには平均より低い要素はすべて入れる方が良い。また平均点より高い要素は値が小さい順に入れていけばよい。すなわち \(A\) の空でない部分列の中でスコアを最大にするには、要素を値の小さい順に並べた上で、先頭から順に部分列を作り、その中でスコア（平均を超える要素数）を計算していけば、最大スコアを得られる。
解説
入力を受け取ります。
# 入力
T=int(input())テストケース分繰り返し、入力を受け取ります。
# テストケース分繰り返す
for _ in range(T):
# 入力
N=int(input())
A=list(map(int,input().split()))\(A\) を昇順でソートします。
# 昇順でソート
A.sort()答えのスコアをans、平均値を求めるための累積和をcumsum、平均以下となる要素のインデックスをkとします。
# スコア
ans=0
# 累積和
cumsum=0
# 平均以下となる要素のインデックス
k=0ソート済の \(A\) の先頭から順に部分列を作り、その中でスコア（平均を超える要素数）を計算していけば、最大スコアを得られます。平均を求めるために累積和と平均以下の要素のインデックスを尺取り法で求めます。
for i in range(N):
# 累積和に加える・
cumsum+=A[i]
# 尺取り法で平均以下の要素のインデックスを求める
while k<=i and A[k]*(i+1)<=cumsum:
k+=1
# スコアは平均を超える要素の数
ans=max(ans,i+1-k)最後に答えを出力します。
# 答えを出力
print(ans)解答
# 入力
T=int(input())
# テストケース分繰り返す
for _ in range(T):
# 入力
N=int(input())
A=list(map(int,input().split()))
# 昇順でソート
A.sort()
# スコア
ans=0
# 累積和
cumsum=0
# 平均以下となる要素のインデックス
k=0
for i in range(N):
# 累積和に加える・
cumsum+=A[i]
# 尺取り法で平均以下の要素のインデックスを求める
while k<=i and A[k]*(i+1)<=cumsum:
k+=1
# スコアは平均を超える要素の数
ans=max(ans,i+1-k)
# 答えを出力
print(ans)