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

振り返りです。

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 - Full House

やってみよう！

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

test_dataA = [ { "in":[[1, 2, 1, 2, 1]], "out": "Yes" },{ "in":[[12, 12, 11, 1, 2]], "out": "No" } ] def A(n): pass test_all(A)

自由欄

try

こんな感じ。

def A(n): s = set(n) if len(s) == 2 and n.count(s.pop()) in [2, 3]: return "Yes" else: return "No" test_all(A)

結果：提出 #33856906

自由欄

解説

解説ではソートを利用した方法が紹介されています。

なるほどなぁ～

def A(n): n = sorted(n) if ( n[0] == n[1] and n[2] == n[4] or n[0] == n[2] and n[3] == n[4] ): return "Yes" else: return "No" test_all(A)

自由欄

B - Ancestor

やってみよう！

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

test_dataB = [ { "in":[3, [1, 2]], "out": 2 },{ "in":[10, [1, 2, 3, 4, 5, 6, 7, 8, 9]], "out": 9 }, ] def B(N, P): pass test_all(B)

自由欄

try

ちょっと設問を理解するのに時間が掛かりました。
入力の形式までしっかり確認しないとですね。

def B(N, P): P = [None, None] + P gen = 0 now = N while now != 1: now = P[now] gen += 1 return gen test_all(B)

結果：提出 #33814353

自由欄

C - Monotonically Increasing

やってみよう！

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

test_dataC = [ { "in":[2, 3], "out": """1 2 1 3 2 3""" },{ "in":[3, 5], "out": """1 2 3 1 2 4 1 2 5 1 3 4 1 3 5 1 4 5 2 3 4 2 3 5 2 4 5 3 4 5""" }, ] def C(N, M): pass test_all(C)

自由欄

try

以下でBufやreturnはこの記事用です。
combinationsをプリントするだけです。

from itertools import combinations class Buf(): def __init__(self): self.s = "" def write(self, s): self.s += s def C(N, M): buf = Buf() for com in combinations(range(1, M+1), N): print(*com, file=buf) return buf.s[:-1] test_all(C)

結果：提出 #33817810

自由欄

解説

解説をちょっと修正してジェネレーターにしたのが以下。

def gen_set(N, K, A=[]): if len(A) == K: yield A return if len(A) == 0: start = 1 else: start = A[-1] + 1 for i in range(start, N + 1): yield from gen_set(N, K, A + [i]) def C(N, M): buf = Buf() for com in gen_set(M, N): print(*com, file=buf) return buf.s[:-1] test_all(C)

結果：提出 #33939686

自由欄

D - Left Right Operation

やってみよう！

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

test_dataD = [ { "in":[5, 4, 3, [5, 5, 0, 6, 3]], "out": 14 },{ "in":[4, 10, 10, [1, 2, 3, 4]], "out": 10 },{ "in":[10, -5, -3, [9, -6, 10, -1, 2, 10, -1, 7, -15, 5]], "out": -58 }, ] def D(N, L, R, A): pass test_all(D)

自由欄

解説

今回はコンテスト終了後に自力ACできたのですが、解説でその考え方をめちゃくちゃスマートに体現されていたので、先にご紹介します。

正直、解説は全く理解できてませんが、コードは至ってシンプル。それがこちら。

def D(N, L, R, A): ans = R * N acc = 0 for i in range(N): acc = min(acc + A[i], L * (i + 1)) ans = min(ans, acc + R * (N - 1 - i)) return ans test_all(D)

結果：提出 #33940848

try

で、コンテスト後に自力ACしたというのがこれ。
なにやら累積和を作る前処理をしたり、それを使った値の計算であったり、複雑そうなことをしていますが、実はやってることは上の解説のコードと全く一緒です。

自力ACできて嬉しい！という感情のあとに、同じことを実現するのにこんなにも差が出るものかという徒労感で心が揺さぶられました。

とりあえず線形探索するなら累積和の前処理しなくてもいい場合がある、ってことは覚えとこうと思います。

import numpy as np def D(N, L, R, A): filledL = np.cumsum([0] + [L] * N) A = A[::-1] acc = np.cumsum([0] + A) filledR = np.cumsum([0] + [R] * N) # 各項の値が大きいほど、置き換え後の総和は小さくなる # processed[0]は0で一つも置き換えない(y = 0)ことを意味する processed = acc - filledR # 全てLで置き換える(x = N, y = 0) ans = filledL[N] # 0 <= x < n better_y="0" for in range(n-1, -1, -1): i="N" - if processed[i]> processed[better_y]: better_y = i ans = min(ans, filledL[x] + filledR[better_y] + acc[i] - acc[better_y]) return ans test_all(D)

結果：提出 #33852104

自由欄

まとめ

組み合わせの生成とかをPythonのライブラリに頼ってたけど、実装できるようになりたいなぁ(願望)