今週もAtCoder Beginner Contest 313に参加をしました。

結果

A-Cの3完、AとBで1ペナでした。

Qlitreさんの第四回日本最強プログラマー学生選手権-予選-（AtCoder Beginner Contest 313）での成績：2533位
パフォーマンス：1056相当
レーティング：1057→1057 (±0) :|#AtCoder #第四回日本最強プログラマー学生選手権-予選-（ABC313） https://t.co/vsCDwx14we

— Qlitre (@kuri_tter) August 5, 2023

今回は普段よりも難しめの問題セットだったということで、Cまでの３完という結果で終わりました。

結果としてレートは変わらず、AとBで１ペナずつ出してしまったのが、悔やまれました。

それでは早速コンテストを振り返っていきたいと思います。

A - To Be Saikyo

https://atcoder.jp/contests/abc313/tasks/abc313_a

N人のプログラミング力をあらわす数列が与えられ、人１が一番大きい数字になるためにいくつ増やす必要があるかを求める問題です。

人１をpopして残りの最大と比較したのですが、人がそもそも一人しかいないケースを考慮していなくて、エラーとなってしまいました。素直に比較すると以下のようでしょうか。

def main():
    n = int(input())
    al = list(map(int, input().split()))
    p = al[0]

    ma = 0
    for i in range(1, n):
        ma = max(ma, al[i])

    if p > ma:
        print(0)
    else:
        print(ma - p + 1)


if __name__ == '__main__':
    main()

B - Who is Saikyo?

https://atcoder.jp/contests/abc313/tasks/abc313_b

N人がいて、人Aは人Bより強いという情報が与えられます。

ここで、もし人Bが人Cよりも強いという情報があったら、人Aは人Cよりも強いです。最強の人を一人で特定できるなら出力する、という問題です。

初見ではトポロジカルソートをして、ソートが可能なら配列の一番最初、ということで答えを出力したのですが、WAになってしまいました。それもそのはずで、次数が０の人間が二人以上いた場合、トポロジカルソートは可能ですが、どちらが強いかは分かりません。

コンテスト中では以下のようにコードを書きました。

from collections import defaultdict
import heapq


def topological_sort(n: int, graph: dict, into_num: list) -> list:
    """
    トポロジカルソートした配列を返す
    トポロジカルソート出来なかった場合は空の配列を返す。
    ※注意 now +1 して返す
    :param n:頂点数
    :param graph: {a:[b,c,d],e:[f]...}
    :param into_num: 次数の配列
    """
    que = []
    for i in range(n):
        if into_num[i] == 0:
            que.append(i)
    ret = []
    while que:
        now = heapq.heappop(que)
        ret.append(now + 1)
        for adj in graph[now]:
            into_num[adj] -= 1
            if into_num[adj] == 0:
                heapq.heappush(que, adj)

    if len(ret) == n:
        return ret
    else:
        return []


def main():
    n, m = map(int, input().split())
    ab = [list(map(int, input().split())) for _ in range(m)]
    into_num = [0] * (n)
    graph = defaultdict(list)
    for a, b in ab:
        a -= 1
        b -= 1
        into_num[b] += 1
        graph[a].append(b)
    # 二人以上次数が０がいたらNG
    if into_num.count(0) >= 2:
        exit(print(-1))
    # トポロジカルソート
    ans = topological_sort(n, graph, into_num)

    if ans:
        print(ans[0])
    else:
        print(-1)


if __name__ == '__main__':
    main()

これでACはできたのですが、よくよく考えると、次数が0の人が一人の時点でその人が最強です。

def main():
    n, m = map(int, input().split())
    ab = [list(map(int, input().split())) for _ in range(m)]
    into_num = [0] * n
    for a, b in ab:
        a -= 1
        b -= 1
        into_num[b] += 1
    # 二人以上次数が０がいたらNG
    if into_num.count(0) >= 2:
        exit(print(-1))
    else:
        for i in range(n):
            if into_num[i] == 0:
                exit(print(i + 1))


if __name__ == '__main__':
    main()

C - Approximate Equalization 2

https://atcoder.jp/contests/abc313/tasks/abc313_c

数列が与えられて、二つのindexを選び＋１、ー１することができます。

数列の最大値と最小値を１以下にするまで、最少で何回操作をする必要があるかを答える問題です。

まず、＋１、ー１するので数列の総和はいくら操作しても変わらないということに気が付きました。

それでどのような数列にしたら一番操作が少なくて済むか、というところを考えるのですが、直感的に平均値をとると少なそうだな、と思います。

ただ数列の総和は変わらないので、全ての数を平均にすることができるときと、できないときがあります。

入力例１をみてみますと…

4
4 7 3 7

数列の総和は21で４個あるので、平均は切り下げで計算して5になります。

ただ、総和は21にしないといけないので、一個6が必要です。この一個という数字は21を４で割った余りです。

ここまで考えて、基本は平均で固めて、余りの数だけ＋１を作るのが最適な形そう、ということに気づきます。

では、平均＋１にどれを割り当てればよいかというと、操作は最小にする必要があるので、なるべく大きい数字を割り当てた方が良いです。

def main():
    n = int(input())
    al = list(map(int, input().split()))
    # 合計を出す
    a_sum = sum(al)
    # 平均を計算する
    avg = a_sum // n
    # 余りを計算する
    rem = a_sum % n
    # 配列をソート
    al.sort()
    ans = 0
    # 余りの数だけ平均＋１で操作する
    for i in range(rem):
        num = al.pop()
        ans += abs(avg + 1 - num)
    # 残ったものを平均にする
    for num in al:
        ans += abs(avg - num)
    # プラスとマイナスで２回ずつ足されているので、答えを２で割る
    print(ans // 2)


if __name__ == '__main__':
    main()

おわりに

D問題は取り組んでみたのですが、何も分からず…３完の結果となりました。

しっかりと解説を読んで、取り組んでいきたいと思います。ではでは。