前回のABCは外出していて参加できなかったので，3週間ぶりの参戦となりました． 今回も感想と反省を書き残しておきます．
レート変化
511→524です．ほぼ誤差の範囲ですが温まりました． 復帰してから±20ぐらいでレートが振動しているので脱却したいところです・・・．
A：Not
0か1が入力xとして与えられて，0がきたら1を，1がきたら0を出力せよという問題． ifでやるか，xorでやるか，!xでやるか，人それぞれだと思いますが， 上位の人を数人見ると全員!xでやっていました． 自分はifで振りましたが，!xは芸術点高いなぁと思いました．簡潔でよい．
B：Product Max
掛け算の最大値を出力する問題． 制約的に全探索は間に合いません． 整数$x,y$の定義域の端同士の掛け算だけして最大値を求めれば十分なことにはすぐ気づきました． （本当に良いかあまりよく考えずに提出したのでちょっと危なかったかも）
ちなみに自分は急ぐあまり，最初は整数$a,b,c,d$の積の最大値を求める問題だと勘違いし， 余計な時間を使ってしまいました． 毎回問題の読み間違いをやってるので気を付けないといけませんね，反省．
C：Ubiquity
最初見た時は高校の数Aじゃんって思いました． 4年前まで現役高校生で，しかも現在塾で高校生を教えているのでこんなのすぐACだわ～って思ってたら甘かったです()
考え方はあっているはずなのになぜかテストケース5つぐらいでWAを発生させ， 結局デバッグコード消し忘れなどのポカをやって6WAしました． 結局終了10分前にACし，ここで終了しました．敗因はMODの扱いです．
この問題のように答えが非常に大きくなる場合， 答えをMOD$＝10^{9}+7$で割って出力するというのは競プロerにはおなじみですが， 自分自身新参者なのであまりこの方法に慣れていませんでした． 答えを出す過程で計算結果を適宜MODで割っていくわけですが， そのMODで割っていって出てきた答えを最後に合算した時， 答えがマイナスで出てくる可能性があることを失念していました．
解説ではこれを回避するために，答えを
ans = (ans+mod)%mod
と修正して出力していました． 自分は合算する度に答えがマイナスになっているときといないときの処理を条件分岐でやっていたので， これを見た時天才かよ！！！って思いました． 確かにこれならプラマイがどうであれ関係ないです．この処理は覚えておこうと思いました．
ちなみにこれDPでも解けるらしいです．時間あったら考えてみたい．
D：Redistribution
またMODで割るやつです． C問題で無限に時間を取られたので本番中はほぼ見てません．
解説を読んだところDPするのが良いみたいです． 「D問題のDはDPのD」という言葉の通りですね．
解説をぱっと読んだ感じ，これだと数が出てくる順番考慮されるんか？？（$(3,4)$と$(4,3)$が区別されて出てくるの？？）って思いましたが， 手動でやってみたらこれでうまくいくことが分かりはえーってなりました．DPすげぇ．(こなみかん)
DPってどういう漸化式を立てるかが勝負だと思うので， 解説読んじゃうとダメな気がするんですよね． 解説を読むとただそれに従ってDPを回すだけになっちゃうのであまり意味を感じないというか・・・． （確かに実装できることも大事だと思っていますが・・・）
E：Dist Max
座標が$N$点与えられて，それらのマンハッタン距離の最大値を求める，という問題． どうやらマンハッタン距離の問題は45度回転という頻出テクニックがあるようです．（そんなの知らん）
式変形は省略しますが（書くのがめちゃめちゃめんd(ry），$i$番目の点$(x_i , y_i)$について$z_i=x_i+y_i$ ，$w_i=x_i-y_i$という座標変換を施すことで， $m$番目の点と$n$番目の点のマンハッタン距離は $$max(|z_m-z_n| , |w_m-w_n|)$$ となります．
以上より$z_i=x_i+y_i$ ，$w_i=x_i-y_i$の最大値及び最小値をそれぞれ求めてあげれば，マンハッタン距離の最大値が求まります． $N$点について$z_i$と$w_i$を求めればよいので，計算量は$O(N)$となり間に合います．
マンハッタン距離については，このページを参考にしました． ↓ kagamiz.hatenablog.com
まぁ知ってれば数分で実装できますが，知らないと無理ですな．
最後に
今回も経験のなさが露呈してしまいました，はい． MODの扱いについては収穫あったかなって感じです． 過去のABCにバーチャル参加して精進しようと思います．
