c_Comp-Prog yukicoder No.532 Possible or Impossible
公式解説より少しだけ簡単な証明を書きたいなーって思ったので
問題
日本語なのでリンク先参照
考察
$ 0 \le M \le N \le 50(ただし$ N \ne 0)なら大抵の場合でできるんじゃないかなーという想像をつけることができるので、どうやって作れるかを確認した。
以下で$ \oplusが出てきた場合、それは$ +もしくは$ \timesのどちらかを任意で選ぶことができると考える。
$ (1)M = 0
$ N \ge 3のときは$ 1 + 2 - 3 = 0であるためそれ以降の$ N-1までの数字を乗算したあと、$ Nを加算することで$ Mを満たすことが可能となり、逆に$ N \lt 3の時は不可能である。
$ (2)$ M \ne 0, N\bmod 2 = 1
$ (1)$ 1\oplus(3-2)\oplus\dots\oplus(N-(N-1))とすることで$ (N+1)/2 \ge Mとなる$ Mを求めることができる。
$ (2)$ N-((2-1)\oplus(4-3)\oplus\dots\oplus((N-1)-(N-2)))とすることで$ N-1 \ge M \ge (N-1)/2となる$ Mを求めることができる。
$ (3)$ N\times((2-1)\times(4-3)\times\dots\times((N-1)-(N-2)))とすることで$ N = Mとなる$ Mを求めることができる。
以上により、$ N \ge M \ge 1となる$ Mに対して成り立つ数式が存在することがわかった。
$ (3)$ M \ne 0, N\bmod 2 = 0
$ (1)$ (2-1)\oplus(4-3)\oplus\dots\oplus(N-(N-1))とすることで$ N/2 \ge Mとなる$ Mを求めることができる。
$ (2)$ N-(1\oplus(3-2)\oplus...\oplus((N-1)-(N-2)))とすることで$ N-1 \ge M \ge N/2となる$ Mを求めることができる。
$ (3)$ N\times(1\oplus(3-2)\times...\times((N-1)-(N-2)))とすることで$ N = Mとなる$ Mを求めることができる。
以上により、$ N \ge M \ge 1となる$ Mに対して成り立つ数式が存在することがわかった。
よって、場合分けは全ての状態を直和の形で分離できているため、式が存在しない場合は$ N < 3, M = 0であることがわかった。
code:solve.cpp
int main(){
int n,m;cin>>n>>m;
if(m==0 && n<3)cout << "Impossible" << endl;
else cout << "Possible" << endl;
}
振り返り
証明か？これ