ABC302の振り返り
振り返りです。
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」ボタンをクリックしよう!
自由欄
コンテスト中
「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.
こんな感じ。
結果:#41544181
自由欄
解説を理解する
解説曰く、「$\frac{A}{B}$の切り上げは、$\frac{A + B - 1}{B}$の切り捨てと等しい」とのこと。
以下確認してみます。
整数$x, y$を用いて以下のような整数$a, b$について考えます。
$a = bx + y\:(0 \le y \lt b)$
ここで、$\frac{a}{b}$の切り上げは以下のようになります。
解説の式を見ていくと、
$y < b$なので$\frac{y - 1}{b}$の取りうる範囲は
なので、
となり、結果として
が成り立つという訳ですね。
天才かよ。
Pythonのint型とfloat型の精度
ABC262のA問題でも取り上げましたが、Pythonのint型に精度の制限はありません。対してfloat型は大体倍精度浮動小数点です。
参照)組み込み型 — Python 3.11.4 ドキュメント
私の最初の考えのように「小数点以下を切り上げ」しようとすると倍精度浮動小数点での演算になってしまい、3つ目のテストケースでは表現可能な範囲を超えてしまいます。
倍精度浮動小数点で表現できる整数はせいぜい15桁までです。(参照:sys.float_info.dig)
一方int型の除算であれば、精度の制限なく、かつデフォルトで切り捨ての挙動となるので、解説のような式に変換することで解が得られるという訳なんですね。
A問題、勉強になるなぁ~
B - Find snuke
略
深さ優先探索っぽく再帰関数で実装。
コンテスト中:#41558048
振り返り:#43176130
C - Almost Equal
やってみよう!
C
関数を完成させて「Run」ボタンをクリックしよう!
自由欄
コンテスト中
「これは一筆書きの判定なのでは?」と考えてググると「次数が奇数の頂点が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
自由欄
解説を見る
公式解説では愚直な全探索で問題ないと…
「制約が小さければ全探索」は基本でしたね😇
結果:#43181911
自由欄
D - Impartial Gift
やってみよう!
D
関数を完成させて「Run」ボタンをクリックしよう!
自由欄
コンテスト中
単純な貪欲法で「贈り物の価値の和」が大きいパターンから見ていき、価値の差が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」ボタンをクリックしよう!
自由欄
try
せっかくなのでE問題もやってみます。
と言いつつ力尽きたので早速解説を見ます。どうせ俺がまだ知らないアルゴリズムとか使ってんだろ!
と思いきや、意外にも素直な考え方でイケるっぽい?
という訳で解説の文章だけカンニングして実装してみたのが以下。
結果:#43200104
ちなみにPythonでの提出ではTLEとなってしまいます。
やっぱデフォルトPyPyのほうがいいな。
自由欄