Arakaki Tokyo

ABC307の振り返り(C, D, E)

Arakaki Tokyo — Mon, 17 Jul 2023 11:58:59 GMT

振り返りです。

Tokio Marine & Nichido Fire Insurance Programming Contest 2023（AtCoder Beginner Contest 307) - 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)

C - Ideal Sheet

やってみよう！

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

test_dataC = [ { "in":"""3 5 #.#.. ..... .#... 2 2 #. .# 5 3 ... #.# .#. .#. ... """, "out": """Yes """ },{ "in":"""2 2 #. .# 2 2 #. .# 2 2 ## ## """, "out": """No """ },{ "in":"""1 1 # 1 2 ## 1 1 # """, "out": """No """ },{ "in": """3 3 ### ... ... 3 3 #.. #.. #.. 3 3 ..# ..# ### """, "out": """Yes """ }, ]

def C(): pass test_all(C)

自由欄

コンテスト中

慣れないタイプの問題に困惑して実装の方針を立てるのに時間がかかる・・・
⇨結局以下のようなことを考えた(下図も参照)

シートCを想定して大きなマトリックスを作り、中央にシートAを配置する
シートBを、シートAから上下左右で最大8マス離れる範囲で動かす

一致判定として黒マスの相対座標を返すnormalize関数を作成しました。

def C(): from copy import deepcopy from itertools import product HA, WA = map(int, input().split()) A = [input() for _ in range(HA)] HB, WB = map(int, input().split()) B = [input() for _ in range(HB)] HX, WX = map(int, input().split()) X = [input() for _ in range(HX)] def normalize(m): ret = [] left_top = None for i in range(len(m)): for j in range(len(m[0])): if m[i][j] == "#": if left_top: ret.append(tuple(a - b for a, b in zip([i, j], left_top))) else: left_top = (i, j) ret.append((0, 0)) return ret x_pat = normalize(X) m_base = [list("." * (WB * 2 + WA + 16)) for _ in range(HB * 2 + HA + 16)] for i, j in product(range(HA), range(WA)): if A[i][j] == "#": m_base[HB + 8 + i][WB + 8 + j] = "#" for i in range(HB + HA + 16): for j in range(WB + WA + 16): m = deepcopy(m_base) for k in range(HB): for l in range(WB): if B[k][l] == "#": m[i + k][j + l] = "#" if x_pat == normalize(m): print("Yes") return print("No")

test_all(C)

結果：#42922279

WA x 1 ...😩
結局デバッグできずに無念の試合終了

自由欄

振り返り

WA x 1の原因ですが、結論から言えば

「シートBを、シートAから上下左右で最大8マス離れる範囲で動かす」とすべきところを、
右と下に最大7マスまでしか動かしてなかった

からでした😇
なんというボーンヘッド💀

修正した該当箇所は31行目からのループ部分の17です。

...
    for i in range(HB + HA + 17):
        for j in range(WB + WA + 17):
            ...

def C(): from copy import deepcopy from itertools import product HA, WA = map(int, input().split()) A = [input() for _ in range(HA)] HB, WB = map(int, input().split()) B = [input() for _ in range(HB)] HX, WX = map(int, input().split()) X = [input() for _ in range(HX)] def normalize(m): ret = [] left_top = None for i in range(len(m)): for j in range(len(m[0])): if m[i][j] == "#": if left_top: ret.append(tuple(a - b for a, b in zip([i, j], left_top))) else: left_top = (i, j) ret.append((0, 0)) return ret x_pat = normalize(X) m_base = [list("." * (WB * 2 + WA + 16)) for _ in range(HB * 2 + HA + 16)] for i, j in product(range(HA), range(WA)): if A[i][j] == "#": m_base[HB + 8 + i][WB + 8 + j] = "#" for i in range(HB + HA + 17): for j in range(WB + WA + 17): m = deepcopy(m_base) for k in range(HB): for l in range(WB): if B[k][l] == "#": m[i + k][j + l] = "#" if x_pat == normalize(m): print("Yes") return print("No")

test_all(C)

結果：#43336415　⇨　無事AC。はぁ

教訓

下手な方針を立てると実装が訳分からんくなってバグりやすくなる
- 16とか17とかの固定値なんやねん。。
やむを得ず上記で実装する場合には、しっかりコーナーケースまで検証する
- これはどんな問題でも基本的にやるべきだと思いますが、今回のような場合こそ特に、という意味で

解説を見る

こんな問題どうやって解くのんという訳で解説を見ます。

考え方の方向性は図 by kyopro_friendsと大差ないな…
判定にnormalizeを用いる発想は別解 by evimaと一緒だけど、その前にconvertして探索を容易にしたり、全体の実装が段違いに洗練されている…

結局私の実装力不足でした。本当にありがとうございました。

参考というか目標としてevimaさんの別解を以下に引用します。キレイだよなぁ～

def C_editorial(): ''' editorial by evima https://atcoder.jp/contests/abc307/editorial/6650 ''' def convert(H, W, S): s = set() for i in range(H): for j in range(W): if S[i][j] == '#': s.add((i, j)) return s def normalize(s): my = min(y for (y, x) in s) mx = min(x for (y, x) in s) return set((y - my, x - mx) for (y, x) in s) HA, WA = map(int, input().split()) A = normalize(convert(HA, WA, [input() for _ in range(HA)])) HB, WB = map(int, input().split()) B = normalize(convert(HB, WB, [input() for _ in range(HB)])) HX, WX = map(int, input().split()) X = normalize(convert(HX, WX, [input() for _ in range(HX)])) ans = False for dy in range(-HX, HX): for dx in range(-WX, WX): ans |= normalize(A.union((y + dy, x + dx) for (y, x) in B)) == X print('Yes' if ans else 'No')

test_all(C_editorial)

D - Mismatched Parentheses

やってみよう！

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

test_dataD = [ { "in":"""8 a(b(d))c """, "out": """ac """ },{ "in":"""5 a(b)( """, "out": """a( """ },{ "in":"""2 () """, "out": """ """ },{ "in":"""6 )))((( """, "out": """)))((( """ },{# 追加 "in":"""7 a(b)()) """, "out": """a) """ }, ]

def D(): pass test_all(D)

自由欄

振り返り

コンテスト中はC問題で心折れてボロボロでした。。
振り返るとこんな感じ。

Sを走査して対応する(と)を調べる
Sを走査して対応する(と)に挟まれる範囲を除いて出力する

という単純な実装です。

def D(): N = int(input()) S = input() A = [0] * N start = [] for i, c in enumerate(S): if c == "(": start.append(i) elif c == ")" and start: A[start.pop()] = 1 A[i] = -1 flag = 0 ans = [] for c, a in zip(S, A): flag += a if flag == 0 and a != -1: ans.append(c) print(*ans, sep="")

test_all(D)

結果：#43426522

自由欄

E - Distinct Adjacent

test_dataE = [ { "in":"""3 3 """, "out": """6 """ },{ "in":"""4 2 """, "out": """2 """ },{ "in":"""987654 456789 """, "out": """778634319 """ }, ]

やってみよう！

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

def E(): out = "" return out test_all(E)

解説を理解する

はい、早速解説を見ます。
以下、自分なりの理解。

設問では円環ですが、一旦N人の人が一列に並んでいる場合を考えます。
その場合の回答は、$M \times (M - 1) \times (M - 1)... = M(M - 1)^{N - 1}$となります（多分）。

そこから円環の回答を導くためには、N人目が一人目と同じ番号である場合を除けばよいです。
困りました。そんな条件どうやって実装すんだ。という訳でここから解説の本題です。

N人目までの場合の数を数えた後に、その中から一人目と同じ番号かどうかを判断することはできません。
であれば、N人目までの場合の数を数えるプロセスの中で、i人目の番号が一人目と同じ番号かどうかを保持していけばよいです。

具体的には。
i人目までの場合の数を数えた時点で、i人目の番号が一人目と異なる番号の場合を$i_0$、同じ場合を$i_1$とすると、i+1人目は
$(i + 1)_0 = i_0 \times (M - 2) + i_1 \times (M - 1)$
$(i + 1)_1 = i_0$
となります。
よく見ると、結局i+1人目時点での場合の数は$(i_0 + i_1)\times (M - 1)$となり、総数としては一列に並んでいる場合で考えたときと同じになります。
このように、「一人目と同じ番号かどうか」の情報を引き回しながらN人目まで見たときに$N_0$が本問の回答となります。

考えた人頭いいー😇

包除原理については、余力があるときの宿題とします・・・

def E(): N, M = map(int, input().split()) MOD = 998244353 dp = [0, M] for i in range(N - 1): dp = [ (dp[0] * (M - 2) + dp[1] * (M - 1)) % MOD, dp[0] ] print(dp[0])

test_all(E)

結果：#43663626

自由欄

ABC306の振り返り(B, C, D, E)

Arakaki Tokyo — Mon, 17 Jul 2023 11:58:44 GMT

振り返りです。

Toyota Programming Contest 2023#3（AtCoder Beginner Contest 306） - AtCoder

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

AtCoderAtCoder Inc.

import sys from io import StringIO input = lambda: sys.stdin.readline()[:-1] def test(f, data, detail=True): 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 if detail else ''}, output: {ans if detail else ''}") def test_all(f): for i, data in enumerate(eval(f'test_data{f.__name__[0]}'), 1): print(f"case {i}") test(f, data)

B - Base 2

やってみよう！

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

test_dataB = [ { "in":"""1 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 """, "out": """13 """ },{ "in":"""1 0 1 0 1 0 0 0 0 1 0 0 1 1 0 1 1 1 1 0 0 0 1 0 0 1 1 1 1 1 1 0 0 0 0 1 0 1 0 1 0 1 1 1 1 0 0 1 1 0 0 0 0 1 0 1 0 1 0 1 0 0 0 0 """, "out": """766067858140017173 """ }, ]

def B(): pass test_all(B)

自由欄

コンテスト中

2進数から10進数変換。
コンテスト中は素朴にこんな感じ

def B(): (*A,) = map(int, input().split()) ans = 0 base2 = 1 for a in A: ans += a * base2 base2 *= 2 print(ans)

test_all(B)

結果：#42323982

自由欄

振り返り

int()で一発でしたね。。

def B(): print(int(input().replace(" ", "")[::-1], base=2))

test_all(B)

結果：#43665287

自由欄

他の人の提出を見る

わざわざスペースをreplaceする必要もないのか…！

def B(): print(int(input()[::-2], base=2))

test_all(B)

C - Centers

やってみよう！

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

test_dataC = [ { "in":"""3 1 1 3 2 3 2 2 3 1 """, "out": """1 3 2 """ },{ "in":"""1 1 1 1 """, "out": """1 """ },{ "in":"""4 2 3 4 3 4 1 3 1 1 4 2 2 """, "out": """3 4 1 2 """ }, ]

def C(): pass test_all(C)

自由欄

コンテスト中

こんな感じ。
num_idxにインデックスをappendするのは走査順なので、最終的に1~Nのインデックス配列の2つ目の要素が真ん中のインデックスということですね。

def C(): from collections import defaultdict N = int(input()) (*A,) = map(int, input().split()) num_idx = defaultdict(list) for i, a in enumerate(A): num_idx[a].append(i) _, ans = zip(*sorted([[idx[1], n] for n, idx in num_idx.items()])) print(*ans)

test_all(C)

結果：#42335811

自由欄

D - Poisonous Full-Course

やってみよう！

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

test_dataD = [ { "in":"""5 1 100 1 300 0 -200 1 500 1 300 """, "out": """600 """ },{ "in":"""4 0 -1 1 -2 0 -3 1 -4 """, "out": """0 """ },{ "in":"""15 1 900000000 0 600000000 1 -300000000 0 -700000000 1 200000000 1 300000000 0 -600000000 1 -900000000 1 600000000 1 -100000000 1 -400000000 0 900000000 0 200000000 1 -500000000 1 900000000 """, "out": """4100000000 """ }, ]

def D(): pass test_all(D)

自由欄

コンテスト中

こんな感じ。
単純なDPです。

def D(): N = int(input()) XY = [list(map(int, input().split())) for _ in range(N)] # dp[j]: 状態別(j=0: 健康、j=1: 腹壊し)最大値 dp = [0, 0] for x, y in XY: if x == 0: dp[0] = max(dp[0], dp[0] + y, dp[1] + y) else: dp[1] = max(dp[1], dp[0] + y) print(max(dp))

test_all(D)

結果：#42347396

自由欄

E - Best Performances

やってみよう！

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

test_dataE = [ { "in":"""4 2 10 1 5 2 1 3 3 4 2 2 10 1 0 4 0 3 1 2 0 3 0 """, "out": """5 6 8 8 15 13 13 11 1 0 """ },{#test_01 "in":"""1 1 1 1 900924422 """, "out": """900924422 """ }, ]

def E(): pass test_all(E)

自由欄

振り返り

ついでのE問題。
とりあえず愚直に二分探索でソート済み配列を更新するような実装にしてみたら、案の定というかTLEとなりました...(これとかこれとかこれ)
→多分削除は高速でも追加でダメなんだろうなぁ😩

という訳で解説で使われているmultisetのPython代替を調べます。
下記サイトのアイディアを参考にheapq + dictで削除機能付きのheapqラッパー(my_heapq)を作って無事ACとなりました。(存在確認機能の実装は割愛。代わりに降順で値を持てるようにしたよ。)

Pythonでmultisetの代用ができるデータ構造 - Tsuboの競プロブログ

なお代替案としてBITを使う方法もあるようですが、今回は値の範囲が$0 \le Y_i \le 10^9$で先読みもできないので不可となります。

from heapq import * from collections import defaultdict class my_heapq: def __init__(self, a, reverse=False): self.reverse = reverse if reverse: a = [-v for v in a] self.a = a heapify(self.a) self.rm_list = defaultdict(int) def heappush(self, item): if self.reverse: item *= -1 heappush(self.a, item) def heappop(self): x = heappop(self.a) while self.rm_list[x]: self.rm_list[x] -= 1 x = heappop(self.a) if self.reverse: x *= -1 return x def heappushpop(self, item): if self.reverse: return -heappushpop(self.a, -item) else: return heappushpop(self.a, item) def rm(self, item): if self.reverse: item *= -1 self.rm_list[item] += 1 def get_first(self): while self.rm_list[self.a[0]]: self.rm_list[self.a[0]] -= 1 heappop(self.a) if self.reverse: return -self.a[0] else: return self.a[0]

def E(): N, K, Q = map(int, input().split()) A = [0] * (N + 1) top_k = my_heapq([0] * K) # 通常heap: 先頭が最小 others = my_heapq([0] * (N - K), reverse=True) # 降順heap: 先頭が最大 ans = 0 if N == K: for _ in range(Q): x, y = map(int, input().split()) now = A[x] ans -= now ans += y A[x] = y print(ans) return for _ in range(Q): x, y = map(int, input().split()) now = A[x] A[x] = y if now >= top_k.get_first(): top_k.rm(now) if y >= others.get_first(): # top_kにいて、残る ans -= now ans += y top_k.heappush(y) else: # top_kにいて、外れる ans -= now new = others.heappop() ans += new top_k.heappush(new) others.heappush(y) else: others.rm(now) if y > top_k.get_first(): # top_kにおらず、入る old = top_k.heappop() ans -= old others.heappush(old) ans += y top_k.heappush(y) else: # top_kにおらず、入らない others.heappush(y) print(ans)

test_all(E)

結果：#43688460

自由欄

ABC302の振り返り

Arakaki Tokyo — Sun, 02 Jul 2023 14:21:06 GMT

振り返りです。

TOYOTA MOTOR CORPORATION Programming Contest 2023#2 (AtCoder Beginner Contest 302) - AtCoder

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

AtCoderAtCoder Inc.

A - Attack

やってみよう！

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

test_dataA = [ { "in":"""7 3 """, "out": """3 """ },{ "in":"""123456789123456789 987654321 """, "out": """124999999 """ },{ "in":"""999999999999999998 2 """, "out": """499999999999999999 """ }, ]

def A(): pass test_all(A)

自由欄

コンテスト中

「Bで割って少数点以下は切り上げたらええやん！楽勝～」と思って実装したら3つ目のテストケースでびっくりしました。確認大事。

import math

A, B = map(int, test_dataA[-1]["in"].split()) math.ceil(A/B)

そもそも$\frac{A}{B}$の時点で・・・

print(f"{A/B:f}")

という訳で、場当たり的にdecimalモジュールを使ってAC.
こんな感じ。

def A(): import math from decimal import Decimal A, B = map(int, input().split()) print(math.ceil(Decimal(A)/B))

test_all(A)

結果：#41544181

自由欄

解説を理解する

解説曰く、「$\frac{A}{B}$の切り上げは、$\frac{A + B - 1}{B}$の切り捨てと等しい」とのこと。
以下確認してみます。

整数$x, y$を用いて以下のような整数$a, b$について考えます。
$a = bx + y\:(0 \le y \lt b)$

ここで、$\frac{a}{b}$の切り上げは以下のようになります。

$$ \left\lceil \frac{a}{b} \right\rceil = \begin{cases} x & (y= 0)\\ x + 1 & (y > 0) \end{cases} $$

解説の式を見ていくと、

$$ \begin{align} & \left\lfloor \frac{a + b - 1}{b} \right\rfloor \\ = \:\:& \left\lfloor \frac{(x + 1)b + y - 1}{b} \right\rfloor \\ = \:\:& x + \left\lfloor 1 + \frac{y - 1}{b} \right\rfloor \\ \end{align} $$

$y < b$なので$\frac{y - 1}{b}$の取りうる範囲は

$$ \begin{cases} -1 \le \frac{y - 1}{b} < 0 & (y= 0)\\ 0 \le \frac{y - 1}{b} < 1 & (y > 0) \end{cases} $$

なので、

$$\left\lfloor 1 + \frac{y - 1}{b} \right\rfloor = \begin{cases} 0 & (y= 0)\\ 1 & (y > 0) \end{cases} $$

となり、結果として

$$ \left\lceil \frac{a}{b} \right\rceil = \left\lfloor \frac{a + b - 1}{b} \right\rfloor $$

が成り立つという訳ですね。
天才かよ。

Pythonのint型とfloat型の精度

ABC262のA問題でも取り上げましたが、Pythonのint型に精度の制限はありません。対してfloat型は大体倍精度浮動小数点です。
参照）組み込み型 — Python 3.11.4 ドキュメント

私の最初の考えのように「小数点以下を切り上げ」しようとすると倍精度浮動小数点での演算になってしまい、３つ目のテストケースでは表現可能な範囲を超えてしまいます。
倍精度浮動小数点で表現できる整数はせいぜい15桁までです。（参照：sys.float_info.dig）

import sys # 浮動小数点数で正確に表示できる最大の10進数桁 sys.float_info.dig

一方int型の除算であれば、精度の制限なく、かつデフォルトで切り捨ての挙動となるので、解説のような式に変換することで解が得られるという訳なんですね。

A問題、勉強になるなぁ～

B - Find snuke

略

深さ優先探索っぽく再帰関数で実装。
コンテスト中：#41558048
振り返り：#43176130

C - Almost Equal

やってみよう！

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

test_dataC = [ { "in":"""4 4 bbed abcd abed fbed """, "out": """Yes """ },{ "in":"""2 5 abcde abced """, "out": """No """ },{ "in":"""8 4 fast face cast race fact rice nice case """, "out": """Yes """ }, ]

def C(): pass test_all(C)

自由欄

コンテスト中

「これは一筆書きの判定なのでは？」と考えてググると「次数が奇数の頂点が0または2であれば一筆書きできる」とのことで実装したらWA...。
おとなしく幅優先探索で実装してACとなりましたが、実はそれも誤りでAfter contestのテストケースでWAとなります…。

まず「一筆書き」についてですが、結論から言えばその判定は本問では当てはまりません。
なぜなら一筆書き判定はすべての辺を通る条件（頂点は何度通っても良い）であるのに対して、本問ではすべての頂点を一度だけ通る条件が必要だからです。
解説 by wasd314によると、そのような路はハミルトン路と言い、「ハミルトングラフかどうかを判定する簡単な定理は見つかっていない」ようです。

安易にそれっぽいアルゴリズムに帰着させてはいけないという、教訓を得ました😇

振り返り

という訳で、幅優先探索を深さ優先探索に書き換えたの以下。(この環境用に若干冗長な記述になってます。)

def C(): from collections import defaultdict from itertools import combinations N, M = map(int, input().split()) S = [input() for _ in range(N)] edge = defaultdict(list) for i, j in combinations(range(N), 2): if sum(1 for c1, c2 in zip(S[i], S[j]) if c1 != c2) == 1: edge[j].append(i) edge[i].append(j) route = [] def search(x): route.append(x) if len(route) == N: print("Yes") return True ret = any(search(nxt) for nxt in edge[x] if nxt not in route) route.pop() return ret for i in range(N): if search(i): break else: print("No")

test_all(C)

結果：#43181323

自由欄

解説を見る

公式解説では愚直な全探索で問題ないと…
「制約が小さければ全探索」は基本でしたね😇

def C(): from itertools import permutations N, M = map(int, input().split()) S = [input() for _ in range(N)] for p in permutations(S): for i in range(1, N): if sum([1 for a, b in zip(p[i], p[i - 1]) if a != b]) != 1: break else: print("Yes") return print("No")

test_all(C)

結果：#43181911

自由欄

D - Impartial Gift

やってみよう！

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

test_dataD = [ { "in":"""2 3 2 3 10 2 5 15 """, "out": """8 """ },{ "in":"""3 3 0 1 3 3 6 2 7 """, "out": """-1 """ },{ "in":"""1 1 1000000000000000000 1000000000000000000 1000000000000000000 """, "out": """2000000000000000000 """ },{ "in":"""8 6 1 2 5 6 5 2 1 7 9 7 2 5 5 2 4 """, "out": """14 """ }, ]

def D(): pass test_all(D)

自由欄

コンテスト中

単純な貪欲法で「贈り物の価値の和」が大きいパターンから見ていき、価値の差がD以下であれば回答します。

def D(): N, M, D = map(int, input().split()) (*A,) = sorted(map(int, input().split())) (*B,) = sorted(map(int, input().split())) n = N - 1 m = M - 1 while n >= 0 and m >= 0: if abs(A[n] - B[m]) <= d: print(a[n] + b[m]) return elif a[n]> B[m]: n -= 1 else: m -= 1 print(-1)

test_all(D)

結果：#41577462

自由欄

E - Isolation

やってみよう！

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

test_dataE = [ { "in":"""3 7 1 1 2 1 1 3 1 2 3 2 1 1 1 2 2 2 1 1 2 """, "out": """1 0 0 1 0 3 1 """ },{ "in":"""2 1 2 1 """, "out": """2 """ }, ]

def E(): pass test_all(E)

自由欄

try

せっかくなのでE問題もやってみます。
と言いつつ力尽きたので早速解説を見ます。どうせ俺がまだ知らないアルゴリズムとか使ってんだろ！

と思いきや、意外にも素直な考え方でイケるっぽい？
という訳で解説の文章だけカンニングして実装してみたのが以下。

def E(): from collections import defaultdict N, Q = map(int, input().split()) edge = defaultdict(set) ans = N for _ in range(Q): type, *args = map(int, input().split()) if type == 1: u, v = args for x in [u, v]: if not edge[x]: ans -= 1 edge[u].add(v) edge[v].add(u) print(ans) else: v = args[0] for x in edge[v]: edge[x].remove(v) if not edge[x]: ans += 1 if edge[v]: edge[v] = set() ans += 1 print(ans)

test_all(E)

結果：#43200104

ちなみにPythonでの提出ではTLEとなってしまいます。
やっぱデフォルトPyPyのほうがいいな。

自由欄

ABC301の振り返り

Arakaki Tokyo — Sun, 25 Jun 2023 08:34:30 GMT

振り返りです。

B - Fill the Gaps

やってみよう！

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

test_dataB = [ { "in":"""4 2 5 1 2 """, "out": """2 3 4 5 4 3 2 1 2 """ },{ "in":"""6 3 4 5 6 5 4 """, "out": """3 4 5 6 5 4 """ }, ]

def B(): pass test_all(B)

自由欄

コンテスト中

こんな感じ。

def B(): N = int(input()) (*A,) = map(int, input().split()) print(A[0], end=" ") for i, a in enumerate(A[1:]): if abs(a - A[i]) > 1: if a > A[i]: print(*range(A[i] + 1, a), end=" ") else: print(*range(A[i] - 1, a, -1), end=" ") print(a, end=" ")

test_all(B) # 末尾の無駄なスペースがある & 改行がないのでここではWAですがAtcoder上ではAC判定になります

結果：#41357753

自由欄

振り返り

こんな感じ。
Booleanでうまいこと±1だけとれないかなぁとやってみた。

def B(): N = int(input()) (*A,) = map(int, input().split()) now = A[0] print(now, end="") for a in A[1:]: while now != a: now += (a > now) * 2 - 1 print("", now, end="") print()

test_all(B)

結果：#42306898

自由欄

C - AtCoder Cards

やってみよう！

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

test_dataC = [ { "in":"""ch@ku@ai choku@@i """, "out": """Yes """ },{ "in":"""ch@kud@i akidu@ho """, "out": """Yes """ },{ "in":"""aoki @ok@ """, "out": """No """ },{ "in":"""aa bb """, "out": """No """ }, ]

def C(): pass test_all(C)

自由欄

振り返り

結果、コンテスト中のAC提出とほとんど同じ(ちょっとスッキリ)になりました。

def C(): from collections import defaultdict from string import ascii_lowercase as abc S = input() T = input() s_chars = defaultdict(int) t_chars = defaultdict(int) for s, t in zip(S, T): s_chars[s] += 1 t_chars[t] += 1 for char in abc: s = s_chars[char] t = t_chars[char] if char in "atcoder": if s > t: t_chars["@"] -= s - t elif t > s: s_chars["@"] -= t - s else: if s != t: print("No") return print("Yes" if t_chars["@"] >= 0 and s_chars["@"] >= 0 else "No")

test_all(C)

結果：#42307631

自由欄

D - Bitmask

やってみよう！

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

test_dataD = [ { "in":"""?0? 2 """, "out": """1 """ },{ "in":"""101 4 """, "out": """-1 """ },{ "in":"""?0? 1000000000000000000 """, "out": """5 """ }, ]

def D(): pass test_all(D)

自由欄

振り返り

コンテスト中は「よく分かんねぇ～」と思ってソッコーで諦めましたが、今振り返ってみるとフツーに解けました。
前々回ぐらいから、惰性で参加してたのがよく分かる・・・😇

def D(): S = input()[::-1] N = int(input()) ex2 = {0: 1} now = 0 for i in range(len(S)): if S[i] == "1": now += ex2[i] ex2[i + 1] = ex2[i] * 2 if now > N: print(-1) return elif now == N: print(N) return for i in range(len(S) - 1, -1, -1): if S[i] == "?" and ex2[i] + now <= n: now +="ex2[i]" print(now) < py-cell> test_all(D)

結果：

自由欄

E - Pac-Takahashi

さっそく解説を見ます。
巡回セールスマン問題。。「アルゴリズム」の話題でよく出てくるので名前だけは知ってますが、急に実装しろとなると困る😫

という訳でもっと元気なときの宿題とします。

自由欄

ABC300の振り返り

Arakaki Tokyo — Sun, 25 Jun 2023 06:48:27 GMT

振り返りです。

UNIQUE VISION Programming Contest 2023 Spring(AtCoder Beginner Contest 300) - AtCoder

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

AtCoderAtCoder Inc.

C - Cross

やってみよう！

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

test_dataC = [ { "in":"""5 9 #.#.#...# .#...#.#. #.#...#.. .....#.#. ....#...# """, "out": """1 1 0 0 0 """ },{ "in":"""3 3 ... ... ... """, "out": """0 0 0 """ },{ "in":"""3 16 #.#.....#.#..#.# .#.......#....#. #.#.....#.#..#.# """, "out": """3 0 0 """ },{ "in":"""15 20 #.#..#.............# .#....#....#.#....#. #.#....#....#....#.. ........#..#.#..#... #.....#..#.....#.... .#...#....#...#..#.# ..#.#......#.#....#. ...#........#....#.# ..#.#......#.#...... .#...#....#...#..... #.....#..#.....#.... ........#.......#... #.#....#....#.#..#.. .#....#......#....#. #.#..#......#.#....# """, "out": """5 0 1 0 0 0 1 0 0 0 0 0 0 0 0 """ }, ]

def C(): pass test_all(C)

自由欄

コンテスト中にやりたかったこと

「１行目から見て行って、✕があれば数えながら消していけばいんじゃね？」という単純な考えのもと実装していったのはいいものの、結局うまく落とし込めずWA x 3の末にタイムアップとなった回でした・・・

振り返ってみると、✕の中の✕を考慮できてなかっただけのアホでした。
という訳で、やりたかったのは以下みたいな感じ。

def C(): from collections import defaultdict H, W = map(int, input().split()) C = [list(input()) for _ in range(H)] ans = defaultdict(int) for h in range(H): left_top = [] for w in range(W): if C[h][w] == "#": if w < W - 1 and C[h + 1][w + 1] == "#": left_top.append(w) else: lt = left_top.pop() n = (w - lt) // 2 ans[n] += 1 size = n * 2 + 1 for i in range(size): C[h + i][lt + i] = "." C[h + i][w - i] = "." print(*[ans[n] for n in range(1, min(H, W) + 1)])

test_all(C)

結果：#42736227

自由欄

振り返り

BFSでやるとこんな感じ。
解説 by evimaではDFSでスッキリ書けてて負けた感がすごい😇

def C(): from collections import defaultdict, deque from itertools import product H, W = map(int, input().split()) C = [input() for _ in range(H)] ans = defaultdict(int) seen = set() for h, w in product(range(H), range(W)): if (h, w) in seen: continue seen.add((h, w)) if C[h][w] == ".": continue q = deque([(h, w)]) n = 0 while q: h, w = q.popleft() n += 1 for i, x in [(h + a, w + b) for a, b in product([1, -1], repeat=2)]: if 0 <= 0 1 i <="H" - and (i, x) not in seen: seen.add((i, x)) if c[i][x]="=" "#": q.append((i, ans[(n 1) 4] +="1" print(*[ans[i] for range(1, min(h, w) 1)])< py-cell> test_all(C)

結果：#42716480

自由欄

D - AABCC

やってみよう！

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

test_dataD = [ { "in":"""1000 """, "out": """3 """ },{ "in":"""1000000000000 """, "out": """2817785 """ }, ]

def D(): pass

test_all(D)

自由欄

try

せっかくなのでやってみます。
枝刈り大事。

def D(): from bisect import bisect_left N = int(input()) f_max = int((N / 12) ** (1/2)) + 1 seed = [1] * (f_max + 1) for i in range(3, f_max + 1, 2): if not seed[i]: continue for j in range(i * 2, f_max + 1, i): seed[j] = 0 facs = [2] for i in range(3, f_max + 1, 2): if seed[i]: facs.append(i) ans = 0 for i in range(len(facs) - 2): if facs[i] ** 2 * facs[i + 1] * facs[i + 2] ** 2 > N: break for j in range(i + 1, len(facs) - 1): a2b = facs[i] ** 2 * facs[j] idx = bisect_left(facs, (N / a2b) ** (1/2)) if idx <= j: break elif idx>= len(facs): ans += len(facs) - 1 - j elif a2b * facs[idx] ** 2 == N: ans += idx - j else: ans += idx - j - 1 print(ans)

test_all(D)

結果：#42888284

自由欄

E - Dice Product 3

やってみよう！

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

test_dataE = [ { "in":"""6 """, "out": """239578645 """ },{ "in":"""7 """, "out": """0 """ },{ "in":"""300 """, "out": """183676961 """ },{ "in":"""979552051200000000 """, "out": """812376310 """ }, ]

def E(): pass test_all(E)

自由欄

try

せっかくなのでやってみます。

一旦MODのことは忘れて例題1を手計算してみます。

(6) : $\frac{1}{6}$
(2, 3), (3, 2) : $\frac{1}{18}$

さらに以下のパターンでは等比級数になるので、

(2, 1, 3), (2, 1, 1, 3)... : $\frac{1}{18} \times (\frac{1}{6} + \frac{1}{6 ^ 2} + \frac{1}{6 ^ 3} + ... + \frac{1}{6 ^ \infty}) = \frac{1}{18} \times \frac{1}{5}$

合計$\frac{7}{30}$になります。
加えて、最初に1が1回以上連続して上のパターンを辿る確率も同様に等比級数になるので、結果として $$ \big(1 + \frac{1}{5}\big) \times \frac{7}{30} = \frac{7}{25} $$

になるという訳ですね。
はい、そもそも確率だすのがムズい。

この手計算の段階でだいぶ時間掛かってんのに、実装に落とし込むってなったらどないせいっちゅうねん😡
という訳で解説をみます。曰く、

dp(n) : (持っている数がnである状態からスタートしたときに, 最終的に持っている数がNに一致する確率)と定義すると、答えはdp(1)

そしてdp(n)は以下のようになるとのこと。

$$ \begin{align} & DP(n) = \frac{1}{6}\big(DP(n) + DP(2n) + DP(3n) + DP(4n) + DP(5n) + DP(6n)\big)\\ \Leftrightarrow \:& \frac{5}{6}DP(n) = \frac{1}{6}\big(DP(2n) + DP(3n) + DP(4n) + DP(5n) + DP(6n)\big)\\ \Leftrightarrow \:& DP(n) = \frac{1}{5}\big(DP(2n) + DP(3n) + DP(4n) + DP(5n) + DP(6n)\big)\\ \end{align} $$

あれ、手計算で手こずった1が出る場合のパターンがキレイに消えとる…
そしてめっちゃ簡単そうな再帰呼び出しになりました。実装するとこんな感じ。
ちなみに期待値のMODについてはABC280のE問題でばっちり理解した通りpow関数で一発です(理解したとは言ってない)✌

def E(): from functools import lru_cache MOD = 998244353 N = int(input()) @lru_cache(None) def dp(n): if n > N: return 0 elif n == N: return 1 else: return sum(dp(i * n) for i in range(2, 7)) * pow(5, -1, MOD) % MOD print(dp(1))

test(E, test_dataE[0])

test_all(E)

結果：#42947625

自由欄

ABC299の振り返り

Arakaki Tokyo — Sat, 10 Jun 2023 10:55:32 GMT

振り返りです。

Tokio Marine & Nichido Fire Insurance Programming Contest 2023（AtCoder Beginner Contest 299) - AtCoder

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

AtCoderAtCoder Inc.

A - Treasure Chest

やってみよう！

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

test_dataA = [ { "in":"""10 .|..*...|. """, "out": """in """ },{ "in":"""10 .|..|.*... """, "out": """out """ },{ "in":"""3 |*| """, "out": """in """ }, ]

def A(): pass test_all(A)

自由欄

コンテスト中

正規表現殺しを意図したであろう設問ですが、細々確認する時間が惜しいのでこんな感じです。

def A(): input() S = input() a, b = [i for i, c in enumerate(S) if c == "|"] c = S.index("*") if a < c < b: print("in") else: print("out")

test_all(A)

結果：#40832394

振り返り

正規表現の練習。たまに触れないと忘れちゃいますね😩
正規表現構文もそうだし、reモジュールのsearch()とmatch()の違いとか。

def A(): import re input() print("in" if re.search(r"\|.*\*.*\|", input()) else "out")

test_all(A)

結果：#41929387

自由欄

B - Trick Taking

略

関係ないですけど、１ヶ月以上空けて振り返って新鮮な気持ちで書いたコードが、当時のコンテスト中の提出と全く同じで、なんだか複雑な気持ちになりました。。 (成長してないと見るべきか、この問題に必要な知識は定着していて都度引き出し可能と見るべきか🤔)

C - Dango

やってみよう！

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

test_dataC = [ { "in":"""10 o-oooo---o """, "out": """4 """ },{ "in":"""1 - """, "out": """-1 """ },{ "in":"""30 -o-o-oooo-oo-o-ooooooo--oooo-o """, "out": """7 """ },{ "in":"""5 oooo- """, "out": """4 """ },{ "in":"""5 ----- """, "out": """-1 """ },{ "in":"""2 -o """, "out": """1 """ }, ]

def C(): pass test_all(C)

自由欄

コンテスト中

コンテスト中の提出がこんな感じ。

連続したoの最大値を求める
回答
- -が含まれない(=ans: -1)：-1
- oが含まれない(=ans: 0)：-1
- 上記以外：ans

ここらへんの考え方をキレイに実装に落とし込めず、WA x 2となりました・・・(⬇のACコードも場当たり的に修正して分かりづらい😇)

def C(): N = int(input()) S = input() ans = -1 now = 0 for c in S: if c == "o": now += 1 else: ans = max(ans, now) now = 0 if ans != -1: ans = max(ans, now) print(ans if ans != 0 else -1)

test_all(C)

結果：#41999202

自由欄

振り返り：reモジュールを使う

A問題の振り返りでreモジュールを使ったのでここでも使ってみます。
⇛re.findall(pattern, string, flags=0)

考え方は同じで、

連続するoの個数の最大値が1以上かつ-を含む：連続するoの個数の最大値
上記以外：-1

まぁまぁスッキリ書けました。
が、実は記憶ゼロで振り返ってやってみた時も大分ハマりました・・・。2ヶ月弱サボるとこの体たらく。。精進します！

def C(): import re N = int(input()) S = input() max_len = max(len(m) for m in [""] + re.findall("o+", S)) if max_len > 0 and "-" in S: print(max_len) else: print(-1)

test_all(C)

結果：#42114972

自由欄

解説を見る

解説を見ます。
あ、split・・・。その手があったか😭

あと「特定の文字を含む」はsetで一発判定できますね。

def C(): input() S = input() print(max(map(len, S.split("-"))) if set('o-') == set(S) else "-1")

test_all(C)

結果：#42115796

自由欄

D - Find by Query

略

結論から言うと二分探索なのですが、コンテスト中は「同じ文字が連続してない！にぶたん使えない！分からん寝る！」とあっさり諦めてしまいました。
そこでもうちょい粘って「二分探索に当てはめてみるとどうなるか」を考えてみれば、同じ文字が連続してなくとも適用できることに気づけたはず。

やるからには心身ともに万全のコンディションで臨むべきなのですが、最近は忙しさにかまけてセルフマネジメントができておらず、奇しくもAtcoderでそれば顕在化されてしまいました。
まずは生活リズムを整えるということと、ルーティンの有用性(毎週土曜のAtcoderの結果、というよりいかにして問題を解けたかor解けなかったかでコンディションが分かる)を再認識です。

と言いつつ、直近ではそのルーティンすらこなせてないのが問題です・・・

自由欄

ABC298の振り返り(B, C, D)

Arakaki Tokyo — Sun, 23 Apr 2023 08:17:55 GMT

振り返りです。

TOYOTA MOTOR CORPORATION Programming Contest 2023#1 (AtCoder Beginner Contest 298) - AtCoder

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

AtCoderAtCoder Inc.

B - Coloring Matrix

やってみよう！

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

test_dataB = [ { "in":"""3 0 1 1 1 0 0 0 1 0 1 1 0 0 0 1 1 1 1 """, "out": """Yes """ },{ "in":"""2 0 0 0 0 1 1 1 1 """, "out": """Yes """ },{ "in":"""5 0 0 1 1 0 1 0 0 1 0 0 0 1 0 1 0 1 0 1 0 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 0 0 1 1 1 1 0 1 0 1 1 1 0 1 0 """, "out": """No """ }, ]

def B(): pass test_all(B)

自由欄

振り返り

コンテスト中は設問通りに実装しましたが、『回転』という処理で言えばnumpyにそのものズバリの関数があったなぁと振り返って気づきました。
A, Bの取りうる値は0, 1なので判定もカンタンですね。

def B(): import numpy as np N = int(input()) A = np.array([list(map(int, input().split())) for _ in range(N)]) B = np.array([list(map(int, input().split())) for _ in range(N)]) for _ in range(4): if np.all(B-A>-1): print("Yes") break A = np.rot90(A) else: print("No")

test_all(B)

結果：#40824816

自由欄

線形代数(？)っぽく解く

文系出身なのでここらへんコンプレックスなのですが、サクッと行列の演算で処理できたらカッコいいですよね！
…考えても全然分からんのでググって以下参考にしました😇

matrices - How to rotate the positions of a matrix by 90 degrees - Mathematics Stack Exchange

転置して行を逆順にすれば90度回転になるのか。なんかあんまり行列の演算っぽくはないですね😩

import numpy as np def B(): N = int(input()) A = np.array([list(map(int, input().split())) for _ in range(N)]) B = np.array([list(map(int, input().split())) for _ in range(N)]) for _ in range(4): if np.all(B-A>-1): print("Yes") break A = A.T[::-1] else: print("No")

test_all(B)

結果：#40895995

自由欄

解説を見る

ユーザ解説で紹介されている通り、「転置して行を逆順にする」なら生のPythonでも短く書けます。

A = np.arange(9).reshape(3, -1) print(A)

print(np.array([a[::-1] for a in zip(*A)]))

C - Cards Query Problem

やってみよう！

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

test_dataC = [ { "in":"""5 8 1 1 1 1 2 4 1 1 4 2 4 1 1 4 2 4 3 1 3 2 """, "out": """1 2 1 1 2 1 4 4 """ },{ "in":"""1 5 1 1 1 1 2 1 1 200000 1 2 1 3 200000 """, "out": """1 2 200000 1 """ }, ]

def C(): pass test_all(C)

自由欄

コンテスト中

競プロ初めてもうすぐ1年になりますが、相変わらずアホみたいなミスと言うか、自分で「なんで！？」と突っ込みたくなるようなコーディングしてハマってしまってます…
本問もWA, TLEで終わってしまったのですが、とりあえずコンテスト中に提出した中で一番ましなのが以下。

def C(): from collections import defaultdict from bisect import bisect N = int(input()) Q = int(input()) box = defaultdict(list) card = defaultdict(list) for _ in range(Q): idx, *args = input().split() if idx == "1": i, j = args box[j].append(i) card[i].append(j) #print(box) #print(card) elif idx == "2": print(*sorted(box[args[0]])) elif idx == "3": print(*sorted(set(card[args[0]])))

test_all(C)

結果：#40660450

自由欄

振り返り

まずアホみたいなところから修正しましょう。
上コードでは11行目のidx, *args = input().split()です。

なんで文字列のまま受け取ってんねん！！！！！！

箱の数、カードの数ともに$\le 2 \times 10^5$なので文字列のまま大小比較できるわけがありません。
なんで今更こんなミスするかな…

もう一つ、3番目のクエリにおいてカードが入っている箱は重複を除いて出力するので、情報として保持する時点でユニークにしておけばいいです。(9行目)

以上2つを修正したのが以下。

def C(): from collections import defaultdict N = int(input()) Q = int(input()) box = defaultdict(list) card = defaultdict(set) for _ in range(Q): idx, *args = map(int, input().split()) if idx == 1: i, j = args box[j].append(i) card[i].add(j) elif idx == 2: print(*sorted(box[args[0]])) elif idx == 3: print(*sorted(card[args[0]]))

test_all(C)

結果：#40825330

無事AC…はぁ😩

自由欄

D - Writing a Numeral D - Writing a Numeral

やってみよう！

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

test_dataD = [ { "in":"""3 3 1 2 3 """, "out": """1 12 """ },{ "in":"""3 1 5 2 3 """, "out": """5 """ },{ "in":"""11 1 9 1 9 1 8 1 2 1 4 1 4 1 3 1 5 1 3 2 3 """, "out": """0 """ }, ]

def D(): pass test_all(D)

自由欄

振り返り

これは純粋に実力不足。コンテスト中の愚直解は当然TLE(& RE)となったので解説を見てやり直したのが以下。

def D(): from collections import deque M = 998244353 Q = int(input()) S = deque("1") ans = 1 for _ in range(Q): idx, *args = input().split() if idx == "1": ans = ans * 10 + int(args[0]) ans %= M S.append(args[0]) elif idx == "2": sub = int(S.popleft()) * pow(10, len(S), M) ans -= sub ans %= M else: print(ans)

test_all(D)

結果：#40826483

自由欄

ABC297の振り返り(Eとダイクストラ法)

Arakaki Tokyo — Sat, 22 Apr 2023 08:14:51 GMT

振り返りです。

AtCoder Beginner Contest 297 - AtCoder

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

AtCoderAtCoder Inc.

E - Kth Takoyaki Set

やってみよう！

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

test_dataE = [ { "in":"""4 6 20 25 30 100 """, "out": """50 """ },{ "in":"""2 10 2 1 """, "out": """10 """ },{ "in":"""10 200000 955277671 764071525 871653439 819642859 703677532 515827892 127889502 881462887 330802980 503797872 """, "out": """5705443819 """ }, ]

def E(): pass test_all(E)

自由欄

振り返り

コンテスト中はDPかなぁ～と考えたりしたのですが、うまいこと解法が思いつかず試合終了。

という訳で解説を見ますが、「探索方法」を一読してもよく理解できません😇
ただ、最後に言及されている「上記の探索方法はダイクストラ法に酷似」という部分から、ダイクストラ法ってどんなんだっけな～と実装したのが以下。

heapqモジュールでたこ焼きの組み合わせによる支払い金額を昇順に探索しています。

def E(): import heapq as hq N, K = map(int, input().split()) *A, = map(int, input().split()) price = 0 q = A.copy(); hq.heapify(q) while K: now = hq.heappop(q) if not now > price: continue price = now for a in A: hq.heappush(q, now + a) K -= 1 print(price) test_all(E)

結果：#40630180

ACしてしまった…
こんなシンプルに解けたとなると、どこか穴がないか不安になります…

自由欄

ダイクストラ法

これまで名前は見てきたものの、ずっと後回しにしていたダイクストラ法をしっかり理解してみます。
(初見は約9ヶ月前のABC257の振り返りでした。大分寝かせてたな…)

AtCoderではABC035のD - トレジャーハントが有名なようです。

参照）AtCoderでダイクストラ法を使う最初に出た問題！？AtCoder Beginner Contest 035 [D - トレジャーハント]をScipyのdijkstraで解く（正解率21.51%） - 人工知能と競プロやってくブログ

ロジックの考え方は以下の動画を参考にしました。(こちらもよく紹介されていたので有名？)
グラフ理論⑤(ダイクストラのアルゴリズム) - YouTube

という訳で以下、解説ありきで実装してみます。

test_dataABC035D = [ { "in":"""2 2 5 1 3 1 2 2 2 1 1 """, "out": """6 """ },{ "in":"""2 2 3 1 3 1 2 2 2 1 1 """, "out": """3 """ },{ "in":"""8 15 120 1 2 6 16 1 3 11 9 1 8 1 7 3 14 8 2 13 3 5 4 5 7 5 6 4 1 6 8 17 7 8 5 1 4 2 4 7 1 6 1 3 3 1 10 2 6 5 2 4 12 5 1 30 """, "out": """1488 """ }, ]

def ABC035D(): from collections import defaultdict import heapq as hq N, M, T = map(int, input().split()) *A, = map(int, input().split()) edge = defaultdict(list) edge_rev= defaultdict(list) for _ in range(M): a, b, c = map(int, input().split()) edge[a].append((b, c)) edge_rev[b].append((a, c)) def dijkstra(n, e, start, goal=None): # cost = defaultdict(lambda: float("inf"), {start: 0}) # 1-indexed cost = [float('inf')] * (n + 1); cost[start] = 0 q = [(cost[start], start)] fixed = set() while q: _, now = hq.heappop(q) if now in fixed: continue fixed.add(now) if goal and now == goal: break for nxt, c in e[now]: if nxt in fixed: continue cost[nxt] = min(cost[nxt], cost[now] + c) hq.heappush(q, (cost[nxt], nxt)) return cost print(max([ A[i] * (T - (a + b)) for i, (a, b) in enumerate(zip( dijkstra(N, edge, 1)[1:], dijkstra(N, edge_rev, 1)[1:] )) if a + b < T ]))

for data in test_dataABC035D: test(ABC035D, data)

結果：#40698295

なんとなくダイクストラ法理解できました😊
ただ、これを知っていたからと言って今回のE問題が解けたかどうか…

まぁ武器が一つ増えたということで、よし！

自由欄

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

Arakaki Tokyo — Sat, 08 Apr 2023 10:52:09 GMT

振り返りです。

AtCoder Beginner Contest 296 - AtCoder

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

AtCoderAtCoder Inc.

A - Alternately

やってみよう！

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

test_dataA = [ { "in":"""6 MFMFMF """, "out": """Yes """ },{ "in":"""9 FMFMMFMFM """, "out": """No """ },{ "in":"""1 F """, "out": """Yes """ }, ]

def A(): pass test_all(A)

自由欄

コンテスト中

N=1のケースを見をとしてWAした後の提出がこんな感じ。

def A(): N = int(input()) S = input() if N == 1: print("Yes") else: print("Yes" if len(set(S[0::2])) == 1 and len(set(S[1::2])) == 1 else "No")

test_all(A)

結果：#40210441

自由欄

振り返り

振り返って考えると、上の提出だと以下のケースのように1種類の文字だけの場合でWAになりますね…

制約の「$S$はMおよびFのみからなる長さ$N$の文字列」だけを読むと「必ずMおよびFが含まれる」かのように思われますが、それだとN=1のケースが矛盾します。
したがってSがMのみ、またはFのみの場合にも対応できる必要があります。

wa_case = {"in": '''3\nFFF\n''', "out": '''No\n'''}

test(A, wa_case)

という訳で修正したのが以下。

def A2(): N = int(input()) S = input() if N == 1: print("Yes") else: print( "Yes" if len(set(S[0::2])) == 1 and len(set(S[1::2])) == 1 and len(set(S[:2])) == 2 else "No" )

test(A2, wa_case)

test_all(A2)

結果：#40401849

ロジックより3項演算子の改行が気持ち悪い…
素直に解説のような線形探索したほうがよさそうです😇

自由欄

B - Chessboard

略

C - Gap Existence

略

D - M<=ab

やってみよう！

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

test_dataD = [ { "in":"""5 7 """, "out": """8 """ },{ "in":"""2 5 """, "out": """-1 """ },{ "in":"""100000 10000000000 """, "out": """10000000000 """ }, ]

def D(): pass test_all(D)

自由欄

コンテスト中

コンテスト中は21:11にC問題をACした後、終了時間の22:40までの約90分間に6回提出して全て駄目でした…
その中で一番正解に近そうな(5WA)、5回目の提出が以下。

def D(): import math N, M = map(int, input().split()) if N * N < M: print(-1) # exit() return if M <= n: print(m) # exit() return x="float("inf")" rootm="int(M" ** (1 2)) for a in range(math.ceil(m n), + 1): b, m="divmod(M," a) if 0: * (b 1)) print(x)< py-cell> test_all(D)

結果：#40261549

自由欄

振り返り

他の提出はTLEがあり、つまりロジックが誤っているということです。
それらに比べて上の提出では5つのWAの原因を解消できればACの可能性は高そうです。

という方向で考えてみたのですが、結論として17行目のrangeの終点をrootM + 1からrootM + 2に修正したらACしました。

def D(): import math N, M = map(int, input().split()) if N * N < M: print(-1) # exit() return if M <= n: print(m) # exit() return x="float("inf")" rootm="int(M" ** (1 2)) for a in range(math.ceil(m n), + 2): b, m="divmod(M," a) if 0: * (b 1)) print(x)< py-cell> test_all(D)

結果：#40404533

$a \le b$という条件を仮定したら$a \le \lfloor\sqrt{M}\rfloor$の範囲で探索したらいいんじゃね？という考えだったのですが、答えが$a = b = \lceil\sqrt{M}\rceil$になる可能性もあるので$a \le \lceil\sqrt{M}\rceil$とする必要があったということですね…🤔
ここらへんは解説も参照です。

正直コンテスト中にそこまで厳密に考察できる自信がないですが、$O(\sqrt{M})$の時点でかなり高速なはずなので、探索範囲に余裕を持たせておくというのが実際的な教訓でしょう。

振り返り2

上に気付かず、コンテスト終了6秒前の提出もWAとなってのですが、実はその提出でデバッグ用のprint文を消せばACしていたというね。
これでACできてたらめっちゃスッキリしてただろーなぁ～😩😩😩😩😩😩😩😩😩

def D(): import math N, M = map(int, input().split()) if N * N < M: print(-1) # exit() return if M <= n: print(m) # exit() return x="float("inf")" rootm="int(M" ** (1 2)) for a in range(math.ceil(m n), n + 1): b, m="divmod(M," a) if 0:> (b + 1): break X = min(X, a * (b + 1)) print(X)

test_all(D)

結果：#40404855

これも考え方は同じで、23行目で$a \le b$の条件を明示的に判定するようにしています。
上で「厳密に考察する自信がない」と書いた訳ですが、間接的な判定($a \le \lfloor\sqrt{M}\rfloor$ なのか $a \le \lceil\sqrt{M}\rceil$ なのか)ではなくもっと直接的な判定($a \le b$)を処理に組み込むような実装が最初からできればよかったわけですな。はい。

自由欄

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

Arakaki Tokyo — Sun, 02 Apr 2023 04:32:32 GMT

振り返りです。

AtCoder Beginner Contest 295 - AtCoder

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

AtCoderAtCoder Inc.

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

自由欄

宿題

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

自由欄

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

Arakaki Tokyo — Fri, 31 Mar 2023 13:13:24 GMT

振り返りです。

AtCoder Beginner Contest 294 - AtCoder

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

AtCoderAtCoder Inc.

A - Filter

提出：#39843461

B - ASCII Art

やってみよう！

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

test_dataB = [ { "in":"""2 3 0 1 2 0 0 3 """, "out": """.AB ..C """ },{ "in":"""3 3 24 0 0 0 25 0 0 0 26 """, "out": """X.. .Y. ..Z """ },{ "in":"""3 1 2 9 4 """, "out": """B I D """ },{ "in":"""24 60 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 13 13 14 0 0 0 10 0 0 0 0 0 15 24 14 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 13 23 7 25 24 13 10 0 10 12 0 0 0 0 19 9 23 0 0 0 0 10 10 14 0 0 0 10 14 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 9 13 5 0 0 23 11 14 14 0 0 12 9 1 21 19 0 0 9 12 10 25 3 10 6 0 0 9 13 23 24 14 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 13 14 6 0 0 0 10 5 25 13 0 0 25 0 0 0 0 0 0 0 0 0 0 10 16 0 0 13 21 13 13 14 23 14 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 13 8 2 0 0 0 0 0 13 11 13 19 0 0 1 2 5 9 12 12 5 9 9 20 6 0 14 14 14 9 0 0 0 14 14 18 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 10 23 13 13 13 13 13 13 14 14 14 13 14 14 13 7 0 0 0 0 0 0 0 0 0 0 0 0 13 13 13 2 0 0 0 0 13 11 13 16 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 13 1 0 0 0 9 20 9 20 20 20 20 13 20 20 13 20 23 8 8 8 20 8 20 7 8 17 7 10 13 14 13 19 0 0 0 0 0 22 14 25 13 16 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 13 9 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 20 20 20 13 13 7 20 26 13 8 6 14 0 0 0 0 0 0 0 0 0 0 0 0 0 0 5 0 0 0 0 0 0 0 1 2 20 20 23 13 2 7 2 10 12 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 20 20 23 13 0 0 0 0 0 0 0 0 0 0 0 0 0 13 0 0 0 0 0 0 0 0 1 0 0 0 13 12 9 14 13 13 9 9 20 12 0 0 0 0 0 0 0 0 0 0 0 1 9 9 9 9 12 0 0 0 0 0 0 0 20 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 19 0 0 14 13 14 14 13 13 0 0 9 5 16 0 0 0 0 0 0 5 20 20 13 2 2 20 9 13 14 14 20 12 12 0 0 0 0 9 13 0 0 0 0 0 0 0 0 1 9 0 0 0 0 0 0 0 0 0 0 0 13 10 13 13 13 13 2 5 12 10 5 0 0 0 0 0 0 0 0 20 16 0 0 0 13 14 13 13 13 13 0 0 10 8 0 0 0 0 0 20 7 0 0 0 0 0 0 4 2 0 0 0 0 0 0 0 0 0 0 0 0 9 7 14 10 10 14 13 5 0 0 0 0 0 0 0 0 0 0 0 23 13 12 13 13 13 13 13 9 13 0 14 4 0 0 0 0 0 0 0 9 16 0 0 0 0 0 22 13 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 20 13 13 13 2 9 14 2 20 14 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 5 13 0 0 0 2 7 13 13 13 13 13 13 13 2 9 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 9 20 20 9 0 0 0 0 0 0 0 0 0 0 0 0 0 19 0 0 0 0 0 0 0 20 13 12 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 21 14 7 2 20 24 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 9 6 0 0 0 0 0 0 0 0 0 9 14 14 0 0 20 20 13 13 20 13 9 0 0 10 0 0 0 0 0 0 9 23 13 9 0 0 0 0 0 0 0 10 6 0 0 7 0 0 9 20 13 13 14 2 0 0 0 0 5 0 0 0 0 0 0 0 0 0 0 0 0 20 13 14 0 0 0 0 0 0 0 0 13 9 0 0 0 0 0 0 0 0 13 11 0 0 0 0 0 0 0 14 9 0 0 0 20 25 14 7 0 0 0 0 9 1 14 7 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 9 13 13 20 0 0 0 0 0 9 12 0 0 0 0 0 0 0 14 13 14 0 0 0 0 0 0 0 6 0 0 0 0 0 0 0 0 9 9 20 14 14 4 14 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 20 2 9 0 0 0 0 9 9 20 21 7 13 20 0 0 20 23 7 7 2 12 7 6 0 0 0 0 0 0 0 0 0 0 0 0 5 5 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 20 20 9 9 20 24 10 12 10 0 0 0 0 0 0 0 0 20 20 0 0 0 0 0 20 7 7 13 22 2 5 9 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 9 20 5 20 5 2 5 7 20 5 14 14 5 11 5 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 """, "out": """................................B........................... ...................MMN...J.....OXN.......................... .................MWGYXMJ.JL....SIW....JJN...JN.............. ...............IME..WKNN..LIAUS..ILJYCJF..IMWXN............. ..............MNF...JEYM..Y..........JP..MUMMNWN............ .............MHB.....MKMS..ABEILLEIITF.NNNI...NNR........... ..........JWMMMMMMNNNMNNMG............MMMB....MKMP.......... ........MA...ITITTTTMTTMTWHHHTHTGHQGJMNMS.....VNYMP......... ......MI...............................TTTMMGTZMHFN......... .....E.......ABTTWMBGBJL.......................TTWM......... ....M........A...MLINMMIITL...........AIIIIL.......T........ ...B..........S..NMNNMM..IEP......ETTMBBTIMNNTLL....IM...... ..AI...........MJMMMMBELJE........TP...MNMMMM..JH.....TG.... ..DB............IGNJJNME...........WMLMMMMMIM.ND.......IP... ..VM.................................TMMMBINBTN.........B... ...EM...BGMMMMMMMBI....................ITTI.............S... ....TML..................UNGBTX........................IF... ......INN..TTMMTMI..J......IWMI.......JF..G..ITMMNB....E.... ........TMN........MI........MK.......NI...TYNG....IANG..... ..........IMMT.....IL.......NMN.......F........IITNNDN...... ..............TBI....IITUGMT..TWGGBLGF............EE........ .................TTIITXJLJ........TT.....TGGMVBEIB.......... .........................ITETEBEGTENNEKEB................... ............................................................ """ }, ]

def B(): pass test_all(B)

自由欄

コンテスト中

こんな感じ。

def B(): from string import ascii_uppercase abc = ["."] + list(ascii_uppercase) H, W = map(int, input().split()) A = [list(map(int, input().split())) for _ in range(H)] for i in range(H): print(*[abc[A[i][j]] for j in range(W)], sep="")

test_all(B)

結果：#39851403

自由欄

振り返り

「対応付ける」と言えばmap関数でしょう。(専ら入力を受け取る時に使ってるので本来の用途を忘れがちでした…)

という訳で以下。
コンテスト中よりちょっとすっきり。

def B(): from string import ascii_uppercase as ABC ABC = "." + ABC H, _ = map(int, input().split()) A = [list(map(int, input().split())) for _ in range(H)] for a in A: print(*map(lambda x: ABC[x], a),sep="")

test_all(B)

結果：#40004440

自由欄

C - Merge Sequences

やってみよう！

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

test_dataC = [ { "in":"""4 3 3 14 15 92 6 53 58 """, "out": """1 3 4 7 2 5 6 """ },{ "in":"""4 4 1 2 3 4 100 200 300 400 """, "out": """1 2 3 4 5 6 7 8 """ },{ "in":"""8 12 3 4 10 15 17 18 22 30 5 7 11 13 14 16 19 21 23 24 27 28 """, "out": """1 2 5 9 11 12 15 20 3 4 6 7 8 10 13 14 16 17 18 19 """ }, ]

def C(): pass test_all(C)

自由欄

コンテスト中

こんな感じで、まぁそうだろうなってコードなんですが10分以上掛かってる…
今回のコンテストではE問題まで茶Diffなのでレートアップを狙うには速解きが重要でした。
その意味ではもっとサクッと解けるべき問題だったなぁ😩

def C(): N, M = map(int, input().split()) A = [(x, "A") for x in map(int, input().split())] B = [(x, "B") for x in map(int, input().split())] *C, = enumerate(sorted(A + B), 1) print(*[i for i, (x, AorB) in C if AorB == "A"]) print(*[i for i, (x, AorB) in C if AorB == "B"])

test_all(C)

結果：#39859575

自由欄

振り返り

速解きを意識したらこうなるかな～というのが以下。

def C(): input() *A, = [(a, "A") for a in map(int, input().split())] *B, = [(b, "B") for b in map(int, input().split())] ansA = [] ansB = [] for i, (_, AorB) in enumerate(sorted(A + B), 1): if AorB == "A": ansA.append(i) else: ansB.append(i) print(*ansA) print(*ansB)

test_all(C)

結果：#40005261

自由欄

D - Bank

やってみよう！

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

test_dataD = [ { "in":"""4 10 1 1 3 2 1 1 2 3 3 1 2 2 3 """, "out": """1 2 4 """ } ]

def D(): pass test_all(D)

自由欄

振り返り

設問の理解が不十分で無駄に複雑なコーディングをしてしまった案件です。

とりあえず以下、コンテスト中の提出がインデックスの管理が分かりづらいので微修正したバージョン。
「まだ呼ばれてない人」と「呼ばれて受付に行ってない人」を二分探索のメソッドを追加したBITで管理しています。

class BIT: def __init__(self, a): if hasattr(a, "__iter__"): self.size = len(a) self.data = [0] * self.size self.bit = [0] * (self.size + 1) for i, j in enumerate(a): self.add(i, j) elif isinstance(a, int): self.size = a self.data = [0] * a self.bit = [0] * (a + 1) else: raise TypeError() def add(self, i, x): self.data[i] += x i += 1 while i <= self.size: self.bit[i] +="x" i & -i def sum(self, i): '''get sum of data[:i] ''' total="0" while> 0: total += self.bit[i] i -= i & -i return total def get(self, x): res = 0 i = 1 while i < (self.size + 1) / 2: i <<= 1 while i> 0: if res + i < self.size and self.bit[res + i] < x: x -= self.bit[res + i] res += i i >>= 1 res += 1 return res if res >= x else -1 def __getitem__(self, key): return self.data[key] def __setitem__(self, key, value): self.add(key, value - self[key]) self.data[key] = value def __len__(self): return self.size def __repr__(self): return self.data.__repr__() def __iter__(self): return self.data.__iter__()

def D(): N, Q = map(int, input().split()) no_called = BIT([0] + [1] * N) called_no_gone = BIT(N + 1) for _ in range(Q): # print(no_called.data) # print(called_no_gone.data) ev, *x = input().split() if ev == "1": i = no_called.get(1) - 1 no_called[i] = 0 called_no_gone[i] = 1 elif ev == "2": called_no_gone[int(x[0])] = 0 else: print(called_no_gone.get(1) - 1)

test_all(D)

結果：#40007490

自由欄

解説を見る①

上の提出でACとなったのですが、BITでの管理の考え方だったりインデックスずれのデバッグだったりで時間を費やしてしまいました。
「もっとスマートな方法ないかなぁ」と解説を見て、1つ目の衝撃が以下。

lastを最後に呼ばれた人の番号とする。便宜上はじめlastは0とする。

1 種類目のイベントの場合、次に呼ばれるのはlast + 1である。

という事で、「まだ呼ばれてない人」をBITで管理する必要ねーじゃん！！！！！！！！！！
はい、ちゃんと設問を読んでいれば当たり前のことですね😇

という訳で以下。

def D(): N, Q = map(int, input().split()) call = 1 called_no_gone = BIT(N + 1) for _ in range(Q): ev, *x = input().split() if ev == "1": called_no_gone[call] = 1 call += 1 elif ev == "2": called_no_gone[int(x[0])] = 0 else: print(called_no_gone.get(1) - 1)

test_all(D)

結果：#40007855

実行時間は大差ないですが、考える量は半分にできたと思います。

自由欄

pythonの`set`でイケんじゃね？

さらに解説ではC++の順序付き集合型であるstd::setを使ってます。
pythonのsetは順序を保持しない(ちなみにdictは挿入順を保持する)ので同じようには使えないなぁと思いつつダメ元で試してみたらACしました。

def D(): N, Q = map(int, input().split()) call = 1 called_no_gone = set() for _ in range(Q): ev, *x = input().split() if ev == "1": called_no_gone.add(call) call += 1 elif ev == "2": called_no_gone.remove(int(x[0])) else: print(next(iter(called_no_gone)))

test_all(D)

結果：#40008022

ソース不明ですが、PyPyのset実装では挿入順を保持するっぽいです。
あくまで“挿入順”なのですが、本問ではその挿入順が数字のソート順と同じなのでACしたということなんでしょうね。

実装依存のACなので水物ですが、一応記録として置いておきます。

自由欄

解説を見る②

さらに解説では$O(N + Q)$の解法が紹介されています。
以下写経。

説明を読むと「そりゃそうだ」という内容なのですが、自力でここまで辿り着けるぐらいに読解力を向上させたい…

def D(): N, Q = map(int, input().split()) gone = [False] * (N + 1) ans = 1 for _ in range(Q): ev, *x = input().split() if ev == "1": pass elif ev == "2": gone[int(x[0])] = True else: while gone[ans]: ans += 1 print(ans)

test_all(D)

結果：#40012269

自由欄

E - 2xN Grid

やってみよう！

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

test_dataE = [ { "in":"""8 4 3 1 2 3 2 2 3 3 1 1 4 2 1 3 3 """, "out": """4 """ },{ "in":"""10000000000 1 1 1 10000000000 1 10000000000 """, "out": """10000000000 """ },{ "in":"""1000 4 7 19 79 33 463 19 178 33 280 19 255 33 92 34 25 19 96 12 11 19 490 33 31 """, "out": """380 """ }, ]

def E(): pass test_all(E)

自由欄

コンテスト中

ランレングス圧縮というやつらしいです。
ランレングス圧縮（連長圧縮 / RLE）とは - 意味をわかりやすく - IT用語辞典 e-Words

while文内の19行目で絶対抜けることになるので、whileの条件が実質意味ないあたり、イケてないですね。

def E(): L, N1, N2 = map(int, input().split()) L1 = [list(map(int, input().split())) for _ in range(N1)] L2 = [list(map(int, input().split())) for _ in range(N2)] ans = 0 i1 = 0; i2 = 0; r1 = L1[0][1]; r2 = L2[0][1]; while i1 < N1 and i2 < N2: # print(i1, i2, ans) if L1[i1][0] == L2[i2][0]: ans += min(r1, r2) if r1 == r2: i1 += 1; i2 += 1; if i1 == N1 or i2 == N2: break r1 = L1[i1][1] r2 = L2[i2][1] elif r1 > r2: i2 += 1 r1 -= r2 r2 = L2[i2][1] else: i1 += 1 r2 -= r1 r1 = L1[i1][1] print(ans)

test_all(E)

結果：#39875457

自由欄

解説を見る

公式解説は意味不明なのでスルーして、素朴な実装の解説を見ます。

考え方は自分の提出と同じなのですが、「『共通部分』の長さの出し方」がスマートだし全体的にも短くスッキリまとまってます。
日本語で理解すると：比較対象ブロックを含めた先頭からの長さの短い方 - 比較対象ブロックを除いた先頭からの長さの長い方。
これも、言われると「確かに。。」となる内容なんですが、気付けんなぁ～😩

以下写経。

def E(): L, N, M = map(int, input().split()) A = [list(map(int, input().split())) for i in range(N)] B = [list(map(int, input().split())) for i in range(M)] ans, i, j, p, q = 0, 0, 0, 0, 0 while i < N and j < M: if A[i][0] == B[j][0]: ans += min(p + A[i][1], q + B[j][1]) - max(p, q) if p + A[i][1] < q + B[j][1]: p += A[i][1] i += 1 else: q += B[j][1] j += 1 print(ans)

test_all(E)

自由欄

F - Sugar Water 2

やってみよう！

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

test_dataF = [ { "in":"""3 1 1 1 2 4 1 1 4 1 4 3 3 """, "out": """50.000000000000000 """ },{ "in":"""2 2 2 6 4 10 1 5 8 9 6 """, "out": """62.500000000000000 """ },{ "in":"""4 5 10 5 4 1 6 7 4 9 8 2 2 5 6 6 7 5 3 8 1 """, "out": """54.166666666666664 """ }, ]

def F(): pass test_all(F)

自由欄

コンテスト中

ダメ元で全探索したらやっぱりダメでした。

def F(): from itertools import product N, M, K = map(int, input().split()) AB = [list(map(int, input().split())) for _ in range(N)] CD = [list(map(int, input().split())) for _ in range(M)] c = list() for n, m in product(range(N), range(M)): c.append((AB[n][0] + CD[m][0]) / (sum(AB[n]) + sum(CD[m]))) print(sorted(c, reverse=True)[K - 1] * 100)

test_all(F)

結果：#39881266

自由欄

解説を見る

「答えで二分探索」といえば競プロ典型 90 問の001 - Yokan Partyですね！(ネタバレごめん！)
何を隠そう、このブログで初めて競プロの記事を書いたのがその問題でした。

本問では二分探索の着想だけでなく、式変形して「何の値を探すか」という発想がカギだったように思います。(私はどちらも思いつかなかったですが…)

で、解説で紹介されているのが「高橋くんと青木くんの砂糖水が濃度$x$に対して何グラム砂糖が多いか」という値を探すということ。
例えば、高橋くんの砂糖水$\alpha$は濃度$x$に対して3グラム砂糖が多く、青木くんの砂糖水$\beta$は濃度$x$に対して2グラム砂糖が少ない(-2グラム多い)としたら、砂糖水$\alpha$と$\beta$を混ぜた砂糖水$\gamma$の濃度は$x$より濃ゆくなるはずです。

そして水$w$グラムが与えられた場合、濃度$x$になるための砂糖$s'$の量は、

$$ \begin{align*} & \frac{s'}{w + s'} = x \\[10pt] \Leftrightarrow \;& s' = x(w + s') \\[10pt] \Leftrightarrow \;& s'(1 - x) = xw \\[10pt] \Leftrightarrow \;& s' = \frac{xw}{(1 - x)} \\[10pt] \end{align*}\\ $$

なので、後は実際の砂糖の量から$s'$を引けば前述の値が得られます。(ここまで書き下さないと私には理解できんとです😇)

高橋くんか青木くんの一方でこの値をソートしておき、もう一方から二分探索で混ぜて$x$より濃ゆくなる本数を数えるということなんですね～
かしこっ😩

以下写経。

def F(): from bisect import bisect N, M, K = map(int, input().split()) AB = [list(map(int, input().split())) for _ in range(N)] CD = [list(map(int, input().split())) for _ in range(M)] NG = 0 OK = 1 for i in range(100): x = (NG + OK) / 2 z = x / (1 - x) v = sorted([CD[j][0] - CD[j][1] * z for j in range(M)]) num = 0 for j in range(N): w = AB[j][0] - AB[j][1] * z num += M - bisect(v, -w) if num < K: OK = x else: NG = x print(OK * 100)

test_all(F)

結果：#40164296

自由欄

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

Arakaki Tokyo — Sun, 19 Mar 2023 14:51:13 GMT

入緑しました！
という訳で振り返りです。

なお、今回からテスト関数を修正して本番同様input()等で入力を取得するようにしています。

AtCoder Beginner Contest 293 - AtCoder

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

AtCoderAtCoder Inc.

A - Swap Odd and Even

やってみよう！

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

test_dataA = [ { "in":"abcdef\n", "out": "badcfe\n" },{ "in":"aaaa\n", "out": "aaaa\n" },{ "in":"atcoderbeginnercontest\n", "out": "taocedbrgeniencrnoetts\n" }, ]

def A(): pass test_all(A)

自由欄

振り返り

コンテスト中は思考停止で設問のまま実装しました。
振り返ると、こんなやり方もあったなぁというのが以下。

def A(): S = input() print(*["".join(x) for x in zip(S[1::2], S[0::2])], sep="") test_all(A)

結果：#39764236

自由欄

B - Call the ID Number B - Call the ID Number

#39608819 #39608819

C - Make Takahashi Happy

やってみよう！

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

test_dataC = [ { "in":"""3 3 3 2 2 2 1 3 1 5 4 """, "out": """3 """ },{ "in":"""10 10 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 """, "out": """48620 """ }, ]

def C(): H, W = map(int, input().split()) A = [list(map(int, input().split())) for _ in range(H)] ans = 0 print(ans) test_all(C)

自由欄

コンテスト中

コンテスト中の提出はこんな感じ。
始点から終点までの経路を「全ての移動($MOVE_0, MOVE_1, \dots, MOVE_i, \dots, MOVE_{H + W - 1}$)のうち下に移動する$i$の組み合わせ」で全探索します。

from itertools import combinations def C(): H, W = map(int, input().split()) A = [list(map(int, input().split())) for _ in range(H)] ans = 0 for com in combinations(range(H + W - 2), r=H - 1): route = [True] * (H + W - 2) for c in com: route[c] = False h = 0 w = 0 numbers = set([A[h][w]]) for nxt in route: if nxt: w += 1 else: h += 1 numbers.add(A[h][w]) if len(numbers) == H + W - 1: ans += 1 # print(numbers) print(ans) test_all(C)

結果：#39618916

自由欄

振り返り

上の実装でもまぁまぁいいと思うんですが、強いて挙げると移動のroute配列を作る処理(9, 10行目)がなんか野暮ったいです。
他の人の提出を見ると再帰DFSが多かったので、再帰しないループDFSで実装してみたのが以下。

これならルートの途中で「嬉しくない」ことが分かれば以降の探索を省略できますね。

def C(): H, W = map(int, input().split()) A = [list(map(int, input().split())) for _ in range(H)] nums = [None] * (H + W - 1) ans = 0 st = [(0, 0)] while st: h, w = st.pop() if A[h][w] in nums[:h + w]: continue nums[h + w] = A[h][w] if h + w == H + W - 2: ans += 1 else: if h < H - 1: st.append((h + 1, w)) if w < W - 1: st.append((h, w + 1)) print(ans) test_all(C)

結果：#39772336

自由欄

D - Tying Rope D - Tying Rope

やってみよう！

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

test_dataD = [ { "in":"""5 3 3 R 5 B 5 R 3 B 4 R 2 B """, "out": """1 2 """ },{ "in":"""7 0 """, "out": """0 7 """ },{ "in":"""7 6 5 R 3 R 7 R 4 R 4 B 1 R 2 R 3 B 2 B 5 B 1 B 7 B """, "out": """2 1 """ }, ]

def D(): pass test_all(D)

自由欄

コンテスト中

連結成分、サイクル、と言えばもはやおなじみDSUですね。

from collections import defaultdict class DSU(): def __init__(self, n=None): self.dsu = defaultdict(lambda: -1) if n: for i in range(n): self.dsu[i] def leader(self, i): if self.dsu[i] < 0: return i self.dsu[i] = self.leader(self.dsu[i]) return self.dsu[i] def merge(self, i, j): '''サイズの大きい方(x)に小さい方(y)をマージ''' if i == j: return x = self.leader(i) y = self.leader(j) if x == y: return if self.dsu[x] > self.dsu[y]: x, y = y, x self.dsu[x] += self.dsu[y] self.dsu[y] = x def members(self, i): l = self.leader(i) return [k for k, v in self.dsu.items() if self.leader(k) == l] def __len__(self): return len([1 for v in self.dsu.values() if v < 0])

def D(): N, M = map(int, input().split()) dsu = DSU(N + 1) circle = 0 for _ in range(M): a, _, b, _ = input().split() a = int(a) b = int(b) if dsu.leader(a) == dsu.leader(b): circle += 1 else: dsu.merge(a, b) leaders = set() for i in range(1, N + 1): leaders.add(dsu.leader(i)) print(circle, len(leaders) - circle) test_all(D)

結果：#39622456

自由欄

E - Geometric Progression

やってみよう！

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

test_dataE = [ { "in":"""3 4 7 """, "out": """5 """ },{ "in":"""8 10 9 """, "out": """0 """ },{ "in":"""1000000000 1000000000000 998244353 """, "out": """919667211 """ }, ]

def E(): pass test_all(E)

自由欄

振り返り

コンテスト中はうまく式変形できずに終了となりました。
「式変形」がどれぐらいのレベルだったかというと、等比数列の和の公式が分からない、というかこれが等比数列だということにも気付かないレベルでした...😇

という訳で！等比数列ですよ。

$$ \sum^{X - 1}_{i = 1}A^i = \frac{A^X - 1}{A - 1} $$

こんなん余裕やん！

def E(): A, X, M = map(int, input().split()) Ax = 1 Ae = A while X: if X & 1: Ax = Ax * Ae % M X >>= 1 Ae = Ae * Ae % M # print(Ax, pow(A - 1, -1, M)) print((Ax - 1) * pow(A - 1, -1, M) % M) test_all(E)

結果：#39787192

RE x 18 😭
なぜ・・・

自由欄

解説を見る①

kyopro_friendsさんの解説を見ます。

剰余の法$M$と互いに素とは限らない数$K$で除算を行いたい場合、$\bmod MK$で計算を行えばよい

上の提出では$A - 1$と$M$が互いに素でない場合にREとなっていたようです。

ところで「$\bmod MK$で計算」すればいいの理由が分かりません…🤔
と納得できずにググったら丁寧に解説されている方がいたのでまるっと引用します。
参照：【AtCoder】ABC293 のA,B,C,D,E における Python解説 - Qiita

$$ \begin{align*} & \frac{b}{a} \equiv q \pmod{p} \\[10pt] \Leftrightarrow \;& \frac{b}{a} = np + q \\[10pt] \Leftrightarrow \;& b = nap + aq \\[10pt] \Leftrightarrow \;& \bf{b \equiv aq \pmod{ap}} \\[10pt] \Leftrightarrow \;& \bf{q = \frac{b \pmod{ap}}{a}} \\[10pt] \Leftrightarrow \;& \bf{\frac{b}{a}\pmod{p} = \frac{b \pmod{ap}}{a}} \\[10pt] \end{align*}\\ $$

なるほど、天才か。
そしてpow関数を使えば繰り返し2乗法をする必要すらないとは…
という訳で以下解説のまんま。

def E(): A, X, M = map(int, input().split()) print(X % M if A == 1 else (pow(A, X, M * (A - 1)) - 1) // (A - 1) % M) test_all(E)

結果：#39831846

自由欄

解説を見る②

Kazu1998kさんの解説とshakayamiさんの解説を見ます。

コンテスト中はなんとなくこんなことを想定して考えてました。
と言っても、再帰まで思い至らない時点で後出し知ったかぶりが見苦しいですね…

という訳で2つの解説をまとめると以下のような感じです。

$$ f(A, X) := \sum^{X-1}_{i=0}A^iとおく。\\ \begin{align*} f(A, X) \:\:\:=\:\:\: & \begin{cases} 1 & (X = 1)\\ f(A, X-1) + A^{X-1} & (X \ge 3, X: odd)\\ (1 + A^{\frac{X}{2}})f(A, \frac{X}{2}) & (X: even) \end{cases} & (1)\\ または、\\ f(A, X) \:\:\:=\:\:\: & \begin{cases} 1 & (X = 1)\\ 1 + A f(A, X-1) & (X \ge 3, X: odd)\\ (1 + A)f(A^2, \frac{X}{2}) & (X: even) \end{cases} & (2)\\ \end{align*} $$

以下、自分なりに咀嚼してコーディングしてみましたが、結局解説 by shakayamiの実装例通りになってしまいました。
せめてオリジナリティを出そうとpow関数的なヤツを自作してみましたが、特に意味はありません😇

from functools import lru_cache @lru_cache(None) def exp(base, e, M): if e == 1: return base ret = base if e & 1 else 1 e >>= 1 cnt = 2 while e: if e & 1: ret = ret * exp(base, cnt // 2, M) ** 2 % M e >>= 1 cnt *= 2 return ret % M def f1(a, x, M): if x == 1: return 1 % M elif x % 2: return (f1(a, x - 1, M) + exp(a, x - 1, M)) % M else: return ((1 + exp(a, x // 2, M)) * f1(a, x // 2, M)) % M def f2(a, x, M): if x == 1: return 1 % M elif x % 2: return (1 + a * f2(a, x - 1, M)) % M else: return (1 + a) * f2(a * a % M, x // 2, M) % M

(1)の場合

def E(): A, X, M = map(int, input().split()) print(f1(A, X, M)) test_all(E)

結果：#39834986

(2)の場合

def E(): A, X, M = map(int, input().split()) print(f2(A, X, M)) test_all(E)

結果：#39834989

自由欄

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

Arakaki Tokyo — Sun, 12 Mar 2023 07:15:03 GMT

振り返りです。

AtCoder Beginner Contest 292 - AtCoder

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

AtCoderAtCoder Inc.

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 - CAPS LOCK

提出：#39404553

B - Yellow and Red Card

提出：提出 #39410010 - AtCoder Beginner Contest 292

C - Four Variables

やってみよう！

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

test_dataC = [ { "in":[4], "out": 8 },{ "in":[292], "out": 10886 },{ "in":[19876], "out": 2219958 }, ]

def C(N): pass test_all(C)

自由欄

解説を見る：$O(N \sqrt{N})$

コンテスト中にACできず…
考えたのは、$1 \le AB, CD \le N - 1$だから$1 \le X \le N - 1$の全てのXについて素因数分解して、素因数の数(X:10の場合、2, 5で2つ)を$p$としたら$2^p$がABまたはCDの組み合わせになって・・・みたいな。
↓
でも、そもそも素因数分解がだるいし、X:16(=$2 ^ 4$)の時って「選ぶ・選ばない」でAB作っても4 × 4になるような0101, 1100,...みたいなのを重複して数えることになっちゃうから「$2^p$がABまたはCDの組み合わせになる」って考えるのは間違ってるな・・・

結果、結構な時間を使って考えた挙げ句、むっっっっずーーーーーーーー無理！！！！！！！！！となって飛ばしました。

という訳で解説 - AtCoder Beginner Contest 292を見ます。
文章だけ読んだ状態で「なるほどAを決め打ってA≦Bとしたら$O(N \sqrt{N})$でイケんのか」と実装したのが以下。

from math import ceil, sqrt def C(N): a = [0] * N a[1] = 1 for i in range(2, N): for j in range(1, ceil(sqrt(i))): if i % j == 0: a[i] += 1 a[i] *= 2 if int(sqrt(i)) ** 2 == i: a[i] += 1 # print(a) ans = 0 for i in range(1, N): ans += a[i] * a[N - i] return ans

test_all(C)

結果：#39555777

ACやったー
jでイテレートしてるrangeの終点の設定が分かりづらいですね。。

自由欄

解説を見る：--約数の個数を調べる--$O(N \log{N})$

さらに解説を見ます。

$AB=X$を満たす正整数$A,B$の個数は$X$の正の約数の個数に等しいです

😲😲😲😲😲😲😲😲😲😲😲😲😲😲😲😲❗❗❗❗❗❗❗❗❗❗❗❗❗❗❗❗❗❗❗❗❗❗❗❗❗❗❗❗❗❗❗❗

そっか…素因数分解じゃなくて約数調べたらよかったのか…
んで、その計算量は$\frac{N}{1} + \frac{N}{2} + \dots + \frac{N}{N} = N(\frac{1}{1} + \frac{1}{2} + \dots + \frac{1}{N})$で、カッコ内が調和数というものらしく、増大度は n の自然対数 ln(n) と同程度の速さであるようです。
つまり$O(N \log{N})$になるわけですね。

numpyを使って実装するとこんな感じ。

import numpy as np def C(N): a = np.ones(N, dtype=int) for i in range(2, N): sli = slice(i, N, i) a[sli] += 1 a = a[1:] return sum(a * a[::-1])

test_all(C)

結果：#39592679

自由欄

解説を見る：--やっぱり素因数分解する--

もう一つのより高速な解法の解説を見てみます。
線形篩とはなんぞ？エラトステネスの篩とは違うの？

ということで、解説内でも示されているえびちゃん🍑🍝🦃（@rsk0315_h4x）さんのライブラリ(下記1.)や、例によってググったらヒットしたけんちょんさんの記事(下記2.)を参考にクラス化してみました。

が、結論としては37zigenさんが言及しているとおりエラトステネスの篩の方が高速なため、「最小の素因数を求める」というアイディアと素因数分解や約数列挙の考え方・実装のみ援用しています。
結局、線形篩は$O(N)$ですがエラトステネスの篩$O(N \log\log{N})$(参照)の方が高速で、「各iがlpf(i)で何回割り切れるか」も前処理として$O(N)$で求めておくことで(下記41行~)、iの昇順に素因数分解を$O(1)$で得られることになります。
そして素因数分解が分かっていれば、約数の個数は簡単に計算できてしまいます。(参照)

一般に$N = p_{1}^{e_{1}} p_{2}^{e_{2}} \dots p_{K}^{e_{K}}$と素因数分解できるとき、約数の個数は$(e_{1} + 1)(e_{2} + 1) \dots (e_{K} + 1) 個$となります。

「約数の個数を求めるために素因数分解する」という着想自体は、(けんちょんさんの指摘通りオーバーキルだとしても)間違ってなかったんですね。

ちなみに、線形篩というキーワードだけで横道に逸れた結果、もとの解説とはもはや別物です。(というか、解説をよく分かってない。)

参考🔎

LinearSieve in nekolib::math - Rust
- linear_sieve.rs - source
けんちょんさんの記事
- エラトステネスの篩の活用法を総特集！〜高速素因数分解・メビウスの反転公式〜 - Qiita
  - 線形篩について：線形篩 – 37zigenのHP
  - 素因数分解：4-1. 高速素因数分解
  - 約数列挙：4-2. 高速約数列挙
- AtCoder 版！マスター・オブ・整数 (素因数分解編) - Qiita
  - 約数の個数について：5-1. 約数の個数 (問題 5)
  - ところで、約数の個数を求めるだけなら素因数分解はオーバーキルで、約数列挙で十分です。しかし、素因数分解で考えることには大きなメリットがあります。それは「約数に関する考察をしやすい」ということです。
Linear Sieve - Algorithms for Competitive Programming

from enum import Enum from functools import lru_cache, reduce from operator import mul from itertools import product class Sieve: method = Enum("method", ["ERATOSTHENES", "LINEAR"]) def __init__(self, n, method=method.ERATOSTHENES): if method == self.method.ERATOSTHENES: primes = [False, False] + [True] * (n - 1) self.lpf = list(range(n + 1)) for p in range(2, int(n ** (1 / 2)) + 1): if not primes[p]: continue self.lpf[p] = p for q in range(p * 2, n + 1, p): primes[q] = False if self.lpf[q] == q: self.lpf[q] = p elif method == self.method.LINEAR: self.lpf = list(range(n + 1)) primes = [] for i in range(2, n + 1): if self.lpf[i] == i: primes.append(i) lpf_i = self.lpf[i] for p in primes: if p > lpf_i or i * p > n: break self.lpf[i * p] = p else: raise ValueError(f"'method' must be instance of '{self.__class__.__name__}.method'.") # 各iがlpf(i)で何回割り切れるか self.lpf_e = [[1, 0] for _ in range(n + 1)] for i in range(2, n + 1): p = self.lpf[i] j = i // p self.lpf_e[i] = ( [self.lpf_e[j][0] * p, self.lpf_e[j][1] + 1] if self.lpf[j] == p else [self.lpf[i], 1] ) @lru_cache(None) def factors(self, n): lpfs = [(self.lpf[n], self.lpf_e[n][1])] if self.lpf_e[n][0] == n: return lpfs else: return lpfs + self.factors(n // self.lpf_e[n][0]) @lru_cache(None) def divisors(self, n): if n == 1: return [1] elif self.lpf[n] == n: return [1, n] else: return sorted([ a * b for a, b in product( self.divisors(n // self.lpf_e[n][0]), [self.lpf[n] ** i for i in range(self.lpf_e[n][1] + 1)] ) ]) def divisors_count(self, n): return reduce(mul, [e + 1 for _, e in self.factors(n)])

def C(N): s = Sieve(N) return sum(s.divisors_count(N - i) * s.divisors_count(i) for i in range(1, N))

test_all(C)

結果：#39594096(線形篩の場合：#39594745)

おぉ、実行時間が危なっかしいところですが無事AC。

自由欄

D - Unicyclic Components

やってみよう！

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

test_dataD = [ { "in":[3, 3, [[2, 3], [1, 1], [2, 3]]], "out": "Yes" },{ "in":[5, 5, [[1, 2], [2, 3], [3, 4], [3, 5], [1, 5]]], "out": "Yes" },{ "in":[13, 16, [[7, 9], [7, 11], [3, 8], [1, 13], [11, 11], [6, 11], [8, 13], [2, 11], [3, 3], [8, 12], [9, 11], [1, 11], [5, 13], [3, 12], [6, 9], [1, 10]]], "out": "No" }, ]

def D(N, M, uv): pass test_all(D)

自由欄

解説を見る①

コンテスト中はお馴染みのDSUクラスを、連結成分の数ではなく辺の数を持つように変更を加えることでACに至りましたが、その過程で2WAとなってしまいました😇

解説を見ます。あっ、そんな面倒なことせずともDSUクラスのままでイケたんや…
という訳で以下。

def D(N, M, uv): dsu = DSU(N + 1) for i in uv: dsu.merge(*i) edge = defaultdict(int) for u, v in uv: edge[dsu.leader(u)] += 1 for l, e in edge.items(): if abs(dsu.dsu[l]) != e: return "No" return "Yes" if len(uv) == N else "No"

test_all(D)

結果：#39661034

自由欄

解説を見る②

ユーザ解説を見ます。

答えは、$N=M$かつすべての連結成分がサイクルを持つことです。

ということで超頂点を導入し、サイクルができたら超頂点と繋ぐとのこと。
実装を見ると、UnionFindクラスでunionメソッドの返り値が「既に連結成分かどうか」を返してるっぽいので、我がDSUクラスでも同様の挙動になるように変更を加えて(下記15, 18行目)、こんな感じ。

from collections import defaultdict class DSU(): def __init__(self, n=None): self.dsu = defaultdict(lambda: -1) if n: for i in range(n): self.dsu[i] def leader(self, i): if self.dsu[i] < 0: return i self.dsu[i] = self.leader(self.dsu[i]) return self.dsu[i] def merge(self, i, j): '''サイズの大きい方(x)に小さい方(y)をマージ''' # if i == j: return x = self.leader(i) y = self.leader(j) if x == y: return True if self.dsu[x] > self.dsu[y]: x, y = y, x self.dsu[x] += self.dsu[y] self.dsu[y] = x def members(self, i): l = self.leader(i) return [k for k, v in self.dsu.items() if self.leader(k) == l] def __len__(self): return len([1 for v in self.dsu.values() if v < 0])

def D(N, M, uv): dsu = DSU(N + 1) for u, v in uv: if dsu.merge(u, v): dsu.merge(0, u) return "Yes" if N == M and abs(dsu.dsu[dsu.leader(0)]) == N + 1 else "No"

test_all(D)

結果：#39661999

自由欄

E - Transitivity E - Transitivity

やってみよう！

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

test_dataE = [ { "in":[4, 3, [[2, 4], [3, 1], [4, 3]]], "out": 3 },{ "in":[292, 0, []], "out": 0 },{ "in":[5, 8, [[1, 2], [2, 1], [1, 3], [3, 1], [1, 4], [4, 1], [1, 5], [5, 1]]], "out": 12 }, ]

def E(N, M, uv): pass test_all(E)

自由欄

try

コンテスト中はBFSっぽい実装で愚直に操作を繰り返して数え上げました。
それが以下。

from collections import defaultdict, deque def E(N, M, uv): nxt = set() edge = defaultdict(list) for u, v in uv: edge[u].append(v) nxt.add(v) ans = 0 for a in range(1, N + 1): q = deque(edge[a]) while q: b = q.popleft() if b == a: continue for c in edge[b]: if c in [a, b]: continue if c not in edge[a]: ans += 1 edge[a].append(c) q.append(c) # print(a, b, c) return ans

test_all(E)

結果：#39443129

TLE x 3😇

自由欄

解説を見る

解説によると、「最終的なグラフの状態において存在する頂点$x$を始点とする有向辺は、初期状態において頂点$x$から到達可能な頂点」らしいです。
そうなんだ…　あー、まぁ、そうか…

で結局全ての頂点についてBFSです。

from collections import defaultdict, deque def E(N, M, uv): edge = defaultdict(set) for u, v in uv: edge[u].add(v) ans = 0 for i in range(1, N + 1): q = deque(edge[i]) seen = edge[i].copy() seen.add(i) while q: now = q.popleft() for nxt in edge[now]: if nxt in seen: continue q.append(nxt) seen.add(nxt) ans += len(seen) - 1 - len(edge[i]) return ans

test_all(E)

結果：#39663652

自由欄

まとめ

自由欄

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

Arakaki Tokyo — Fri, 03 Mar 2023 13:48:21 GMT

振り返りです。

AtCoder Beginner Contest 291（Sponsored by TOYOTA SYSTEMS） - AtCoder

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

AtCoderAtCoder Inc.

A - camel Case

提出：#39225518

B - Trimmed Mean

提出：#39231783

C - LRUD Instructions 2

やってみよう！

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

test_dataC = [ { "in":[5, "RLURU"], "out": "Yes" },{ "in":[20, "URDDLLUUURRRDDDDLLLL"], "out": "No" } ]

def C(N, S): pass test_all(C)

自由欄

振り返り

振り返ってゼロからやってみたのがこちら。

from collections import defaultdict def C(N, S): move = { "R": lambda x, y: (x + 1, y), "L": lambda x, y: (x - 1, y), "U": lambda x, y: (x, y + 1), "D": lambda x, y: (x, y - 1), } now = (0, 0) points = defaultdict(int, {now: 1}) for c in S: nxt = move[c](*now) if points[nxt]: return "Yes" break else: points[nxt] += 1 now = nxt else: return "No"

test_all(C)

結果：#39371279

自由欄

コンテスト中

コンテスト中の提出がこちら。
とりあえずsetにぶっこんで後から要素数を数えてるんですね。
なんかコンテスト中のほうが時間に追われてるせいか、無駄がない実装ができてるな笑(でも1回WA出したのは内緒)

def C(N, S): move = { "R": lambda x, y: (x + 1, y), "L": lambda x, y: (x - 1, y), "U": lambda x, y: (x, y + 1), "D": lambda x, y: (x, y - 1), } now = (0, 0) points = set([now]) for c in S: now = move[c](*now) points.add(now) return "No" if len(points) == (N + 1) else "Yes"

test_all(C)

結果：#39240915

自由欄

D - Flip Cards

やってみよう！

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

test_dataD = [ { "in":[3, [[1, 2], [4, 2], [3, 4]]], "out": 4 },{ "in":[4, [[1, 5], [2, 6], [3, 7], [4, 8]]], "out": 16 },{ "in":[8, [[877914575, 602436426], [861648772, 623690081], [476190629, 262703497], [971407775, 628894325], [822804784, 450968417], [161735902, 822804784], [161735902, 822804784], [822804784, 161735902]]], "out": 48 }, ]

def D(N, AB): pass test_all(D)

自由欄

コンテスト中

単純なDPです。
段々DPが解けるようになってきて嬉しい😊

def D(N, AB): dp = [[0] * 2 for _ in range(N)] dp[0][0] = 1 dp[0][1] = 1 for i in range(1, N): if AB[i][0] != AB[i - 1][0]: dp[i][0] += dp[i - 1][0] if AB[i][0] != AB[i - 1][1]: dp[i][0] += dp[i - 1][1] if AB[i][1] != AB[i - 1][0]: dp[i][1] += dp[i - 1][0] if AB[i][1] != AB[i - 1][1]: dp[i][1] += dp[i - 1][1] dp[i][0] %= 998244353 dp[i][1] %= 998244353 return sum(dp[-1]) % 998244353

test_all(D)

結果：#39253036

自由欄

E - Find Permutation

やってみよう！

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

test_dataE = [ { "in":[3, 2, [[3, 1], [2, 3]]], "out": """Yes 3 1 2\n""" },{ "in":[3, 2, [[3, 1], [3, 2]]], "out": """No\n""" },{ "in":[4, 6, [[1, 2], [1, 2], [2, 3], [2, 3], [3, 4], [3, 4]]], "out": """Yes 1 2 3 4\n""" }, ]

from io import StringIO

def E(N, M, XY): out = StringIO() print("answer", file=out) return out.getvalue() test_all(E)

自由欄

コンテスト中

コンテスト中は「DFSで葉まで辿り着いた時に全ての数字を通っていれば"Yes"だろう」って考えで実装したのが以下。
ブラウザ環境で実行するために余計な処理が入ってますが、基本は単純なDFSです。

が、TLEとなりその後微修正を繰り返すもACならず試合終了。

from collections import defaultdict, deque def E(N, M, XY): out = StringIO() edge = defaultdict(list) larger = set() for X, Y in XY: larger.add(Y) edge[X].append(Y) route = [] exit = [False] def dfs(n): if exit[0]: return route.append(n) if len(route) == N: _, ans = zip(*sorted(zip(route, range(1, N + 1)))) print("Yes", file=out) print(*ans, file=out) exit[0] = True for nxt in edge[n]: dfs(nxt) route.pop() first = set(range(1, N + 1)) - larger if len(first) > 1: print("No", file=out) else: dfs(first.pop()) if not exit[0]: print("No", file=out) return out.getvalue() test_all(E)

結果：#39261710

振り返り

「DFSの計算量って$O(N + M)$なのになんでTLEなんの！？😡」と思ったのですが、今回のように「葉にたどり着いたときに全ての数字を通っている」ことを確認するためには一度通った頂点や辺を何度も重複して探索する必要があるんですね。
通常の全探索を行うDFSなら一度通った頂点はパスするので$O(N + M)$になりますが、上の実装では上記理由からその処理を行っていないのでTLEになるのは当然だったのでした…

ではどうするか。
今回の問題では最短経路ならぬ最長経路を求めているようなものなので、ある頂点に辿り着く経路が複数ある場合、その経路が短い方は明らかに解ではありません。
そのような管理ができるのはBFSで、最短経路を求めるように探索しながら、ある頂点に辿り着いたときにその頂点に辿り着ける別の未探索の経路がある場合にはそれ以上探索しない(最短経路探索なので未探索の経路の方が長い)ことで計算量を$O(N + M)$に抑えることができます。

そんな感じで実装したのが以下。
数字の昇順にインデックスを繋ぐグラフをedgeで、逆方向の降順のグラフをegdeで管理することで上の考えを実現できました。

from collections import defaultdict, deque def E(N, M, XY): edge = defaultdict(set) egde = defaultdict(set) larger = set() for X, Y in XY: larger.add(Y) edge[X].add(Y) egde[Y].add(X) route = defaultdict(int) first = set(range(1, N + 1)) - larger if len(first) > 1: return "No\n" first = first.pop() q = deque([first]) while q: now = q.popleft() for nxt in edge[now]: if len(egde[nxt]) > 1: egde[nxt].remove(now) continue route[nxt] = now q.append(nxt) ans = [] while now != 0: ans.append(now) now = route[now] if len(ans) < N: return "No\n" else: _, ans = zip(*sorted(zip(ans[::-1], range(1, N + 1)))) return "Yes\n" + " ".join(map(str, ans)) + "\n"

test_all(E)

結果：#39377313

解説で言及されているトポロジカルソートについては、いつか勉強します😇

自由欄

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

Arakaki Tokyo — Thu, 02 Mar 2023 10:54:33 GMT

振り返りです。

Toyota Programming Contest 2023 Spring Qual B（AtCoder Beginner Contest 290） - AtCoder

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

AtCoderAtCoder Inc.

A - Contest Result

B - Qual B

略

C - Max MEX

やってみよう！

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

test_dataC = [ { "in":[7, 3, [2, 0, 2, 3, 2, 1, 9]], "out": 3 } ]

def C(N, K, A): pass test_all(C)

自由欄

try

振り返りよりコンテスト中の方がいい感じだったので置いときます。
こんな感じ。

def C(N, K, A): A = sorted(set(A)) ans = 0 for i in range(min(K, len(A))): if A[i] == i: ans += 1 else: break return ans

test_all(C)

結果：#39024386

自由欄

D - Marking

やってみよう！

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

test_dataD = [ { "in":[9, [[4, 2, 1], [4, 2, 2], [4, 2, 3], [4, 2, 4], [5, 8, 1], [5, 8, 2], [5, 8, 3], [5, 8, 4], [5, 8, 5],]], "out": """0 2 1 3 0 3 1 4 2""" }, ]

def D(T, NDK): pass test_all(D)

自由欄

try

コンテスト中の終了間際提出が変数名間違えるという凡ミスしてたので修正したのが以下。
でも結局RE x 4...

import numpy as np def D(T, NDK): for n, D, k in NDK: D = D % n if n % D == 0: cycle = n // D else: cycle = np.lcm(D, n) // D if cycle == 0: d = 0 m = k else: d, m = divmod(k - 1, cycle) m += 1 # print(k, m, cycle) print((d + (D * (m - 1))) % n) return

test_all(D)

結果：#39313452

振り返り

上のコードを見返しても、何がしたかったのかよく分かりません😇
まぁ、頑張って考えたんだろうな、俺。そして頭の中ごちゃごちゃになったんだろうな。お疲れ…

という訳で改めて考えてみると、以下のようなことがしたかったんでしょう。

import numpy as np def D(T, NDK): for N, D, K in NDK: if D % N == 0: cycle = 1 else: D = D % N cycle = np.lcm(D, N) // D K -= 1 print(D * K % N + K // cycle) return

test_all(D)

結果：#39313452

無事AC😁

解説を見る

実は上の振り返りの前に解説を見てみたのですが、一旦理解することを諦めました。
それが以下。

import numpy as np def D(T, NDK): for N, D, K in NDK: K -= 1 a = N // np.gcd(N, D) print(D * K % N + K // a)

test_all(D)

結果：#39313982

んで、振り返りの後にまた見てみると、ほとんど一緒やん！！(まぁところどころ影響を受けたのは否めない…)
自力で考えたのは、「何回目に元の場所に戻るか」ということで、それなら最小公倍数だろうとなったのですが、最大公約数でも同じ数が出せるというなんですね。

確認します。
今回「何回目に元の場所に戻るか」を知るために$\frac{lcm}{D}$で計算しました。
ここで$D = gcd \times d$、$N = gcd \times n$と置くと、$lcm = gcd \times d \times n$と表せます。
という訳で、結局
$\frac{lcm}{D} = \frac{gcd \times d \times n}{gcd \times d} = n = \frac{N}{gcd}$
という解説の想定解の式になるわけですね。勉強になった。(中高で習った…？)

自由欄

E - Make it Palindrome

やってみよう！

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

test_dataE = [ { "in":[5, [5, 2, 1, 2, 2]], "out": 9 } ]

def E(N, A): pass test_all(E)

自由欄

解説を見る

回文を作れって、稀によく見る気がしますね。
まぁそんな気がするだけで解法の見当は全くつかないので解説を見ます。

斜め読みして「主客転倒完全に理解した！」ってことで提出したのが以下。

from itertools import combinations from collections import defaultdict def E(N, A): ans = 0 for i, j in combinations(range(N), 2): if A[i] == A[j]: continue ans += min(i + 1, N - j) return ans test_all(E)

結果：#39333959

TLE × 56...
そりゃすべての組み合わせを見ると$O(N ^ 2)$になって今回の制約下だと無理だわな。

ちゃんと解説を見る

「悪い線の合計、簡単に出せるじゃん」と考えて書いたのが上のコードでした。
もちろん処理自体は簡単なのですが、計算量の壁が立ちはだかります。

解説でわざわざ(悪い線の合計) = ( 線の合計 - 良い線の合計 )としているのは、工夫すれば良い線の合計を$O(N)$で出せるからなんですね。
詳細は解説を見ていただくとして、以下のコードでは9行目からのfor文がそれにあたります。
考え方を理解するのになかなかの時間を要しました😇

def E(N, A): p = defaultdict(list) for i, a in enumerate(A, 1): p[a].append(i) res = 0 for i in range(1, N + 1): res += (N + 1 - i) * (i // 2) for v in p.values(): l = 0; r = len(v) - 1 while l < r: if v[l] < (N + 1 - v[r]): res -= (r - l) * v[l] l += 1 else: res -= (r - l) * (N + 1 - v[r]) r -= 1 return res test_all(E)

結果：#39335826

自由欄