ABC268の振り返り(A, B, C, D)

C問題解けず…
無念の振り返りです。

def test_all(f): for i, data in enumerate(eval(f'test_data{f.__name__[0]}')): exp = data["out"] ans = f(*data["in"]) result = "AC" if exp == ans else "WA" print(f"{i+1} {result}: expected: {exp}, output: {ans}")

A - Five Integers

略

B - Prefix?

略

結果：提出 #34729850

C - Chinese Restaurant

やってみよう！

C関数を完成させて「Run」ボタンをクリックしよう！

test_dataC = [ { "in":[4, [1, 2, 0, 3]], "out": 4 },{ "in":[3, [0, 1, 2]], "out": 3 },{ "in":[10, [3, 9, 6, 1, 7, 2, 8, 0, 5, 4]], "out": 5 }, ] def C(N, p): pass test_all(C)

自由欄

解説を見る

コンテスト中、そして振り返って考えても$O(N^2)$から抜け出せず(#34743985、#35564583)…。
おとなしく解説を見ます。

「料理に聞く」のか…！お前を何回回せばいいんだい、と…！

def C(N, p): cnt = [0] * N for i, d in enumerate(p): cnt[(d + 1 - i) % N] += 1 cnt[(d - i) % N] += 1 cnt[(d - 1 - i) % N] += 1 return max(cnt) test_all(C)

結果：#35565353

ちなみに、pythonでは被除数が負の場合でもよしなにしてくれる(参考：ABC266-Bの解説)ので、% Nする際、解説のように被除数にNを加算する必要はありません。

自由欄

D - Unique Username

やってみよう！

D関数を完成させて「Run」ボタンをクリックしよう！

test_dataD = [ { "in":[1, 1, ['chokudai'], ['chokudai']], "out": -1 },{ "in":[2, 2, ['choku', 'dai'], ['chokudai', 'choku_dai']], "out": "dai_choku" },{ "in":[2, 2, ['chokudai', 'atcoder'], ['chokudai_atcoder', 'atcoder_chokudai']], "out": -1 },{ "in":[4, 4, ['ab', 'cd', 'ef', 'gh'], ['hoge', 'fuga', '____', '_ab_cd_ef_gh_']], "out": "ab__ef___cd_gh" }, ] def D(N, M, S, T): pass test_all(D)

自由欄

try

コンテスト中はたどり着けなかったですが、せっかくなのでやってみます。
と思って問題を見た瞬間、一気にやる気が失せました…。

全然、アルゴリズム感がない！！（C問題も解けなかったことは一旦棚に上げます😇）
かと言って、実装するのはそれはそれで面倒くさそう…。

とりあえず義務感で実装したのが以下。

from itertools import permutations from itertools import combinations_with_replacement from itertools import chain def D(N, M, S, T): pad = 16 - (sum(len(s) for s in S) + N - 1) if pad < 0: return -1 ans = [] perm = permutations(S) for per in perm: for p in range(pad + 1): for com in combinations_with_replacement(range(N - 1), p): sep = ["_"] * (N - 1) for c in com: sep[c] += "_" new = "".join(chain(*zip(per, sep + [""]))) if len(new) > 2: ans.append(new) ans = set(ans) - set(T) return ans.pop() if len(ans) else -1 test_all(D)

結果：#35569501

何の意外性もなくACとなりました。
初めてcombinations_with_replacementを使って勉強になったということで、良しとします！

自由欄