physics0523's 精進ログ

主に競プロの面白い問題の解法をメモします

AquaMoon and Wrong Coordinate(CFR732Div1-D)

Problem - D - Codeforces

問題概要

以下の方法で、全ての要素が $1$ 以上 $10^6$ 以下の整数である $k \times m $ 行列 $A$ を作成する。(ただし、添え字は 0-indexed とする)

  1.  全ての $0 \le j < m $ について、 $A$ の $j$ 列目を、全ての項が $1$ 以上 $10^6$ 以下の等差数列とする。
  2.  全ての $0 \le i < k$ について、 $A$ の $i$ 行目を任意に並べ替える。
  3. $0 \le p < k, 0 \le q < m $ を満たす整数組 $(p,q)$ を任意に選ぶ。そして、 $s=A_{p,q}$ として記録しておき、 $A_{p,q}$ を $s$ 以外の整数 $t$ に置き換える。

作成後の行列が与えられるので、 $p,s$ を特定せよ。

 

$5 \le m \le 1000, 7 \le k \le 1000$

実はこの問題にはdiff3000が付いています。こんな簡単な、いや、こんな簡単に題意が理解できる問題が解けるだけでLGMなのです。解法を聞いたらめちゃくちゃ納得できるし当たり前にすら聞こえるのに、この解法が見えなかった、これぞ僕が望む競プロでの分からせられ方なのです。ある種の感動さえ覚えました。

 

まず、自明な観察として、 $p$ はすぐに特定できます。 方法としては、行に含まれる値の総和は (だいたい) 等差数列になりますが、必ず公差が乱れるところが $1$ 箇所か $2$ 箇所発生することがわかります。理由は等差数列からちょうど $1$ 項選んで違う値に編集することを考えると自明でしょう。 $7 \le k$ であることに注意すると、乱れた位置は容易に特定可能です。

 

ここまでは誰でも辿り着く範囲だと思いますが、ここからが本当の勝負どころです。

実は、等差数列の乱れからわかるものは、 $p$ の値だけではありません。(等差数列の本来の項)-(乱れた項) は $(s-t)$ と一致します。これで自由度が $1$ 落ちました。

あと $1$ つ自由度を落とせば $s$ の特定が可能なのですが、どうすればよいでしょうか?

先ほどやったことをもう少しよく観察しましょう。

等差数列 $(Ck + D)$ の公差はある定数 $C$ となる。ゆえに、等差数列をいくつか足し込んだ数列の公差も何らかの定数 $C'$ となる。つまり、等差数列をいくつか足し込んだ数列は $k$ に関する一次式(即ち、等差数列)になるはずである。 

この文章を少しいじくってみます。

等差数列 $(Ck + D)$ の隣接項の二乗の差はある $k$ に関する一次式 $2C^2k + (C^2+2CD)$ となる。これを $Ek+F$ とおく。このとき、差数列の各項を二乗した数列をいくつか足し込んだ数列の公差も何らかの一次式 $E'k+F'$ となる。つまり、等差数列の各項を二乗した数列をいくつか足し込んだ数列の一般項は $k$ に関する二次式で表されるはずである。 

証明は省略しますが、これは正しい事実です。ざっくり理解するなら積分のイメージでよいです。

つまり、適当に $3$ 項選んで二次式を補間してやれば、$p$ 行について、(本来の項の二乗和)-($A$ の $p$ 行の項の二乗和) が求まります。

ぱっと見「これの何が嬉しいねん…」と思いましたが、ここからがはっとするところ。

実はこの差は他でもない $s^2-t^2$ なのです。

ここで、 $(s-t)$ 、 $(s^2-t^2)$ の双方が分かったことは、とても喜ばしいことです。

$(s-t) = X$

$(s^2-t^2) = Y$

とすると、 $(s^2-t^2)=(s+t)(s-t)$ より

$(s+t)=Y/X$

なんと和差算になってしまいました。 ここまで来れば $s$ も特定するととが出来ます。めでたしめでたし。

等差数列での議論があまりに自明であるからその議論が拡張できることに気づきづらく、ドツボにハマってしまう問題なのかな…と思います。いや~、この問題に負かされるのは本当に爽快だなぁ…というお気持ちです。

 

補足 : 多項式補間がmodじゃないのでけっこう心臓に悪いのですが、補間するべき値が高々 $10^{15}$ とかで、和差算に直す段階で割り算の処理も入るので、 $(s+t)$ を復元するのには long double を使えばなんか大丈夫でした(ホンマか?)

Submission #122556490 - Codeforces