otsunekoの日常

Educational Codeforces Round 3 精進日記

公開日：2021年5月1日

最終更新日：2021年5月1日

Educational Codeforces Round 3

なぜか問題一覧のページでA、B問題がロシア語になってますね。変換ミス？

公式解説

A. USB Flash Drives

ポイント

USBメモリを容量大きい順にソートして、貪欲にファイルを保存していく

usb_flash_drives.py

N = int(input())
M = int(input())
A = [int(input()) for _ in range(N)]
A.sort(reverse=True)

ans = 0
for a in A:
    if M <= 0:
        break
    M -= a
    ans += 1
print(ans)

B. The Best Gift

累積和のアイデアに至るまで、itertools.combinationsやCollectionsでいろいろ迷走して時間を使ってしまった。あと問題文の意味を正しく解釈するまでに毎回10分～20分ぐらい使ってる気がする…多分サンプルケースの説明を紙に書いてイメージするのが一番確実なんだろうな…

ポイント

愚直に全探索で解こうとすると1冊目の本候補と2冊目の本候補の全探索で $O(N^2)$ となりTLEなので、ジャンルごとの冊数カウントと累積和を使って計算量を減らす
予めジャンル毎に本の冊数をカウント(例：ジャンル1：2、ジャンル2：1、ジャンル3：1)して累積和を作っておく。例えばジャンル1の本を1冊目に選ぶとき、選べる組み合わせは、(ジャンル1の冊数)×(ジャンル1以外の冊数)になるので、これをジャンル2が1冊目の時、ジャンル3が1冊目の時…と繰り返していく(既に選ばれたジャンルの本を候補から外すのに累積和を使用)
他の方の解答見てるともっと効率いい解き方ありそう。ジャンルごとのカウント結果を基に組み合わせ全探索(2つ目のコード)とか、重複無視して ${}_n C _2$ の組み合わせ求めた後に、同一ジャンルから2冊選ばれてしまう組み合わせを除外する(3つ目のコード)とか

the_best_gift.py

from collections import Counter
N,M = map(int,input().split())
A = list(map(int,input().split()))

cnt = list(Counter(A).values())
l = len(cnt)
ruiseki = [0]*(l+1)
for i in range(l):
    ruiseki[i+1] = ruiseki[i] + cnt[i]

ans = 0
for i in range(l):
    ans += cnt[i]*(ruiseki[l]-ruiseki[i+1])
print(ans)

the_best_gift2.py

#!/usr/bin/env python3
 from collections import Counter
 
def solve():
    N, M = map(int, input().split())
    gen = list(map(int, input().split()))
 
    cnt = Counter(gen)
 
    total = 0
    for gen1, cnt1 in cnt.items():
        for gen2, cnt2 in cnt.items():
            if gen1 == gen2:
                continue
            total += cnt1 * cnt2
    print(total//2)
 
if __name__ == '__main__':
    solve()

the_best_gift3.py

from collections import Counter
n,m = map(int, input().split())
l = list(map(int, input().split()))

num = Counter(l)

ans = n*(n-1)//2
for i in num.values():
    ans -= i*(i-1)//2
print(ans)

C. Load Balancing

WA取れずに解説ACすらできず。ちゃんと考察できていなかったので、学びの多い問題となりました。数列って本当に競プロのテーマになりやすいですね。普段から、数列の法則性に想像を巡らせるように意識したいです。

ポイント

前提として、ある数列をロードバランス(任意の要素のペアを選び小さい方を+1、大きい方を-1)して全要素を同じ数字(=数列の平均値)にできるのは、数列の和 $S$ が数列の要素数 $N$ で割り切れるとき
$S$ が $N$ で割り切れない場合にロードバランスすると、 $S$ を $N$ で割った余り( $S$ % $N$ )の数ぶんだけ、数列の平均値(の切り捨て) $S$ // $N$ に1を足した数値の要素ができ、それ以外が $S$ // $N$ を値に持つ要素となる
上記の考えを基にロードバランス完了後の数列を生成してソートし、元の数列をソートしたものとで各要素の差分の絶対値を足し合わせてその合計を半分にしたものが答え

load_balancing.py

import sys
input = sys.stdin.readline

n = int(input())
m = list(map(int, input().split()))
m.sort()
s = sum(m)
l = []

for i in range(n):
    if i<s%n:
        l.append(s//n+1)
    else:
        l.append(s//n)
l = l[::-1]

ans = 0
for mi, li in zip(m, l):
    ans += abs(mi-li)
print(ans//2)