ABC258の振り返り(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 - When?

やってみよう！

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

def A(K): pass A(63) A(45) A(100)

自由欄

try

divmod関数はなにかと便利です。
また、解説でも紹介されている datetimeモジュールは日時の演算をよしなにしてくれます。

from datetime import * def A(K): h, m = divmod(K, 60) print("divmod :", f'{21+h}:{m:02}') d = datetime.combine(date.today(), time(21)) + timedelta(minutes=K) print("datetime:", d.strftime("%H:%M")) A(63) A(45) A(100)

結果：提出 #32886823 - AtCoder Beginner Contest 258

自由欄

B - Number Box

やってみよう！

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

test_dataB = [ { "in":[4, ['1161', '1119', '7111', '1811']], "out": 9786 },{ "in":[10, ['1111111111', '1111111111', '1111111111', '1111111111', '1111111111', '1111111111', '1111111111', '1111111111', '1111111111', '1111111111']], "out": 1111111111 } ] def B(N, A): pass test_all(B)

自由欄

try

こんな感じ。
コンテスト中の提出とは若干異なりますが、考え方はだいたい一緒です。

2次元配列で考える場合、水平方向の計算が楽です。
また、進行方向が逆になるだけの2方向はまとめることができます。

という訳で、垂直方向と斜め方向(×2)を水平方向で計算できる形にして共通の処理にかけてます。

def transpose(A): return ["".join(r) for r in zip(*A)] def proc(m): ret = 0 for r in m: for c in range(len(r)): right = r[c:]+r[:c] left = right[::-1] ret = max(ret, int(right), int(left)) return ret def B(N, A): return max([proc(m) for m in [ A, transpose(A), transpose([r[i:]+r[:i] for i, r in enumerate(A)]), transpose([r[::-1][i:]+r[::-1][:i] for i, r in enumerate(A)]), ]]) test_all(B)

結果：提出 #33571411 - AtCoder Beginner Contest 258

自由欄

C - Rotation

やってみよう！

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

test_dataC = [ { "in":[3, 3, 'abc', [[2, 2], [1, 1], [2, 2]]], "out": '''b a''' },{ "in":[10, 8, 'dsuccxulnl', [[2, 4], [2, 7], [1, 2], [2, 7], [1, 1], [1, 2], [1, 3], [2, 5]]], "out": '''c u c u''' } ] def C(N, Q, S, qs): pass test_all(C)

自由欄

try

こちらもコンテスト中の提出とは微妙に異なりますが、こんな感じです。

B問題より簡単でしたね。

def C(N, Q, S, qs): top = 0 ret = [] for q, x in qs: if q == 1: top = (top + N - x) % N else: ret.append(S[(top + x - 1) % N]) return "\n".join(ret) test_all(C)

結果：提出 #33653820 - AtCoder Beginner Contest 258

自由欄

D - Trophy

やってみよう！

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

test_dataD = [ { "in":[3, 4, (3, 2, 4), (4, 3, 2)], "out": 18 },{ "in":[10, 1000000000, (3, 1, 4, 1, 5, 9, 2, 6, 5, 3), (3, 6, 7, 8, 7, 9, 4, 4, 1, 1)], "out": 1000000076 }, ] def D(N, X, A, B): pass test_all(D)

自由欄

try1: 素朴な実装

def D(N, X, A, B): *AB, = zip(A, B) ans = 10 ** 19 acc = 0 for i, (a, b) in enumerate(AB[:min(N, X)], start=1): acc += a + b if acc > ans: break ans = min(ans, acc + b * (X - i)) return ans test_all(D)

結果：提出 #34067250

try1-2: 短くしてみた

上のスクリプトを圧縮しました。可読性が著しく悪いです。
セイウチ演算子を使ってるのでPyPyでは実行不可です。

def D(N, X, A, B): *AB, = zip(A, B) acc = 0 return min((acc := acc + a + b) + b * (X - i) for i, (a, b) in enumerate(AB[:min(N, X)], start=1)) test_all(D)

結果：提出 #34090814

try2: 先に累積和を取る

今回は何度も和を取らなければならないような問題では無いので、上の解法で十分です。
めちゃくちゃ短くなるとか読みやすくなるとかでも無いので、微妙な感じです。

from itertools import accumulate from operator import add def main(N, X, A, B): *acc, = accumulate(map(add, A, B)) return min(B[i] * (X-i-1) + acc[i] for i in range(min(N, X))) test_all(D)

結果：提出 #34077549

自由欄

まとめ

1周全探索するだけの問題でもパッとみ累積和とりたくなっちゃう