ABC267の振り返り(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 - Saturday

やってみよう！

A関数を完成させて「Run」ボタンをクリックしよう！(テストデータ省略)

def A(S): pass print(A("Wednesday")) # 3 print(A("Monday")) # 5

自由欄

try

def A(S): return 5 - [ "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", ].index(S) print(A("Wednesday")) # 3 print(A("Monday")) # 5

結果：提出 #34535168

自由欄

B - Split?

やってみよう！

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

test_dataB = [ { "in":["0101110101"], "out": "Yes" },{ "in":["0100101001"], "out": "Yes" },{ "in":["0000100110"], "out": "No" },{ "in":["1101110101"], "out": "No" }, ] def B(S): pass test_all(B)

自由欄

try

以下がコンテス中にACした回答。
色々とかっこ悪いです。

def B(S): *pin, = map(int, S) pin = [None] + pin col = [ sum(pin[7:8]), sum(pin[4:5]), sum([pin[2],pin[8]]), sum([pin[1],pin[5]]), sum([pin[3],pin[9]]), sum(pin[6:7]), sum(pin[10:11]), ] phase = 1 if pin[1] == 0: for c in col: if phase in [1, 3] and c > 0: phase += 1 elif phase == 2 and c == 0: phase += 1 return "Yes" if phase == 4 else "No" test_all(B)

結果：提出 #34546981

解説を見る

こちらの解説で紹介されているのが、ピンの立っている列の集合を使ってスプリットを判定するというもの。
なるほどなぁ。

def B(S): if S[0] == "1" or "1" not in S: return "No" col = [4, 3, 5, 2, 4, 6, 1, 3, 5, 7] p_col = set() for p, c in zip(S, col): if p == "1": p_col.add(c) return "Yes" if len(p_col) != max(p_col) - min(p_col) + 1 else "No" test_all(B)

結果：提出 #34797483

自由欄

try2: n本のピンに対応

本筋からは逸れますが、ピンの立っている列をハードコーディングするのが気になります。
という訳でピンの本数から列番号を生成する関数を作ってみました。

が、やっぱりかっこ悪い…

①素朴な実装

def to_column(size, first_pin_col=0): if size < 1: return [] ret = [first_pin_col] i = 1 # 2行目のピンから見ていく cnt = 1 while True: edge = ret[0] - i for j in range(i + 1): if cnt == size: break ret.append(edge + 2 * j) cnt += 1 else: i += 1 continue break return ret

②短くしてみた

from math import ceil from itertools import chain def to_column(size, first_pin_col=0): rows = ceil((2 * size + 0.25)**(1/2) - 0.5) return list(chain.from_iterable( [[first_pin_col - r + c for c in range(0, (r+1)*2, 2)] for r in range(rows)] ))[:size]

戯れに描画関数も作ってみました。

描画関数定義：print_pins

# 縮小表示 def print_pins(pins, col): cols = max(col) - min(col) + 1 if cols % 2 == 0: cols += 1 mn = min(col) col = [c - mn for c in col] lines = [] i = 0 r = 0 while i != len(pins): line = [" "] * cols for _ in range(r + 1): line[col[i]] = "●" if pins[i] == "1" else "○" i += 1 if i == len(pins): break r += 1 lines.append("".join(line)) print(*lines[::-1], sep="\n")

以下のように使用できます。

pins, = test_dataB[0]["in"] print_pins(pins, to_column(len(pins)))

10本以上でもOK

import random n = 55 pins = random.choices(["0", "1"], k=n) print_pins(pins, to_column(n))

行が全部埋まらなくてもOK

import random n = 100 pins = random.choices(["0", "1"], k=n) print_pins(pins, to_column(n))

上の回答をto_column関数に置き換え

def B(S): if S[0] == "1" or "1" not in S: return "No" p_col = set() for p, c in zip(S, to_column(len(S))): if p == "1": p_col.add(c) return "Yes" if len(p_col) != max(p_col) - min(p_col) + 1 else "No" test_all(B)

結果：提出 #34801018

自由欄

C - Index × A(Continuous ver.)

やってみよう！

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

test_dataC = [ { "in":[4, 2, [5, 4, -1, 8]], "out": 15 },{ "in":[10, 4, [-3, 1, -4, 1, -5, 9, -2, 6, -5, 3]], "out": 31 }, ] def C(N, M, A): pass test_all(C)

自由欄

try1

時間内にACならず。
まず素朴に実装したのがこちら。

def C(N, M, A): return max(sum(j*A[i+j-1] for j in range(1, M+1)) for i in range(N-M+1)) test_all(C)

結果：TLE x 22

提出 #34555434 - NECプログラミングコンテスト2022 (AtCoder Beginner Contest 267)

自由欄

try2

なにかしら前処理が必要だと考え頭を捻ったものの$O(NM)$から逃れられず…
ダメ元でnumpy使ってみたけどやっぱりダメでした

import numpy as np def C(N, M, A): A = np.array(A) return np.stack([A[i:i+N-M+1]*(i+1) for i in range(M)]).sum(axis=0).max() test_all(C)

結果：TLE x 22, MLE x 1
初めてMLE(メモリ制限超過)が出た😂

提出 #34565855 - NECプログラミングコンテスト2022 (AtCoder Beginner Contest 267)

自由欄

解説

という訳で解説を見ます。
pythonで書き換えるとこんな感じ。

from itertools import accumulate def C(N, M, A): *acc, = accumulate([0] + A) B = [sum(A[i] * (i + 1) for i in range(M))] for i in range(N-M): B.append(B[-1] + M * A[M + i] - (acc[M + i] - acc[i])) return max(B) test_all(C)

結果：AC

提出 #34600152 - NECプログラミングコンテスト2022 (AtCoder Beginner Contest 267)

解説を理解する

サンプルデータの2つ目を例に考えます。

N, M, A = test_dataC[1]["in"] A = np.array(A) N, M, A # 縮小表示 import pandas as pd import jinja2 df = pd.DataFrame( np.stack( [np.concatenate([[0]*i, A[i:i+N-M+1]*(i+1), [0]*(M-1-i)]) for i in range(M)], ), columns=range(1, 11), dtype=int ) df.index = [ "x1", "x2", "x3", "x4", ]

まずは4行目で、$A_1$から選んだ$\sum^{M}_{i=1}i \times B_i$を計算します。

# 縮小表示 style_str = lambda _: "background: lightgreen; font-weight: bold" sty = df.style for i, label in enumerate(df.index, 1): sty = sty.applymap(style_str, subset=(f"{label}", i)) sty sum(A[i] * (i + 1) for i in range(M))

次に$A_2$から選んだ場合の値を計算したいのですが…

# 縮小表示 style_str = lambda _: "background: aqua; font-weight: bold" sty = df.style for i, label in enumerate(df.index, 2): sty = sty.applymap(style_str, subset=(f"{label}", i)) sty

以下の式のように、すでに計算した値から該当範囲の累積和を引いて最終項を加えることで算出できます。

$$ \begin{matrix} & 1 \times A_1 & + & 2 \times A_2 & + & 3 \times A_3 & + & 4 \times A_4 & &\\ -) & A_1 & + & A_2 & + & A_3 & + & A_4 & - & 4 \times A_5 \\\hline & & & 1 \times A_2 & + & 2 \times A_3 & + & 3 \times A_4 & + & 4 \times A_5 \\ \end{matrix} $$

という処理を行っているのが5,6行目ということですね。
はぇ～、すっごい

D - Index × A(Not Continuous ver.)

やってみよう！

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

test_dataD = [ { "in":[4, 2, [5, 4, -1, 8]], "out": 21 },{ "in":[10, 4, [-3, 1, -4, 1, -5, 9, -2, 6, -5, 3]], "out": 54 }, ] def D(N, M, A): pass test_all(D)

自由欄

try

コンテスト中、C問題に行き詰まってD問題を解こうと試みましたが、DP使うんだろうことは想像できても「選ぶ場合と選ばない場合をどうすりゃええや…」となってお手上げでした。
以下は解説参照。いざ正答を見るとこれしかないって感じです。
maxで大きい方を採るのね、はいはい。ちくしょー！😭

def D(N, M, A): dp = [[0] * (M + 1) for _ in range(N + 1)] dp[0][1] = -10**14 A = [0] + A for i in range(1, N+1): for j in range(1, M+1): dp[i][j] = (-10**14 if j > i else max(dp[i-1][j], dp[i-1][j - 1] + A[i] * j)) # print(np.array(dp)) return dp[-1][-1] test_all(D)

結果：提出 #34601411 - NECプログラミングコンテスト2022 (AtCoder Beginner Contest 267)

解説でなぜ-1000000000000000000llを初期値としてるのか最初分からなかったのですが、$A_i$が全て$-2 \times 10^5$で$M = N = 2000$だった場合、最大値は$-40002000000000$になります。

sum(i*-2*10**5 for i in range(1, 20001))

比較する初期値としてはそれよりも小さくなければならない、ということで上のコードでは-10**14としました。

自由欄