ABC302の振り返り

振り返りです。

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.
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 - 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 ドキュメント

私の最初の考えのように「小数点以下を切り上げ」しようとすると倍精度浮動小数点での演算になってしまい、3つ目のテストケースでは表現可能な範囲を超えてしまいます。
倍精度浮動小数点で表現できる整数はせいぜい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のほうがいいな。

自由欄

自由欄