ABC320 E - Somen Nagashi (Diff: 1096 緑) の解説 [AtCoder] [Python]

問題へのリンク

https://atcoder.jp/contests/abc320/tasks/abc320_e

問題概要

先頭から順に1~Nの番号がついたN人が一列に並んでいる。これからM回そうめんが流される。

そうめん i は時刻 T_i に流され、量は W_iである。そうめん i が流されたとき、列の先頭にいる人が全てを得る。その人は列から外れ、時刻T_i + S_iに元いた場所に戻ってくる。

それぞれの人がどれだけそうめんを得られたか求めよ。

制約

• 1 ≦ N, M ≦ 10⁵
• 0 < T_1 < T_2 … <T_M ≦ 10⁹
• 1 ≦ S_i, W_i ≦ 10⁹

解説

問題文に出てくる「列」を「そうめん列」と呼ぶことにする。

i番目のそうめんを食べることができるのは、そうめん列の中で番号が最小の人である。この部分は「優先度付きキュー」(heapq)で高速に実装できそうだ。

また、ある人がそうめん i を食べた時、戻ってくる時間はT_i + S_i だと分かっている。そのため、そうめん列から外れた人を管理する「待機列」を作り、そうめん列に戻る時間が小さい順に並べる。そして、そうめん i が配られる前の各タイミングで、「 最も順番が早い人が戻る時間が T_i 以下の時、そうめん列に戻す」操作を繰り返す。

この「待機列」も、(戻る時間, 人の番号)のタプルを要素にすることで、優先度付きキューで実装できそうだ。

実装(Python)

from heapq import *

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

# そうめん列, heapq化
somen_que = list(range(N))
heapify(somen_que)

# そうめんを得た量を管理するリスト
somen_counter = [0] * N

# 待機列
wait_que = []

for _ in range(M):
    T, W, S = map(int, input().split())

    # もし待機列に人がいて,
    # 先頭の戻る時間がT以下なら戻す
    while wait_que and wait_que[0][0] <= T:
        t, p = heappop(wait_que)
        heappush(somen_que, p)

    # そうめん列に誰もいないなら何もしない
    if not somen_que:
        continue

    # p: そうめん列の先頭の人
    p = heappop(somen_que)
    somen_counter[p] += W

    # (pが戻る時間, 番号)のタプルを追加
    heappush(wait_que, (T + S, p))

# 答えを出力
for i in somen_counter:
    print(i)

ABC315 C - Flavors (Diff: 321 灰) の解説 [AtCoder][Python]

2023/8/21 解説を大幅に修正

　 問題へのリンク: https://atcoder.jp/contests/abc315/tasks/abc315_c

問題概要

Nカップのアイスがある。i番目のアイスの味は F_i, 美味しさは S_i (S_iは偶数)である。 この中から2つを選んで食べる。この時の満足度は次のように定義される。

2つのアイスの美味しさをs, t(s≧t)とすると、

• 味が異なれば、満足度は s + t
• 味が同じなら、満足度は s + (t / 2)

満足度の最大値を求めよ。

解説

forループで2つの組を調べていると間に合わない。どのようにして求められるか考える。

N個のアイスのうち最も美味しさが大きいアイスをアイスmとする。(ただし、同じ美味しさのアイスが複数存在するなら、アイスmはそのうちの1つとする。)

すると、アイスmは必ず選ばれる。

理由は、アイスmよりも美味しさが小さいアイスから2つ選んだ時、そのどちらかをアイスmに置き換えることによって、必ず前よりも満足度を高くすることができるからだ。

入力例を見て考える。下の図は、入力例1を示している。同じ色のアイスは同じ種類である。この場合、最も美味しさが大きいアイスmは図の上にあるアイス2である。

入力例1

例えば、アイス1とアイス3を選んだ時の満足度は4+8=12だが、アイス3をアイス2(アイスm)に置き換えることによって満足度が4+10=14に上昇する。

また、アイス1とアイス3を選んだ時の満足度は4+6=10だが、アイス1をアイス2(アイスm)に置き換えることによって満足度は10+6=16に上昇する。

このように、アイスmと同色のものがあればその中で美味しさが小さいもの、無ければ美味しさが小さいものに置き換えることによって、必ず満足度を大きくできる。よって、満足度が最も高いアイスの1つであるアイスmは必ず使わなくてはならないことが分かった。

これが分かれば後は簡単で、アイスmと、アイスm以外の全てのアイスの組を全て試せば良い。計算量はO(N)。実際は全てを試す必要はないが、計算量は変わらない。

実装例(Python)

N = int(input())
I_L = [list(map(int,input().split())) for _ in range(N)]

# idx_x: 最も美味しいアイス(アイスm)のindex
idx_x = 0
# max_d: ここまでの最大の美味しさ
max_d = 0

for i in range(N):
    # もしこれまでで一番美味しかったら更新
    if I_L[i][1] > max_d:
        idx_x = i
        max_d = I_L[i][1]

# アイスmの味f1、美味しさd1
f1, d1 = I_L[idx_x]
# 答え(美味しさの最大値)
ans = 0

#アイスm以外のもう1つのアイスとの組を調べる
for i in range(N):

    # アイスxは既に選択済み
    if idx_x == i: continue

    # i番目のアイスの味f2、美味しさd2
    f2, d2 = I_L[i]

    # 味が同じ
    if f1 == f2:
        ans = max(ans, d1 + d2 // 2)
    # 味が異なる
    else:
        ans = max(ans, d1 + d2)

print(ans)

ABC314 D - LOWER (Diff: 585 茶) の解説 [AtCoder][Python]

問題概要

小文字または大文字のアルファベットN文字から成る文字列Sがある。これからQ個の操作を行う。

• 操作ごとに(t_i, x_i, c_i)が与えられる。
• t_i = 1の時、Sのx_i文字目をc_iに変更する。(c_iは大文字または小文字)
• t_i = 2の時、Sの文字を全て小文字にする。
• t_i = 3の時、Sの文字を全て大文字にする。

Q回の操作後のSを出力せよ。

解説

愚直に操作を行う際の計算量

t_iが1の時、2・3の時の操作を愚直(工夫せず)に行う際の計算量を考える。

t_i = 1の時

t_iの文字をc_iに変更する動作は、Sを1文字ずつリスト化【S=abcであれば(リスト) = [‘a’, ‘b’, ‘c’]のように】しておくことで、O(1)で行える。

t_i = 2, 3の時

全て大文字または小文字にする操作を実装するためには、Sに含まれる全ての文字N個に対して操作を行う必要がある(動作を行っても変化しないものも確認する必要がある)。よって、これを行うのに必要な計算量はO(N)である。

以上のことより、最悪計算量はO(NQ)となり、(5×10⁵)² = 25×10¹⁰回程度の計算が必要になるので間に合わない。

計算量の削減

そこで、計算の重い 全て大文字/小文字 にする回数を減らすことを考える。

Sを1文字変更する動作を操作(変)、Sを全て大文字にする動作を操作(大)、小文字にする操作を操作(小)とする。

操作(大)の後に、操作(小)という操作をするのなら、操作(大)は行わなくても結果は変わらない。また、操作(大)と操作(小)の前や間に操作(変)があっても、変更した文字は小文字に変換されるので、操作(大)を行わなくてよい。 そして、操作(大)→操作(小)→操作(大)と3つ以上続いていく場合も、結局最後の操作(大)のみを行うのと結果は変わらない。最後の操作(小)あるいは(大)の後にある操作(変)は、普通に変更すれば良い。

よって、操作(大)と操作(小)は、その2種類の操作のうち最も後にある1つを行うだけで良い。また操作(変)は、状況に関わらず普通に行える。

そのため、実装は次のようなものになる。

• あらかじめ全ての操作を読み込んでおき、操作(大)または操作(小)の中で最後のものは何番目か記録しておく。
• 1~N個目の操作を順に見て行く。
  • 操作(変)は普通に行う。
  • 操作iが最後の操作(大)または操作(小)でないなら、操作(大)・操作(小)は行わない。
  • 操作iが最後の操作(大)または操作(小)であれば、全ての文字列を大文字または小文字に変更する。

計算量はO(N+Q)。

実装(Python)

N = int(input())
S = list(input())
Q = int(input())

# 操作の組を保存するリスト
Q_L = []

for i in range(Q):
    t, x, c = input().split()

    #t, xは数値に変換
    t = int(t)
    x = int(x)

    # Q_Lに追加
    Q_L.append([t, x, c])

# 操作が全て操作(変)のみの場合のために-1にしておく
lastchange = -1

# 操作を大きい順に見ていく
for i in range(Q - 1, -1, -1):
    t, x, c = Q_L[i]

    # もし操作(大)または(小)なら
    if t == 2 or t == 3:

        # 最後の操作は i
        lastchange = i
        break


# 各操作について
for i in range(Q):
    t, x, c = Q_L[i]

    # もしt == 1[操作(変)]なら
    if t == 1:
        # 変更(リストは0始まりなので1を引く)
        S[x - 1] = c

    #もしt == 2またはt == 3なら
    else:
        # もし最後の操作(大)または(小)なら
        if i == lastchange:

            # 操作(小)の時
            if t == 2:
                for i in range(N):
                    S[i] = S[i].lower()

            #操作(大)の時
            else:
                for i in range(N):
                    S[i] = S[i].upper()

        else:
            # そうでなければ何もしない
            pass

# 文字を結合して出力
print("".join(S))

ABC310 D - Peaceful Teams (Diff: 1368 水) の解説 [AtCoder][Python]

なるほど、再帰DFSか…(今回私は解説ACです)

問題概要

N人をT個のチームに分けたい。しかし、その中には仲の悪いペアがM組存在し、人A[i]とB[i]は同じグループに入れてはいけない。チーム分けの方法は何通りか。

主な制約

• 1 ≦ T ≦ N ≦ 10
• 0 ≦ M ≦ N(N-1)/2

解説

N ≦ 10より、今回は少なくとも10人しかいないので、実際に全てのグループの分け方を列挙することができる。最大の数に関しては、最後にある「おまけ: 今回の条件における最大の通り数」参照。

列挙するためには再帰関数を用いる。状況を示すリストと、最後に入れた人eを引数として持つ再帰関数を作り、「各グループに人e+1を入れられるなら入れて再帰、新しいグループを作れるなら作って再帰し、最終的にTグループになっていればカウント」という動作をするように実装する。詳しくは実装を見てほしい。

実装(Python)

# Pythonで再帰関数を使うためのおまじない
import sys
sys.setrecursionlimit(10**8)

N, T, M = map(int, input().split())
L = [list(map(int, input().split())) for _ in range(M)]

# 仲の悪い相手を管理するリスト
incompatible_list = [set() for _ in range(N+1)]

# 隣接リストのように入れていく
for a,b in L:
    incompatible_list[a].add(b)
    incompatible_list[b].add(a)

# 答えをカウントする変数
cnt = 0

# group_list: 現時点でのグループの状況, e: 最後に入れた要素
def rec(group_list, e):
    # 関数内でもcntを使えるようにグローバル化
    global cnt

    # もし最後の人まで分け終わっていたら
    if e == N:
        # もしグループがT個でなく、条件に合っていないなら
        if len(group_list) != T:
            # 何もせず終了
            return

        # 条件に合っているので、カウントして終了
        cnt += 1
        return

    # 人eまで入れたので、次は人e+1を入れたい
    # 次に入れる人e+1を、グループiに入れられるかを示すリスト
    can_add = [True] * len(group_list)

    # i: e+1と仲の悪い相手
    for i in incompatible_list[e+1]:
        # j: 各グループの番号
        for j in range(len(group_list)):
            # もしe+1と仲の悪い相手iがグループjにいるなら
            if i in group_list[j]:
                # グループjには入れられない
                can_add[j] = False

    # 各グループにおいて
    for i in range(len(group_list)):
        # もしe+1をグループiに追加できるなら
        if can_add[i]:
            # 追加
            group_list[i].add(e+1)
            # 再帰関数
            rec(group_list, e+1)
            # 関数が終わったら元に戻しておく
            group_list[i].discard(e+1)

    # もし新しいグループを作る余裕があるなら
    if len(group_list) < T:
        # グループを追加
        x = group_list + [{e+1}]
        rec(x,e+1)

# 最初は空のリスト、1(0+1)を次に追加するので0
rec([], 0)

# 答えを出力
print(cnt)

おまけ: 今回の条件における最大の通り数

仲の悪いペアがいないとき、N人をTペアに分ける通り数は「第二種スターリング数」というもので表すことができるようだ。これに基づいて計算すると、1 ≦ T ≦ N ≦ 10の条件の中で第二種スターリング数が最大になる「N = 10, T = 5」の時でも42525通りしかない。従って、十分に列挙可能であるといえる。

第二種スターリング数は以下の再帰関数で計算可能(ただしn ≧ k, n < kなら0)。試しに入力例3のN=6, K=4を入れてみると確かに出力例と同じ「65」が返ってくる。

# 第二種スターリング数
def S(n, k):
    if k == 1 or n == k:
        return 1
    return S(n - 1, k - 1) + k * S(n - 1, k)

参考文献

• http://www.igaris.com/math/c.pdf 「2 ボールが区別でき, 箱が区別できない場合」より
• https://manabitimes.jp/math/841

ABC313 B - Who is Saikyo? (Diff: 213 灰) の解説 [AtCoder][Python]

問題へのリンク https://atcoder.jp/contests/abc313/tasks/abc313_b

問題概要

N人の中で、「A[i]はB[i]よりも強い」という関係がM個成り立つ。また、「推移律」(AはBより強く、BがCより強いとき、AはCよりも強いという関係)が成り立つ。 この時、どの人よりも強い人を「最強」と呼ぶことにすると、「最強」の人は1人に特定できるか。

重要な制約

• 2 ≦ N ≦ 50
• 0 ≦ N ≦ N×(N-1)/2
• A[i] ≠ B[i]
• 全ての情報が正しくなるよう強さの関係を作ることができる

解説

AはBよりも強いという関係を「A>B」と表現する。 もし、A>Bという関係があるなら、BはAより強くないのでBは最強では無くなる。よって、すべての関係において弱い側(B側)の人は必ず最強ではない。

逆に、弱い側に1回も出てこなかった人全員に最強である可能性がある。直接の関係からでは弱い側におらず、推移律も直接の関係において弱い側にいないと、他の人より弱いということにはならないからだ。

よって、まず全ての人を最強候補として集合(set)に入れ、各関係で弱い側(B)の人を除外していく。そして、最後に残ったのが1人であれば最強はその人、2人以上残った場合は最強を特定できないので-1を出力する。

問題文より、全ての人が最強ではない(集合に1人も残らない)という状況は生まれない。

ちなみに、今回の条件では最強候補を管理するのに集合ではなくリストを使っても良いが、集合を使うと要素の削除が高速になり、また削除時その要素が存在しない場合でもエラーを出さないので実装が簡単になる。

集合には添え字([i])のようにアクセスできないので、1個しかない集合の要素を出力するのにpop()を使っている。pop()では取り出す要素を指定できないが、今回は集合に1個しかないので問題ない。

実装(Python)

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

# 最強候補を管理する集合
saikyo_set = set()

for i in range(1, N + 1):
    # まず1～Nを最強候補として集合に追加
    saikyo_set.add(i)

for i in range(M):
    # a, bを標準入力から受け取る
    a, b = map(int,input().split())

    # 弱い側(b側)の要素を集合から削除
    saikyo_set.discard(b)

# もし残ったのが1人なら
if len(saikyo_set) == 1:
    # 要素がただ1つしかない集合から取り出す
    print(saikyo_set.pop())

# 2人以上残ったなら
else:
    # -1を出力
    print(-1)

ABC313 C - Approximate Equalization 2 (Diff: 681 茶) の解説 [AtCoder][Python]

問題へのリンク https://atcoder.jp/contests/abc313/tasks/abc313_c

問題概要

長さNの整数列Aがある。Aの要素から2つ選び、一方の要素には1を加え、もう一方の要素には1を引く動作を繰り返す。この時、Aの最小値と最大値の差が1になるようにするために必要な最小の操作回数を求めよ。

例

入力

4
4 7 3 7

出力

3

操作の例

最初 (4,7,3,7)
→ (5,6,3,7)
→ (5,6,4,6)
→ (5,6,5,5)

制約

• 1 ≦ N ≦ 2×10⁵
• 1 ≦ A[i] ≦ 10⁹

解説

この問題を理解しやすくするために、直線状に並んだN個の場所にA[i]個、箱が積み上げられているのをイメージする。「目標」は、一番上に積まれた箱を1つ別の場所に移す動作を繰り返し、最も高く積まれた場所と、最も低い場所の個数の差が1個以内にすることである。この時、最も高い場所の箱を1つ取って(1引く)、最も低い場所に1つ積む(1足す)ことを繰り返し、回数を数えていけば良さそうだ。

しかし、個数が多くなってくると、1個1個箱を動かすのは時間がかかる。そのため、各場所で箱を何個動かせば良いのか考える。

操作を繰り返し行い、「目標」を満たした後のことをイメージする。すると、箱は全て同じような高さで、高いほう(最大値)と低いほう(最小値)があり、高い部分は低い部分より1個だけ多く積み上げられているようになっているはずだ。そして、その時積み上げられる高さは全ての箱(Aの総和)の合計をNで割った「平均値」に近い値になっており、端数の部分で高い部分と低い部分が生まれる。例えば、入力例1では、N=4、箱の数(Aの総和)は21個で、平均値は21/4=5.25となるが、高さは整数でないといけないから操作後の高さは(5,6,5,5)のようになり、低い部分(5)と高い部分(6)が生まれている。

操作後に、この低い部分と高い部分が何個生まれるかを考えれば、操作を何回行えば良いのか分かりそうだ。(最小値)+1=(最大値)なので、操作後は先に全て同じ最小値の分積まれ、箱が余った数だけ1個ずつ積まれた状態になる、と考える。入力例1では、操作後のすべての要素は、21/4の切り捨ての5個積まれ、余った1個(21/4の余り)がどこか1か所に積まれる状態になる。これが積まれる場所に関しては、元のAが大きい順に置いていくと、操作回数を最も少なくできる。

そして、全ての場所で(最初の箱の数)-(操作後の箱の数)を計算し、正の数(箱を除くべき回数)をカウントする。

なお、実際は箱の順番、つまりAの要素は入れ替えても影響がない。操作、また最小値・最大値には場所は関係しないからだ。Aを大きい順に並び替えると、先ほどの余った箱を積む場所を大きい順に置いていく部分の実装が楽になる。

実装(Python)

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

total = sum(A) # Aの総和(箱の個数)
ave = total // N # 総和の平均の切り捨て
L = [ave] * N # 操作後のA[i]の要素(箱の個数)

# 余りの分だけ、大きい順に1を足していく
# (iが小さいほどA[i]が大きくなるようAをソートしている)
for i in range(total % ave):
    L[i] += 1

A.sort(reverse=True) # 要素(箱数)が大きい順に並び変える
ans = 0

for i in range(N):
    if A[i] - L[i] > 0:
        # もし-1する回数が0より大きいなら答えに加える
        # 今回は-1の回数だけを集計している
        ans += A[i] - L[i]

print(ans)

ABC312 D - Count Bracket Sequences (Diff: 964 緑) の解説[AtCoder][Python]

問題へのリンク https://atcoder.jp/contests/abc312/tasks/abc312_d

問題概要

'('、')'、'?'の3つの文字からなる文字列Sが与えられる。 この時、'?'を'('または')'に置き換えて括弧列になるような置き換え方の個数を998244353で割った余りを出力せよ。

括弧列: すべての'('と')'を、'('、')'の順番のままペアを作れる文字列。例えば、(())は括弧列、 )(は括弧列ではない。

解説

動的計画法を用いる。

まず、括弧列の条件を考える。すると、次の2条件を満たすことが分かる。

• '('と')'が同数
• 文字列を左から見ていったとき、')'の数が'('を超えることはない。

1つ目の条件に関しては、'('と')'が同数で無ければ()のペアを作ることができない。2つ目は、')'の数が'('を超えると、超えた')'は左側に'('がないのでペアを作れない。

動的計画法の結果をメモする配列をdpとする。

dp[(左からi文字目まで見て)] ['('がj個] [')'がk個]]とすると、おおよそ計算回数が(Sの長さ)の3乗 (O(|S|)³、|S|はSの長さ)となり、Sが3000文字だった時にTLEになってしまいそうだ。

今回は、'('から')'を引いた数を管理することを考え、dp[(i文字目まで見て)] ['(' - ')'の数]とする。すると、最後の文字まで見て'(' - ')'が0なら、'('と')'が同数であるということになる。また、'(' - ')'がマイナスの値になる時は、')'の数が'('より大きくなり、条件2を満たさなくなっているので計算する必要がない。計算量もO(|S|^2)となり間に合う。

※今回は、S[i]は1始まりで考える。先頭の文字は0文字目ではなく1文字目とする。

dpの式は、配るdpで考えたとき、次の文字S[i+1]が'?'であれば'('の時と')'の時両方を選べる。S[i+1]が'('または')'の時はそれを選ぶしかない。

そのS[i+1]に基づいて、'('を選ぶとき、'(' - ')'の数は1増加し、')'を選ぶと'(' - ')'の数は1減少する。よって、次のようになる。

dp[i+1][j+1] = dp[i][j] (S[i+1] in ['(','?'])
dp[i+1][j-1] = dp[i][j] (S[i+1] in [')','?'])

そして、最終的に出力すべき値はdp[N][0]である。

実装例(Python)

S = input()
# Sの長さをNとする
N = len(S)
# 添字を1始まりにするため先頭に適当な文字を追加
S = "!" + S 

dp = [[0] * (N+1) for _ in range(N+1)]
# 1文字も選ばずに、'(' - ')'=0になるように選ぶ方法は1通り
dp[0][0] = 1

MOD = 998244353

for i in range(N):
    for j in range(N):
        #もしS[i+1]が'('または'?'なら
        if S[i+1] in ('(', '?'):
            # (を選ぶ
            dp[i+1][j+1] += dp[i][j]
            # 余りをとる
            dp[i+1][j+1] %= MOD

        #もしS[i+1]が')'または'?'なら
        if S[i+1] in (')', '?'):
            # )を選ぶ j-1<0の時は考えない
            if j-1<0: continue
            dp[i+1][j-1] += dp[i][j]
            # 余りをとる
            dp[i+1][j-1] %= MOD

# N文字目まで見て'(' - ')'が0になる時が括弧列
print(dp[N][0])