AtCoder Beginner Contest 163の復習, E問まで(Python)

競プロ初心者の復習用記事です。

ここで書く解は解説や他の人の提出を見ながら書いたものです。自分が実際に提出したものとは限りません。

A - Circle Pond

半径Rの円周を出力する問題です。

円周cは半径rに対して

$$ c = 2\pi r $$

で求まります。

import math
R = int(input())
print(2 * math.pi * R)

誤差の許容範囲も大きいので、こんな行儀よく円周率を読みこむ必要はないようです。

B - Homework

$\boldsymbol{A}$日必要な夏休みの宿題をやると夏休みは何日残るか答える問題です。

(夏休みの日数)-(配列の合計)が負になるなら-1, それ以外ならそのまま出力。max()を使えばif文を使う必要がないですね。

N, M = map(int, input().split())
A = list(map(int, input().split()))

print(max(N - sum(A), -1))

C - management

「社員番号$A_i$を上司に持つ、社員番号$i$の職員」という情報が与えられます。それぞれの職員に対して部下は何人ずついるか答える問題です。

問題文を理解するのに一番手間取りました。要するに番号の分布を聞かれているんですね。

collections.Counterを用いて番号の分布を数えました。

import collections
N = int(input())
A = list(map(int, input().split()))
count = collections.Counter(A)
for n in range(N):
  print(count[n+1])

D - Sum of Large Numbers

$N+1$個の数値の中から$K$個以上を取る全ての組み合わせの中で、和としてありうるものの個数を答える問題です。ただしそれぞれの数値は$10^{100}+i$という形をしているため、$M$個の数値を取った和と$M+1$個取った和は絶対に一致しません。

さっぱりわかりません。和の個数をなんかの数式にできないでしょうか。「1~9までの数字から$M$個取った時の和の組み合わせ」というものがどんな分布になるのか試しに計算してみました。$m$行目に出力したものが$m$個取った場合の和の分布を表しています。

実際にはここで諦めました。ただ、今これ見ると大事なヒント出てます。

この出力を見ると「組み合わせ和の最小値と最大値の間までに数字抜けは存在しない」という推測が経ちます。それなら「和の最小値」と「和の最大値」をそれぞれ計算すれば$M$個取った時の組み合わせ和の個数が求まります。

$M$個取った時の最小値は「$M$個目までの数値の合計」最大値は「$N-M+1$個目からの数値の合計」で求まります。あとはその差+1がありうる組み合わせ和の数です。

N, K = map(int, input().split())
mod = 10**9 + 7
count = 0
for n in range(K, N+2):
  maxSum = (n*(N + N-n+1))//2
  minSum = (n*(n-1))//2
  count += maxSum - minSum + 1
  count %= mod

print(count)

これで通りました。これは解説見ないでもわかったので、コンテスト中に解きたかったなあ。

E - Active Infants

位置$i$に存在する幼児ごとの係数$A_i$が与えられ、幼児が動き回る距離×係数の最大値を求める問題です。

全然わかりません。苦し紛れに総当たりの解答を提出して(TLE)諦めました。

TLEのやつ.py

import itertools 

N = int(input())
A = list(map(int, input().split()))
ureshisa = [
            [A[i] * abs(i-j) for j in range(N)] for i in range(N)
]
maxV = 0
for P in itertools.permutations(list(range(N))):
  maxV = max(maxV, sum([ureshisa[P[i]][i] for i in range(N)]))
print(maxV)

解説を見...てもよくわからなかったので、他の解答を参考にします。以下のコードはこの解答からそのまま引用したものです。

引用.py

# E - Active Infants

n = int(input())
a = list(map(int, input().split()))
assert len(a) == n

# 添字のリスト
p = list(range(n))
p.sort(key=lambda i: a[i])

# dp[j] = 位置jから幅iの区間に小さい方からi個を配置したときの最大うれしさ
dp = [0] * (n + 1)

for i in range(n):
    for j in range(n - i):
        dp[j] = max(dp[j]     + a[p[i]] * abs(p[i] - (j + i)),
                    dp[j + 1] + a[p[i]] * abs(p[i] - j))

print(dp[0])

わからないので処理を追ってみる

配列[1, 3, 4, 2]が与えられたときの処理について、順番に追ってみましょう。

まず$A_i$が最小値となる$i = 0$の幼児(以下$a_0$と呼ぶ)の配置を考えます。

$a_0$を0, 1, 2, 3それぞれの位置に配置したときのうれしさはそれぞれ計算して0, 1, 2, 3となります。

この値は配列dpとして保存します。下から一個の幼児$a_0$を配置したときの配列dpは以下のようになります

$$\mathrm{dp}_1= [0, 1, 2, 3]$$

次に、$A_i$が二番目に小さい値となる$i=3$の幼児$a_3$も配置します。ただし、「$a_0$の一つ後ろに配置する」「$a_0$を一つ後ろに押しのけて配置する」という状態のみを考えます。

まず、$a_0$が$i=0$に置かれている時は「$a_0$をそのままにして$a_3$を$i=1$に配置する」「$a_0$を$i=1$に押しのけて$a_3$を$i=0$に配置する」の二つがあります。うれしさをそれぞれ計算すると4, 7となりました。大きいほうの値だけ残し、dp[0] = 7とします。

これを同様に計算していくと、$a_0$の配置が$i=1, 2$の時はそれぞれ6, 5が最大となります。(dp[3]の値はここで吸収されました)

というわけで、係数が下から二つの幼児($a_
{03}$と呼ぶ)を並べて配置したとき

$$\mathrm{dp}_2 = [7, 6, 5]$$

がそれぞれの位置に対応した最大値となります。

次に係数が下から3番目の$i=1$の幼児$a_1$の配置を同様に考えます。

「並べた二人の幼児$a_{03}$の後ろに配置する」「並べた二人の幼児$a_{03}$を一つ後ろに押しのけて配置する」をそれぞれ計算します。

これまでと同様に計算し、数が下から三つの幼児($a_{031}$と呼ぶ)を並べて配置したとき以下のように求まりました。

$$\mathrm{dp}_3 = [10, 12]$$

最後に係数$A_i$が最大の幼児$a_2$に対してもう一回同じ処理を行います。

$a_{031}$を$i=0$に配置して$a_2$を$i=3$に配置する場合が$14$, $a_{031}$を$i=1$に配置して$a_2$を$i=0$に配置する場合が$20$。大きいほうを取ります。

$$\mathrm{dp}_4 = [20]$$

これで答えが求まりました。

ちょっと自分にはイマイチ理解が追い付いていません...。この考え方で行くには、「係数が下からM番目の幼児は必ず『1からM-1番目までの幼児の列』に隣接する」という考察にたどり着く必要があるんですかね？直観的にそんな気がしないでもないですが、証明できるかというとよくわかりません。

解説の方の考え方だと係数が高い幼児から順番に左右どちらかの壁を埋めていく。要するに逆順で同じことをやってるようですね。

この記事はここまでとします。

参考

https://atcoder.jp/contests/abc163/submissions/12150591
E問はこれを引用しました。