無念のゼロAC…

という訳で振り返りです。

AtCoder Regular Contest 145 - 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 - AB Palindrome

A - AB Palindrome

やってみよう！

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

test_dataA = [ { "in":[3, 'BBA'], "out": "Yes" },{ "in":[4, 'ABAB'], "out": "No" }, ] def A(N, S): pass test_all(A)

自由欄

try

以下のようなことを考えましたが、結果として全くの見当違いでした…

  • Sを前半後半に分けて、前半だけ操作して後半と一致するようにすればいいのかなぁ
  • S[0]から順に見ていけばいいのかなぁ。いや、後半が...BBBBBAみたに終わる場合は先頭から順に操作するわけじゃないしなぁ…
  • 実際に操作せずとも、後半部分が操作後の形になっていればいいのでは！？つまり、「(後ろから見て)1つ以上のAと1つ以上のBの組み合わせ」が1つ以上で成り立っていればいいのでは？
  • いやいや、上に一致しない範囲でも初期値で回分状態になっていればいいわけで…

どうすりゃいいんだい！

泥沼です。無理くり実装してみましたが当然のごとくWAで紹介する価値もないので、以下解説を見てみましょう。

結局、以下の条件のいずれかを満たす場合のみ答えはNoで、それ以外の場合答えはYesです。

  • Sの先頭の文字がAで末尾の文字がBのとき
  • SがBAのとき

まじかぁ～！？
確かにぃぃ～～

def A(N, S): return "No" if (S[0] == "A" and S[-1] == "B") or S == "BA" else "Yes" test_all(A)

結果：提出 #33648791 - AtCoder Regular Contest 145

自由欄

B - AB Game

B - AB Game

やってみよう！

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

test_dataB = [ { "in":[4, 2, 1], "out": 2 },{ "in":[27182818284, 59045, 23356], "out": 10752495144 }, ] def B(N, A, B): pass test_all(B)

自由欄

try

解説にある通り、Aliceが勝つのは$n \ge A かつ n\mod A \lt B$の場合です。
その実装がなかなか難しく(解説がすんなり理解できない…)、以下のようにしてみました。
(よくよく解説を理解すると、やってることは大体一緒、のはず)

def B(N, A, B): if A > B: d, m = divmod(N, A) m = (m + 1) % A return max(0, (d-1)*B + min(m, B)) else: return max(0, N - A + 1) test_all(B)

結果：提出 #33649868 - AtCoder Regular Contest 145

自由欄

C - Split and Maximize

C - Split and Maximize

やってみよう！

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

test_dataC = [ { "in": [2], "out": 16 },{ "in": [10000], "out": 391163238 }, ] def C(N): pass test_all(C)

自由欄

try

せっかくなのでC問題まで見てみます。
とはいえ、解説を読んで理解はできても、その思考プロセスを身につけられる気がしません。
余談ですが、中学時代の数学の先生の言葉を思い出しました。曰く、

「分かる」と「できる」は違う。(だから何度も練習問題やろうね)

という訳で、思い立った時にこの記事上でサクッとコーディングできる環境だけ用意しておくことにします。(反復練習！)

以下はまんま解説の実装例です。
ARC143のB問題でも似たような計算をしていますが、そのときは$1 \le N \le 500$という制約下だったので計算途中にmodを組み込まなくても回答できました。
今回はさすがにmodを取りながらでないとTLEになってしまいます。

mod = 998244353 def C(N): res = pow(2, N, mod) for i in range(N+2, 2*N+1): res *= i res %= mod return res test_all(C)

結果：提出 #33652061 - AtCoder Regular Contest 145

自由欄

まとめ

地道に継続します。

自由欄