ABC295の振り返り(A, B, C, D, E)

振り返りです。

AtCoder Beginner Contest 295 - AtCoder
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.
import sys from io import StringIO input = lambda: sys.stdin.readline()[:-1] def test(f, data): stdin = sys.stdin stdout = sys.stdout sys.stdin = StringIO(data["in"]) out = StringIO() sys.stdout = out err = None try: f() except BaseException as e: err = e else: ans = out.getvalue() exp = data["out"] sys.stdin = stdin sys.stdout = stdout if err: raise err result = "AC" if exp == ans else "WA" print(f"{result}: expected: {exp}, output: {ans}") def test_all(f): for i, data in enumerate(eval(f'test_data{f.__name__[0]}'), 1): print(f"case {i}") test(f, data)

A - Probably English

やってみよう!

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

test_dataA = [ { "in":"""10 in that case you should print yes and not no """, "out": """Yes """ },{ "in":"""10 in diesem fall sollten sie no und nicht yes ausgeben """, "out": """No """ } ] def A(): pass test_all(A)

自由欄

解説を見る

ユーザ解説setを使った解法が紹介されています。
思いつかなかったのでメモ。

def A(): input() print("No" if len(set(input().split()) & set(["and", "not", "that", "the", "you"])) == 0 else "Yes") test_all(A)

結果:#40197335

自由欄

B - Bombs

やってみよう!

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

test_dataB = [ { "in":"""4 4 .1.# ###. .#2. #.## """, "out": """...# #... .... #... """ },{ "in":"""2 5 ..#.# ###.# """, "out": """..#.# ###.# """ },{ "in":"""2 3 11# ### """, "out": """... ..# """ },{ "in":"""4 6 #.#3#. ###.#. ##.### #1..#. """, "out": """...... #..... #....# ....#. """ }, ] def B(): pass test_all(B)

自由欄

コンテスト中

こんな感じ。
なんですが、時間掛かった…。実装力…😇

def B(): from copy import deepcopy from itertools import product from string import digits R, C = map(int, input().split()) B = [list(input()) for _ in range(R)] def get_points(p, dist): px, py = p ret = set() for x in range(dist + 1): for y in range(dist + 1 - x): ret.add((px + x, py + y)) ret.add((px - x, py + y)) ret.add((px + x, py - y)) ret.add((px - x, py - y)) return ret ans = deepcopy(B) for i, j in product(range(R), range(C)): if B[i][j] in digits: for x, y in get_points((i, j), int(B[i][j])): if 0 <= 0 x < r and c: ans[x][y]="." for a in ans: print(*a, sep )< py-cell> test_all(B)

結果:#40037758

自由欄

解説を見る

原案者の実装を見ます。
$O(R^2C^2)$でもいいとのこと。

考える量とコーディング量を大分減らせるな…

def B(): from itertools import product R, C = map(int, input().split()) B = [list(input()) for _ in range(R)] for r in range(R): for c in range(C): ans = B[r][c] for r2, c2 in product(range(R), range(C)): if B[r2][c2].isdecimal() and abs(r -r2) + abs(c - c2) <= int(b[r2][c2]): ans="." break print(ans, end ) print()< py-cell> test_all(B)

結果:#40198440

C - Socks

Bより簡単なので省略。

結果:#40040530

D - Three Days Ago

やってみよう!

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

test_dataD = [ { "in":"""20230322 """, "out": """4 """ },{ "in":"""0112223333444445555556666666777777778888888889999999999 """, "out": """185 """ },{ "in":"""3141592653589793238462643383279502884197169399375105820974944 """, "out": """9 """ }, ] def D(): pass test_all(D)

自由欄

解説を見る

全探索($O(|S|^2)$)以外の解法が思いつかず、コンテスト中は早々にスルー。

という訳で解説を見ます。

$R_i$が等しい$i$のうちから相異なる2つを選べば、その組に嬉しい列である区間が対応することになります。

天才かよ…

def D(): from collections import defaultdict S = input() mp = defaultdict(int) cnt = [0] * 10 mp[tuple(cnt)] += 1 for s in S: cnt[int(s)] ^= 1 mp[tuple(cnt)] += 1 res = 0 for v in mp.values(): res += v * (v - 1) // 2 print(res) test_all(D)

結果:#40205349

自由欄

E - Kth Number

やってみよう!

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

test_dataE = [ { "in":"""3 5 2 2 0 4 """, "out": """3 """ },{ "in":"""2 3 1 0 0 """, "out": """221832080 """ },{ "in":"""10 20 7 6 5 0 2 0 0 0 15 0 0 """, "out": """617586310 """ }, ] def E(): pass test_all(E)

自由欄

コンテスト中

Dをスルーしたので挑戦してみました。
結果、サンプルだけACで他はREかTLEでした…

combinations_with_replacementで数字を置き換える全ての組み合わせを列挙していますが、

$N = M = 2000$で$A_i$が全て$0$の場合、列挙する組み合わせは$_{3999}C_{2000}$で$8 \times 10^{1202}$通りになってしまいます。 そりゃ無理だ😇 from math import factorial factorial(3999)//factorial(2000)//factorial(1999) def E(): from collections import defaultdict from functools import reduce from itertools import combinations_with_replacement as cr from math import factorial from operator import mul MOD = 998244353 N, M, K = map(int, input().split()) *A, = map(int, input().replace("0", "").split()) zeros = N - len(A) ans = defaultdict(int) for com in cr(range(1, M + 1), zeros): # print(com) ns = defaultdict(int) for c in com: ns[c] += 1 size = factorial(zeros) // reduce(mul, [factorial(v) for v in ns.values()]) # print(sorted(A + list(com))) x = sorted(A + list(com))[K - 1] ans[x] += size ans[x] %= MOD pat = sum([k * v % MOD for k, v in ans.items()]) % MOD total = pow(pow(M, -1, MOD), zeros, MOD) print(pat * total % MOD) # print(ans) test_all(E)

結果:#40055409

自由欄

宿題

解説を理解しようという気力が湧かないので、宿題とします。

自由欄