AtCoder Regular Contest 143 の A、B を解く

はじめに

A - Three Integers

考察

• A、B、C の順序は答えに影響しなさそうなので最初にソートしてしまおう。
  • A <= B <= C とする。
• 初期値で考えられるパターンは A == B == C、A < B == C、A == B < C、A < B < C の 4 種類。
  • A == B == C の場合、操作 2 (すべての整数から 1 を引く) を繰り返すことで目標が達成できる。
  • A < B == C の場合、操作 1 (2 つの整数を選んで，それらから 1 を引く) を B と C に対して行うことで A == B == C にできる。
    • 操作 1 を B - A 回、操作 2 を A 回行うので、答えは B - A + A = B 回になる。
  • A == B < C の場合が厄介そう。A と B を同じだけ減らし、C をより多く減らす方法を考える。
    • 操作 1 を A と C、B と C に合計 2 回行うことで A、B、C をそれぞれ 1、1、2 減らすことができる。（この操作を「操作 3 」とする。）
    • 上の操作の繰り返し以外で C だけをより多く減らす方法はなさそう。
    • これってどんなパターンでもできる？？？
      • できない。2*B < C の時、操作 3 を繰り返すと最終的に C が残ることになる。
    • 2*B < C の時は答えが -1、そうでなければ操作 3 を C - B 回した後、操作 2 を残りの数行うので (C - B) * 2 + (B - (C - B)) = C
  • A < B < C の場合、操作 1 を B と C に (B-A) 回行うことで A == B < C にできる。そこからは A == B < C のパターンと一緒。

実装

def resolve():
  A, B, C = sorted([int(x) for x in input().split(" ")])

  # A == B == C のパターン
  if A == C:
    print(A)
    return

  # A < B == C のパターン
  if B == C:
    print(B)
    return

  # A < B < C のパターンは最終的に A == B < C を経由するので先に A < B < C パターンから処理する。
  ans = B-A
  C -= B-A
  B -= B-A

  if C > 2*B:
    print(-1)
    return
  
  # A == B < C のパターン
  ans += C
  print(ans)

resolve()

B - Counting Grids

考察

• 数学問題っぽい？
• 事象をそのまま求める場合と、全事象 - 余事象 のパターンがあるけどどっちだろう？
  • すべてのマスについて条件を満たしていることを考えるのは大変そうなので、余事象を求める方針でやってみる。
• 条件を満たさないマス目について考える。
  • そのマス目に書かれている数字は「そのマスが含まれている列で最大」かつ「そのマスが含まれている行で最小」である必要がある。
    • 条件を満たさないマス目に書かれている数字を X とした時、X 未満の数字を (N-1) 個、X よりも大きい数字を (N-1) 個使えば条件を満たさないマスを作れる。
    • N^2 個ある数字から、1 + N-1 + N-1 = 2*N - 1個の数字を取ってきて、中央値を X とし、X 未満の数字を同じ列に、X よりも大きい数字を同じ行に配置すれば良さそう。
    • N^2 から 2N - 1 個の数字を取ってくる組み合わせは (N^2)C(2N-1) パターン
    • X を配置するマスの選び方は N^2 マスから 1 個選ぶので (N^2) パターン
    • X 未満の数字を同じ列に配置するのはマス目の数が N-1 個なので (N-1)! パターン
    • X よりも大きい数字を同じ行に配置するのは、同じように (N-1)! パターン
    • 残りの数字を空いたマスに配置するのは、マス目の数が (N-1)*(N-1) = (N-1)^2 なので、((N-1)^2)! パターン
    • よって余事象の数は ↑ のすべてのパターンの掛け合わせなので (N^2)C(2*N-1) * (N^2) * (N-1)! * (N-1)! * ((N-1)^2)!
  • 条件を満たさないマスが複数個あった場合におかしいことになりそう。
    • 条件を満たさないマスは高々 1 個なので大丈夫
    • 上記の条件を満たさないマス以外のマスに数字 Y を置くことを考える。
      • X < Y の時、X と同じ列かつ Y と同じ行の数字を p とすると、X と同じ列に書かれている数字は X 未満なので、p < X < Y となり、Y は条件を満たす。
      • Y < X の時、X と同じ行かつ Y と同じ列の数字を p とすると、X と同じ行に書かれている数字は X よりも大きいので、Y < X < p となり、Y は条件を満たす。

実装

def resolve():
  # 高速な組み合わせ計算
  def comb(N, R, mod):
    if N-R < R: R = N-R

    # 分母を計算
    ans = 1
    for n in range(N-R+1, N+1):
      ans*=n
      if ans > mod: ans%=mod

    # 分子を計算
    den = 1
    for r in range(2, R+1):
      den*=r
      if den > mod: den%=mod

    ans *= pow(den, mod-2, mod)
    return ans%mod

  mod = 998244353
  N = int(input())
  if N == 1:
    print(0)
    return

  # 余事象を求める
  # N**2 個の数字から 2*N-1 個の数字を選ぶ組み合わせ
  comp = comb(N**2, 2*N-1, mod)

  # どのマス目に条件を満たさない X を配置するか選ぶ組み合わせ
  comp = (comp * (N**2))%mod

  # 中央値 X 以外の数字を行と列にそれぞれ配置する組み合わせ。
  # (N-1)! を 2 回かける
  for _ in range(2):
    for n in range(2, N):
      comp *= n
      if comp >= mod: comp %= mod

  # 他の数字を配置する組み合わせ
  for n in range(2, (N-1)**2 + 1):
    comp *= n
    if comp >= mod: comp %= mod
  
  # 全事象は (N**2)!
  all_pattern = 1
  for n in range(2, N**2 + 1):
    all_pattern *= n
    if all_pattern >= mod: all_pattern %= mod

  print((all_pattern - comp)%mod)

resolve()