初参戦したコンテストでC問題を時間内に解けなかったのでメモ。

Aising Programming Contest 2022（AtCoder Beginner Contest 255） - AtCoder
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.
AtCoderAtCoder Inc.

問題

C - ±1 Operation 1

要は与えられた整数$X$と、最も近い等差数列$S$の値との差の絶対値を求めよ、という問題。

こうして考えると簡単そうですね。
えぇ、簡単なんですよ、しょうもないミスをしなければ…

try(WA)

考え方

  • $X$が$S$の初項($S_{(1)}$)より小さければ$abs(S_{(1)}-X)$を返す
  • $X$が$S$の末項($S_{(N)}$)より大きければ$abs(S_{(N)}-X)$を返す
  • それ以外なら$S$から最も近い値を探す(2分探索)
    • この場合、$S$は$X$より小さい範囲と大きい範囲に分割できる。
    • その境界を挟む2点のうち、どちらかが$X$に最も近い。

という感じで実装したのが以下

def main(X, A, D, N): def check(i): return A+D*i - X < 0 seq_max = A+D*N if A > seq_max: seq_min = seq_max seq_max = A else: seq_min = A if X > seq_max: return abs(seq_max - X) elif X < seq_min: return abs(seq_min - X) else: neg = 0 pos = N while abs(neg - pos) > 1: mid = (neg + pos) // 2 if check(mid): neg = mid else: pos = mid return min(abs(A+D*neg - X) , abs(A+D*pos - X))

テストデータ・テスト関数定義

# 縮小表示 test_data = [ { "in": [6, 2, 3, 3], "out": 1 },{ "in": [0, 0, 0, 1], "out": 0 },{ "in": [998244353, -10, -20, 30], "out": 998244363 },{ "in": [-555555555555555555, -1000000000000000000, 1000000, 1000000000000], "out": 444445 }, ] def test_all(f): for i, data in enumerate(test_data): exp = data["out"] ans = f(*data["in"]) result = "AC" if exp == ans else "WA" print(f"{i+1} {result}: expected: {exp}, output: {ans}") test_all(main)

良さそうに見えますが、上のコードには2箇所の間違いがあります。

結果

提出 #32414158 - エイシングプログラミングコンテスト2022（AtCoder Beginner Contest 255）

ACとWAが約半々という結果に…
ここで時間切れとなってしまいました。

デバッグ

聡明な読者諸賢ならお気づきかと思いますが、以下が修正点です。

  1. 8行目：数列の最大(小)値はA + D * (N - 1)である
  2. 18~19行目：整数$X$より小さい範囲(neg)、大きい範囲(pos)の初期値は、$D < 0$の場合逆になる

どちらも悲しくなるくらい愚かなミスです😡👹
以後、同じことを繰り返さないよう、戒めとしてここに残しておきます。

という訳で修正したのがこちら

def main(X, A, D, N): def is_positive(i): """数列のi番目がXより大きいか""" return A+D*i - X > 0 seq_max, seq_min = (A+D*(N-1), A) if D > 0 else (A, A+D*(N-1)) if X >= seq_max: return abs(seq_max - X) elif X <= seq_min: return abs(seq_min - X) else: neg, pos = (0, N-1) if D > 0 else (N-1, 0) while abs(neg - pos) > 1: mid = (neg + pos) // 2 if is_positive(mid): pos = mid else: neg = mid return min(abs(A+D*neg - X) , abs(A+D*pos - X)) test_all(main)

結果

無事ACとなりました

提出 #32423981 - エイシングプログラミングコンテスト2022（AtCoder Beginner Contest 255）

推敲

公式解説でのポイントは以下でしょうか

  • 最初に$D > 0$となるように正規化する
  • 2文探索を使わなくても解ける

1点目によって、今回のミスの一つは防ぐことができます。
『場合分けを減らす』というアイディアは色んな場面で活用できそうです。

2点目は盲点というかなんというか、ついつい覚えた手法(今回は2文探索)を使いたくなってしまいがちですが、それを使わず簡単に解けるなら越したことはありません。
状況に応じた柔軟な考え方ができるようになりたいものです。

def main(X, A, D, N): if D < 0: A = A+D*(N-1) D = -D seq_max, seq_min = A+D*(N-1), A if X >= seq_max: return abs(seq_max - X) elif X <= seq_min: return abs(seq_min - X) else: side1 = (X - A) % D return min(side1, D - side1) test_all(main)

結果：提出 #32433205 - エイシングプログラミングコンテスト2022（AtCoder Beginner Contest 255）

まとめ

数列の項数と、インデックス…注意

自由欄