AtCoder Grand Contest 063 C
(工事中)
解き方
解説（公式）の前提に記載されている通り、操作前に$ A_{i} = A_{j} 解説（公式）の前提に記載されている通り、ある2つの$ N 以下の正整数$ i と$ j について、操作前に$ A_{i} = A_{j} の場合を考える。 このとき、
解説（公式）の前提に記載されている通り、ある2つの$ N 以下の正整数$ i と$ j について、操作前に$ A_{i} = A_{j} である場合を考える。 このとき、どのような操作を行ったとしても、操作後も明らかに$ A_{i} = A_{j} が成り立つ。
解説（公式）の前提に記載されている通り、ある$ N 以下の正整数$ i と$ j について、操作前に$ A_{i} = A_{j} である場合を考える。 このとき、どのような操作を行ったとしても、常に$ A_{i} = A_{j} が成り立つため、$ A が$ B
このとき、どのような操作を行ったとしても、常に$ A_{i} = A_{j} が成り立つため、$ A を$ B に一致させられるためには$ B_{i} = B_{j} が必要である。
このとき、どのような操作を行っても常に$ A_{i} = A_{j} が成り立つため、$ A を$ B に一致させられるためには$ B_{i} = B_{j} が必要である。
つまり、$ A_{i} = A_{j} かつ$ B_{i} \neq B_{j} となるような$ N 以下の正整数$ i と$ j が存在するならば、答えはNoである。
逆に、$ N 以下の任意の正整数$ i と$ j について、$ A_{i} = A_{j} \implies B_{i} = B_{j} が成り立つならば、実は$ A を$ B に一致させられる。
以下では、この前提のもとで、具体的に$ A を$ B に一致させるための操作手順を構成することで、この事実を示す。
簡単のため、数列$ A の中に同じ数が
簡単のため、数列$ A の中に同じ数が複数含まれることはない、すなわち、数列$ A に含まれる数は全て異なると仮定する。
前提により、ある2つの$ N 以下の正整数$ i と$ j について$ A_{i} = A_{j} だとすると、$ B_{i} = B_{j} である。
簡単のため、（操作前の）数列$ A の中に同じ数が複数含まれることはない、すなわち、数列$ A に含まれる数は全て異なると仮定する。
つまり、$ i と$ j を区別する必要はないため、これらをまとめて１つの添字とみなすことで
もし、ある2つの$ N 以下の正整数$ i と$ j について$ A_{i} = A_{j} だった場合、上の前提により、$ B_{i} = B_{j} である。
つまり、$ i と$ j を区別する必要はないため、これらをまとめて１つの添字とみなすことで数列$ A に含まれる数は全て異なると考えることができる。
つまり、$ i と$ j に違いはないため、これらをまとめて１つの添字とみなすことで数列$ A に含まれる数は全て異なると考える。
また、ある操作を行った後の各項の値に並び順は影響しないため、数列$ A が降順に並んでいるとしても一般性を失わない。
以上より、（操作を行う前の）数列$ A は狭義単調減少の非負数列であるという仮定のもとで以降は考える。
ここで、$ B の任意の項より大きく、
ここで$ Y を、$ B の任意の項より大きく、$ NY \lt 10^{18} を満たす正整数であるとする。
この問題の制約において、このような正整数$ Y が存在することは明らかである。
例えば、下の回答例では$ Y にあたる値として、適当に$ 10^{12} を使用しているが、特にこの値である必要はない。
この$ Y は、手順の一番最後の操作において、$ y の値として
この$ Y の条件は、手順の一番最後の操作において、$ y の値として$ Y を選ぶことを意図して設定している。
最後の操作で$ y の値として$ Y を選ぶことを考えると、$ B の各項は$ Y で割ったあまりであるため、$ Y は$ B の各項より大きい必要がある。
最後の操作で$ y の値として$ Y を選ぶためには、
最後の操作で$ y の値として$ Y を選ぶことを考えると、$ B の各項は$ Y で割ったあまりであるため、$ Y は$ B の各項より大きい。
$ Y が$ B の各項より大きければ、$ B の各項は$ Y で割ったときのあまりに成り得るため、$ Y が最後の操作の$ y の値として使用できる。
手順の一番最後の操作において$ y の値として$ Y を選ぶとしたとき、その操作の直前がどのような状態であるべきかを考える。
$ N-1 以下の任意の正整数$ i について、ある$ x が存在して$ A_{i}+x \equiv B_{i} かつ$ A_{i+1}+x \equiv B_{i+1} である必要がある。
これはつまり、$ A_{i+1}-A_{i}
操作後に$ B に一致するため、$ N 以下の任意の正整数$ i について、ある$ x が存在して$ A_{i}+x \equiv B_{i} \mod Y である必要がある。
よって$ N-1 以下の任意の正整数$ i について、$ A_{i}+x \equiv B_{i} \mod Y かつ$ A_{i+1}+x \equiv B_{i+1} \mod Y である。
これはつまり、$ N-1 以下の任意の正整数$ i について$ A_{i+1} - A{i} \equiv B_{i+1} - B_{i} が必要なことを表す。
操作後に$ B に一致するため、$ N-1 以下の任意の正整数$ i について、$ A_{i+1} - A_{i} \equiv B_{i+1} - B_{i} \mod Y が必要である。
逆に、上が成り立てば、$ x の値を適切に選ぶことで、操作後に$ B に一致させることができることがわかる。
よって、最後の操作までに、$ N-1 以下の正整数$ i それぞれについて、$ A_{i+1} - A_{i} の値を調整することを考える。
よって、最後の操作までに、$ N-1 以下の正整数$ i それぞれについて、$ A_{i+1} - A_{i} の値を調整することを考えれば良い。
よって、最後の操作までに、$ N-1 以下の正整数$ i それぞれについて、$ A_{i+1} - A_{i} の値を調整することを考える。
操作は最大$ N 回だけ許されているため、単純に考えて、$ N-1 以下の正整数$ i それぞれについて上の調整を$ 1 回で行いたい。
ここで気になっているのが、一度調整した間隔が、その後の操作によって崩される場合があるということ。
ここで気になっってくるのが、ある$ i について間隔を調整できたとしても、その後の操作で間隔が変わってしまう可能性があること。
つまり、すでに調整した間隔を変えないような操作ができないのか、ということが次に考えたくなってくる。
そして、実は操作の順番などを工夫すれば、このような操作が可能であることがわかる。
ここで重要になってくる事実は、ある正整数$ y と、それ未満の非負整数$ x について、$ x を$ y で割ったあまりを考えても、それは$ x と変わらないということ。
ここで重要になってくる事実は、ある正整数$ y で割ったあまりに置き換える操作で変化しないのは、対象が$ y 未満の非負整数である場合ということ。
ここで重要になってくる事実は、ある正整数$ y で割ったあまりに置き換える操作で$ y 未満の非負整数は変化しないということ。
つまり、$ A_{i}+x や$ A_{i+1}+x より大きい値を$ y として選べば、操作前後で$ A_{i+1}-A_{i} が変わらないようにできる。
このことから、$ A の中の要素のうち大きいものから順に着目して操作を行いたくなる。（そのため狭義単調減少と仮定した）
以上が、この解き方のもととなるアイディアであり、以下では具体的な方法を考えていく。
まず$ N=1 の場合を考えると、これは間隔の調整が不要であるため、最後の操作のみを行えばよい。
具体的には、$ x \equiv B_{1}-A_{1} \mod Y を満たすような$ Y 未満の値を$ x として選び、$ y としては$ Y を選べば良い。
次に$ N \gt 1 の場合を考えるが、まずは$ N+1 回の操作が必要な次のような方法を考える。
まず$ x の値として$ 1 を、$ y の値として$ A_{1}+1 を選び、操作を行う。
まず$ x の値として$ 1 を、$ y の値として$ A_{1}+1 を選び、操作を行う。
$ N \gt 1 かつ$ A が狭義単調減少であることから$ A_{1} \gt 0 であるため、$ x \lt y となることが保証される。
よって、このような操作は可能であり、これにより$ A_{1} は$ 0 となり、それ以外の項は$ 1 だけ加算される。
※ $ x の値として$ 1 を選んだが、この値に特に意味はない。ただ、$ 0 とするとうまくいかない場合があるため、この記事では$ 1 とした。
次に$ i の値を$ 1 から$ N-1 に順に動かしながら以下の操作を行う。
$ x \equiv B_{i}-B_{i+1} \mod Y を満たす$ Y 未満の値を$ x として選び、$ y の値として$ A_{i+1}+x をえらび、操作を行う。
この操作の前に$ A_{i} は$ 0 となてちるはずなので
この操作の前に$ A_{i} は$ 0 となっているはずなので、この操作により$ A_{i} \equiv B_{i}-B_{i+1} となる。
また、この操作により明らかに$ A_{i+1} は$ 0 となるため、結果として
この操作の前に$ A_{i} は$ 0 となっているはずなので、この操作により$ A_{i} \equiv B_{i}-B_{i+1} \mod Y となる。
また、この操作により明らかに$ A_{i+1} は$ 0 となるため、結果として$ A_{i+1} - A_{i} \equiv B_{i+1} - B_{i} \mod Y となる。
それ以外の項は操作前において$ A_{i+1} 未満であるはずのため、この操作では単に$ x だけ加算されるだけである。
つまり、この操作の前までに調整した間隔は保存される。
ちなみに、最初の操作で$ x に$ 1 を選んだため、この操作の前の時点で$ A_{i+1} は必ず正となっている。
これにより、$ x \lt y であることが保証でき、この操作を行うことが常に可能となる。
最後に、$ N = 1
最後に、$ N = 1 の場合と同じ要領で最後の操作を行えば、$ A を$ B に一致させることができる。
以上より、$ N+1 回の操作で$ A を$ B に一致させる手順を構成することができた。
この問題で求められているのは、$ N 回以内の操作で$ A を$ B に一致させる手順であるため、上の方法を改善し、操作回数を$ N 会に減らすことを考える
この問題で求められているのは、$ N 回以内の操作で$ A を$ B に一致させる手順であるため、上の方法から操作を$ 1 回減らせないか考える。
この問題では$ N 回以内の操作で$ A を$ B に一致させる手順を求められているため、上の方法から操作を$ 1 回減らせないか考える。
ここで、上の手順の各操作を思い返すと、$ 1 回目の操作は
ここで、上の手順の各操作を思い返すと、$ 1 回目の操作は$ A_{1} を$ 0 にするための操作で、間隔の調整を行っていない。
ここで、上の手順の各操作を思い返すと、$ 1 回目の操作は$ A_{1} を$ 0 にするためだけの操作で、間隔の調整に何も貢献していない。
$ 1 回目の操作は$ x の値の選び方に自由度があるため、$ x を適切に選ぶことで、後続の作業を省略するような調整ができないか考える。
$ 1 回目の操作は$ x の値の選び方に自由度があるため、$ x の値を調整することで後続の操作を省略できないか考える。
次に、事前に調整しておくことで省略できそうな操作があるか考える。
$ 2 回目から$ N-1 回目の操作は後続の手順に影響があり、最後の$ N+1 回目の操作も必要であるため、省略するなら$ N 回目の操作と思われる。
$ 2 回目から$ N-1 回目の操作は後続の手順に影響があり、最後の$ N+1 回目の操作も省略することは難しい。
よって、省略するとすれば$ N 回目の操作と思われるため、どのような状態であれば$ N 回目の操作が省略できるか考える。
$ N 回目の操作で行っているのは、$ A_{N} と$ A_{N-1} の間隔の調整である。
よって、$ N 回目の操作を行う直前の時点で、$ A_{N}-A_{N-1} \equiv B_{N}-B_{N-1} \mod Y となっていれば、$ N 回目の操作を省略できる。
よって、$ N 回目の操作の直前に、$ A_{N}-A_{N-1} \equiv B_{N}-B_{N-1} \mod Y となっていれば、$ N 回目の操作を省略できる。
以上より、$ 1 回目の$ x の値を適切に選ぶことで、$ N 回目の操作の直前に上記の状態になっているようにできれば良い。
$ 2 回目から$ N-1 回目で$ x として選ばれる値は、$ 1 回目に$ x として選んだ値が何であっても変わらない。
$ 2 回目から$ N-1 回目で$ x として選ばれる値は、$ 1 回目に$ x として選んだ値に依存しない固定の値である。
つまり、$ 1 回目に$ x として選ぶ値を増減させれば、その分だけ$ N 回目の操作の直前の$ A_{N} の値を増減させられる。
よって、$ 1 回目に$ x の値を適切に選ぶことで、$ N 回目の操作を省略でき、それにより$ N
ここで、$ 2 回目から$ N-1 回目で$ x として選ばれる値は、$ 1 回目に$ x として選んだ値に依存しない固定の値である。
つまり、$ 1 回目に$ x として選ぶ値を増減させれば、その分だけ$ N 回目の操作の直前の$ A_{N} の値を増減させられる。
よって、$ 1 回目の操作の$ x の値を適切に選ぶことで、$ N 回の操作で$ A を$ B に一致させられることがわかった。
下の回答例では、とりあえず$ 1 回目の$ x の値を$ 0 にして実際に手順を進め、$ A_{N} がどのような値になるか確認する方法を採っている。
また、$ 1 回目の$ x の値を適切に選び$ N 回目の操作を省略するというのは、次のように考えることもできる。
これまでの議論で$ A_{N} として扱っていた項を$ A_{1} として扱い、最初の$ A の時点で$ 1 回目の操作が完了済みと看做す。
これにより、$ 1 回目の操作が不要となるため、必要な操作を$ N 回に減らすことができる。
最初に書いた手順の$ 1 回目の操作完了後と異なり、最小値が$ 0 となっていないが、間隔の調整は同様に可能である。
つまり、上に書いた$ 1 回目の操作は、$ A_{1} と$ A_{N} の間隔を調整していると考えることができる。
そのため、下の回答例のように、試しに手順を実行してみて$ A_{N} をどれだけ調整するべきか確認する必要はない。
$ 1 回目の操作後に$ A_{1}-A_{N} \equiv B_{1}-B_{N} \mod Y となるように$ x の値を選べば良い。
下のは$ 1 回目の操作の$ x の値を$ 0 にして〜〜〜の下に入れる
最後に、この手順が許されているか、つまりこれらの操作で選んだ$ x と$ y の値が条件を満たしているかを確認する。
途中にも記載した通り、各操作において$ x \lt y となることは保証できているため、最後に$ y \le 10^{18} であるか確認する。
各操作の$ x の値は$ Y 未満とすることができるため、$ N-1 回目までの操作の$ y の値は$ y \lt A_{i}+Y \times i を満たす。
ただし、$ i は$ 1 以上$ N - 1 以下の任意の整数である。
$ NY \lt 10^{18} を満たすように$ Y の値をとっていることと、$ A に関する制約から、$ y \le 10^{18} を満たすことがわかる。
解答例
下は上記の方法で解いたときの提出結果である。また、その提出の際に提出したソースコードをその下に転記する。
code: C
int cmp_ll_rev (const void *ap, const void *bp) {
long long a = *(long long *)ap;
long long b = *(long long *)bp;
if (a < b) {
return 1;
}
if (a > b) {
return -1;
}
return 0;
}
int main () {
int n = 0;
int res = 0;
int anscnt = 0;
long long pow10 = 1000000000000LL;
int is_ng = 0;
long long ab_org10002 = {}; long long gap = 0LL;
res = scanf("%d", &n);
for (int i = 0; i < n; i++) {
res = scanf("%lld", abi); }
for (int i = 0; i < n; i++) {
res = scanf("%lld", abi+1); }
if (n <= 1) {
printf("Yes\n");
printf("0\n");
} else if (ab00 < ab01) { printf("1\n%lld %lld\n", ab01-ab00, pow10); } else {
printf("1\n%lld %lld\n", pow10+ab01-ab00, pow10); }
return 0;
}
qsort(ab, n, sizeof(long long)*2, cmp_ll_rev);
for (int i = 1; i < n; i++) {
is_ng = 1;
}
}
if (is_ng > 0) {
printf("No\n");
return 0;
}
anscnt++;
for (int i = 1; i < n; i++) {
}
}
for (int i = 1; i < n-1; i++) {
long long x = 0LL;
long long y = 0LL;
} else {
}
for (int j = 0; j < n; j++) {
}
anscnt++;
}
}
if (anscnt < n-1) {
long long x = 0LL;
long long y = 0LL;
} else {
}
if (x < y) {
for (int j = 0; j < n; j++) {
}
anscnt++;
}
anscnt++;
printf("Yes\n");
printf("%d\n", anscnt);
for (int i = 0; i < anscnt; i++) {
printf("%lld %lld\n", ansi0, ansi1); }
return 0;
}
anscnt = 0;
for (int i = 0; i < n; i++) {
}
qsort(ab, n, sizeof(long long)*2, cmp_ll_rev);
anscnt++;
for (int i = 1; i < n; i++) {
}
for (int i = 1; i < n-1; i++) {
long long x = 0LL;
long long y = 0LL;
} else {
}
for (int j = 0; j < n; j++) {
}
anscnt++;
}
}
anscnt++;
for (int i = 0; i < n; i++) {
}
printf("Yes\n");
printf("%d\n", anscnt);
for (int i = 0; i < anscnt; i++) {
printf("%lld %lld\n", ansi0, ansi1); }
return 0;
}
感想