Codeforces Round #332 (Div. 2) A～C

virtualで参加。

結果

時間内にACできたのはAだけ。1:30くらいで降参してEditorialを見ました。

A～CはすべてPythonで解けるくらい実装は軽かったので、しっかり解きたかったところ。

A. Patrick and Shopping

Problem - A - Codeforces

通り方はすべてで4通り。それらの最小値をとる。

a, b, c = map(int, input().split())
print(min(a + b + c, 2 * (a + b), 2 * (b + c), 2 * (c + a)))

B. Spongebob and Joke

Problem - B - Codeforces

数列fとbが与えられる。fの要素をbに割り当てる方法が一意に存在する(=Possible)か、複数存在する(=Ambiguity)か、1つも存在しない(=Impossible)かを判定せよ、という問題。

bの各要素について、それがfに複数含まれればAmbiguity、fになければImpossibleである。ただしImpossibleの判定が即座に決まるのに対し、Ambiguityの場合はその後Impossibleに判定が更新されるケースがあることに注意。よってAmbiguityはフラグで管理する。(これに気づかなくてWAだった)

from collections import defaultdict as ddict

n, m = map(int, input().split())
f = list(map(int, input().split()))
b = list(map(int, input().split()))

idf = ddict(list)
for i in range(n):
    idf[f[i]].append(i)

ans = [0] * m
flag_amb = False
for i in range(m):
    if len(idf[b[i]]) == 0:
        print("Impossible")
        exit()
    if len(idf[b[i]]) > 1:
        flag_amb = True
    ans[i] = idf[b[i]][0] + 1

if flag_amb:
    print("Ambiguity")
else:
    print("Possible")
    print(" ".join(map(str, ans)))

C. Day at the Beach

Problem - C - Codeforces

数列hをいくつかのブロックに分け、ブロックごとにソートしたとき全体がソートされるようにしたい。最大でいくつのブロックに分けることができるか、という問題。

と の間でブロックを分けられる必要十分条件は、iまでの最大値 <= i + 1以降の最小値 となることである。よってこの条件を満たすiの個数 + 1が求めるブロックの最大個数となる。

n = int(input())
h = list(map(int, input().split()))

premax = [0] * n
premax[0] = h[0]
for i in range(1, n):
    premax[i] = max(h[i], premax[i - 1])
suffmin = [0] * n
suffmin[-1] = h[-1]
for i in range(n - 1)[::-1]:
    suffmin[i] = min(h[i], suffmin[i + 1])

ans = 1
for i in range(n - 1):
    if premax[i] <= suffmin[i + 1]:
        ans += 1

print(ans)

せめて2完は安定させたい。