ARC143の振り返り(A, B, C)

Aが解けたよ！
という訳で振り返りです。

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 - Three Integers

やってみよう！

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

test_dataA = [ { "in":[2, 2, 3], "out": 3 },{ "in":[0, 0, 1], "out": -1 },{ "in":[0, 0, 0], "out": 0 }, ] def A(*n): pass test_all(A)

自由欄

try

コンテスト中に提出したコードはもうちょっとごちゃっとしてた(提出 #32774805)けど、結局目標達成の条件は以下2つのどちらかだけ。

3つの数が同じ
最も大きい数が他2つの合計以下

def A(*n): n = sorted(n) if n[0] == n[1] == n[2] or n[0] + n[1] >= n[2]: return n[2] else: return -1 test_all(A)

結果：提出 #32826161 - AtCoder Regular Contest 143

自由欄

B - Counting Grids

やってみよう！

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

test_dataB = [ { "in":[2], "out": 8 },{ "in":[5], "out": 704332752 },{ "in":[100], "out": 927703658 } ] def B(N): pass test_all(B)

自由欄

try

これは解説を読んでもスッキリしませんでした。

曰く、

「2 つの条件をともに満たさないようなマスは高々 1 つしか存在しません」←分かる
「2 つの条件を満たすマスが存在するような書き込み方の個数を数えます」←？
- マスの位置は$N^2$通り
- そのマスと同じ行・列に書き込まれる数の選び方は$\begin{pmatrix}N^2\\2N - 1\end{pmatrix}$通り
- 数の書き込み方は
  - マスと同じ行：$(N-1)!$
  - マスと同じ列：$(N-1)!$
  - 他：$(N-1)^2!$

なぜ「2 つの条件を満たすマスが存在するような書き込み方の個数」が上のようになるのかが分からない…
上の計算を素直に解釈すると、「任意の一行と任意の一列に特定の数を使う場合の組合せ」ってだけで、設問の条件とは無関係だと思うんだけどなぁ…

何はともあれ、「2 つの条件を満たすマスが存在するような書き込み方の個数」は以下の簡単な計算で求まることになります。

$$ \begin{alignat}{1} & N^2 \times (N^2)! \:/\: (N^2 - 2N + 1)! \:/\: (2N - 1)! \times (N-1)! \times (N-1)! \times (N-1)^2! \\ = & \frac{N^2 \times (N^2)! \times (N-1)!^2 \times (N^2 - 2N + 1)!}{(N^2 - 2N + 1)! \times (2N - 1)!} \\ = & \frac{(N^2)! \times N!^2}{(2N - 1)!} \end{alignat} $$

ここで他のプログラミング言語であれば、オーバーフローしないように計算の途中で余りを取る処理を入れ込まなければなりません。
対してPythonの整数型は任意長でデータを保持するので、そのまま計算することができます。(参考：Pythonの整数型はどのように実装されているのか)

def B(N): import math p = math.perm MOD = 998244353 return (p(N*N) - p(N*N) * p(N)**2 // p(2*N - 1)) % MOD test_all(B)

結果：提出 #32827156 - AtCoder Regular Contest 143
PyPy(≒Python 3.6)ではmath.permが未実装なのでmath.factorialを使いました。

自由欄

C - Piles of Pebbles

せっかくなのでC問題も見てみます。

C - Piles of Pebbles

やってみよう！

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

test_dataC = [ { "in":[2, 1, 1, [3, 3]], "out": "First" },{ "in":[2, 1, 2, [3, 3]], "out": "Second" }, ] def C(N, X, Y, A): pass test_all(C)

自由欄

try

「二人の最適な行動」とか、どうやって考えたらいいんだ…って感じですが、どうやら$X + Y$で割った余りがポイントのようです。
詳細は解説を参照するとして、コードは以下のようにとてもシンプルになりました。

def C(N, X, Y, A): B = [a % (X+Y) for a in A] if max(B) < X: return "Second" elif X <= y: return "first" else: c="[b" if b < x else - for in b] max(c) "second"< py-cell> test_all(C)

結果：提出 #32825651 - AtCoder Regular Contest 143

自由欄

まとめ

A~Cは発想力？