おはようございます。しほみんです。
前回に引き続きABC171を振り返ります。F問題振り返っている時間なかったので、省きます。コードは金曜日あげます。
んまあ今回のD,Eは知っていれば割と問題なく解けたので両方抑えてはおきたいです。
地味にこの解説を書いていると理解できている範囲と理解できていない範囲が明確化しますね。おとといのC問題はちょっとあいまいでしたし。こういう復習悪くないと思います。
D問題
N個の正の整数列A1,A2,....,Anがあります。
これにQ回操作を続けて行います。
i回目の操作ではBiである要素がすべてCiになる。
このとき、i回目の操作後の要素の和を出力しなさい。
とりあえず、何回かD問題を触れていると、問題文通り実装すると時間がかかるとわかります。
Biをいちいち数列で見つけてCiに置き換える。そのあと、和を求めるではo(NQ)となってしまって、とんでもない時間がかかります。
ここでは、まず基本的な発想はから振り返ってみましょう。
＜基本的な発想＞
1. 左から見ていったときに、何かしらの別情報に変換する。
2. 該当するものを見たとき、前の保持情報から条件を満たすか確認。満たすときは、情報を追加または変更する。満たさないときは無視する。
3. 確認し終わったら結果を出す。
1.として考えると、数列を何かの情報にできないか考えます。
今回操作はBiをCiにするです。つまり、1回の操作では高々1つ数字だけが変わります。
となると、1回の情報ごとで数列全部の値を見る必要がなく、そのBiはいくつあるか？そして、何個Ciになるか？だけわかればよくなります。
つまり、数列の取りうる数だけの配列を用意して、要素のどれがいくつあるか見ればよいです。
例えば、1,2,4,1,1,3だったら、1が3つ、2,3,4が1つずつあるので
a[1] = 3,a[2] = 1,a[3] =1,a[4]=1として、入れておけばよいです。
そうすれば、一回の動作ではa[Bi]の個数を見ればよく、そのあと、a[Ci]にはa[Bi]分足せばよいのです。（これが2の部分ですね）
後は和ですが、i×a[i]なのでいちいち足してもよいですが、これも1回の操作ごとにo(200000)となり、時間がかかりすぎちゃいます。
なので、和の計算も工夫が必要です。
これも同じで、1回の計算で(Ci-Bi)×a[Bi]だけ和が変わることに注目します。
つまり、最初に配列を作った後、その和も作っておけば、一回の操作では上記の式で変形すればよいです。
これで、1回の操作の時間はo(1)となり、o(Q)で処理できるので、間に合います。
まとめると、
1.数列を要素の要素数の配列に置き換える。また、数列の和を求めておく。
2.和は(Ci-Bi)×a[Bi]を足して、出力。
3,a[Ci]にa[Bi]分足し合わせて格納（a[Ci] += a[Bi]）
4. 1-3をQ回繰り返す。
E問題
猫がN匹（偶数）います。それぞれの猫には整数が書かれています。
猫たちはxorを計算したかったので、自分以外の猫のもつ整数のxorを求めました。
このとき、それぞれの猫の整数を求めなさい。
典型問題らしいですが、排他的論理和を知っていれば問題を知らなくても導出は難しくないです。排他的論理和が分からないと厳しいかなって感じです....。
排他的論理和について
AとBを2進数で表しそれぞれの桁を見たとき、2つとも同じ数なら0、そうでなければ1とします。
例えば、4+5なら100+101となり、001で、1となります。
今回知っているべき知識はこれです。（排他的論理和は便宜上+で表します）
・排他的論理和は交換法則が成り立つ。A+(B+C) = (A+B)+C
・A+A = 0である。
まずは、猫が求めた排他的論理和をai,それぞれの猫の整数をbiとします。
するとaiはbi（i = 1 ~ N、ただしi = iを除く）の和です。
ここで、S=a1+a2+a3+....+anを考えます（+は排他的論理和）。
このとき、biでの表記を考えると、実は、biはすべてN-1回出てきます。交換法則が成り立つので好きなように動かせます。
よって、A+A=0という法則と、N-1は奇数から、
S=b1+b2+b3+...+bnが成り立ちます。
最後に、a1+Sを考えます。
このとき、a1はb2からbnまでを持っています。
よって、a1+Sはb1が1つ、b2からbnまでを2つずつ持った排他的論理和になります。
後ろの項は消えるので、a1+S=b1となります。
よってまとめると、
1, 入力数列の排他的論理和を求める。（Sとする）
2, aiとSの排他的論理和をもとめて出力で終わりです。
ちなみにAとBの排他的論理和はA^Bで求められます。
最後に....
正直Cに比べたら、DとEの方が気が付きやすいセットだったなあって感じです。
数学が苦手でもDをきちんと押さえていけばそこまで大失敗でもないのかなあって感じです。まあそこばかりは慣れかもです。
ではでは。
