Xmas Contest 2018 C: CombinatioN 解説

Xmas Contest 2018

https://atcoder.jp/contests/xmascon18/tasks/xmascon18_c

問題概要

Pascal の三角形を書こうとしたが，ある場所で足し算を大きい値に間違えてしまった (→間違いがそこから伝搬)．そして一部消えてしまった．というものが与えられるので，間違えた場所を特定せよ．

部分点解法

(i, j) で間違えて x 大きい値を書いてしまったときの影響を考えると， l \ge j かつ k - l \ge i - j を満たす (k, l) のところが \binom{k - i}{l - j} x だけ大きくなることがわかります．

これを用いると，すべての (i, j) を間違えた場所の候補として，与えられた条件がすべて満たされているか調べる，という解法が得られます (増えているところの情報から x の値を求めて，複数個になったらダメ)． O(N^4) 時間になります．

解法 1

制約をよく見ると，消えずに残っている値は 10^9 以下と書いてあります．ということは，正しい値以上が書いてある場所は \binom{i}{j} \le 10^9 なところしかありません．これは N^2 よりだいぶ少なくて， N = 500 では 4600 箇所です．

大きい方にしか間違えないので，正しい値未満が書いてあったら IMPOSSIBLE です．これで弾かれなければ，部分点解法で間違えた場所 (i, j) を決め打ったあと調べる箇所が 500^2 から 4600 になるので，間に合うかもしれない気がしてきます．実際，実装の定数倍や言語次第かもしれません．

もう少し速くするには，間違えた場所の候補 (i, j) を試すとき， \binom{i}{j} > 10^9 なら間違えても情報が出てこない，ということを用います．まとめるとこんな感じ：

正しい値未満が書いてあったら IMPOSSIBLE
foreach (i, j):
  if check(i, j):
    (i, j) を答えの候補に追加
答えの候補が 0 個なら IMPOSSIBLE，1 個ならそれを出力，2 個以上なら AMBIGUOUS

function check(i, j):
  if C[i][j] > 10^9:
    正しい値より大きい値が書いてあれば return false  // これは前計算しておく
    return true
  foreach 何か書いてある (k, l):
    if k >= i and l >= j:
      x := (A[k][l] - C[k][l]) / C[k - i][l - j]
      x が正の整数でなければ return false
      x を x の候補に追加
    else:
      A[k][l] = C[k][l] でなければ return false
  x の候補が 2 個以上なら return false
  return true

これなら一番計算が重い部分が 4600^2 で，無事間に合います．

解法 2

正しい値より大きい値が書いてある場所 (k, l) をひとつ決めると，間違えた量 x は A_{k,l} - \binom{k}{l} の約数なので，それをすべて試します．正しい値より大きい値が書いてあるという情報から，間違えた場所 (i, j) がどんどん絞られていきます．というのも， \binom{i-k}{j-l} の値から i-k と j-l がほぼ決定されるからです ( 1 のときを除いて，最大 6 通りしかないようです)．

計算量のボトルネックは， 4600 \times (約数の個数) とかになります．実装は結構大変かもしれません．さらに，AMBIGUOUS 等の判定で間違えがちです：例えば，一番下の段でひとつだけ消えていて，他が全部正しいとき，正しい値しか書いていないですが間違えた場所は一意に特定されます．

コメント

適当に問題設定を考えついて，最初は約数を調べる解法を思いついて適当に投下したのですが，snuke さんがすぐに言ってきた素直に全箇所調べる解法が十分速いことに気づき，簡単めでいいかな～と思って採用されました．しかしはまりがちポイントが大量にあることが徐々に発覚し，綺麗な実装ができますかという問題に．一発で通せた方はすごい！