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

振り返りです。

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 - 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$)を処理に組み込むような実装が最初からできればよかったわけですな。はい。