2020年 11月 10日
まえがき
俺もお前もみんなタイヤ
今日は，友達に何かお勧めの曲ある？って聞いて教えてもらった曲やで
本文
競プロ最高，大学カス！
解いたモンダイたち
ABC083 D- Wide Flip
- [考えるな，感じろ,解説神,区間操作]
解説が神です． s[i] != s[i+1] のとき，Sを'00000...0'に変える仮定のどっかしらで必ずs[i]は変えるがs[i+1]は変えない．(もしくはその逆)の操作を行わないと行けない.
s[i]とs[i+1]を常に一緒にヒックリ返していたら，いつまでたっても10,01のままで目的を達成できないにきあです！！
よって，s[i] != s[i+1]となるようなiを見つけたとき，s[i]は変えるけれどs[i+1]は変えないような区間のうち，区間の長さが最大のものは，s[0] ~ s[i]を反転させる操作で，この時の区間の長さはi+1です．
逆に,s[i]は変えないけどs[i+1]は変えるような操作で区間の長さが最大となるものは，s[i+1]からs[n-1]までを変える操作で，(n = s.size());このときの長さは,(n-1)-(i+1)+1 = n-i-1です
この，(i+1)と(n-i-1)を比較して，大きい方を使って反転させるほうがお得です．
この大きい方をb_iとでもテキトウにしておきますか．
つまり，b_iは，s[i] != s[i+1]のときに考えられる反転操作で区間の長さを可能な限り大きくしたもの.です
まぁ，何か簡単のため（？）に，s[i] == s[i+1] のときは b_i = INFとでもしておきましょうか．
そうすると，出力する答えは b_0, b_1, b_2, ..., b_n-1のうち最小の物となります(ﾎﾟﾔｰ)
ABC066 D-11
- [ncm,包除原理(とまでは言わない?)]
まず,答えに影響するのは，a[i] == a[j] (i != j)となるようなa[i]という値ではなく，
iとjの値です．
どの数字が2つあるかっていうのは興味がなくて，同じ数字が，どれくらい離れた距離にでてくるのかということにしか興味がありません．
まぁ，どうにかして2つの被ってる値の距離を求めて，その2つの間にある数字の数を mid としましょう
(つまり, a[i], a[i+1], a[i+2], ... , a[i+mid], a[j] です(j-i-1がmid);
さて，ここまで書いた上で投げやりですが，解説PDFが分かりやすいのでこれを読んでください．
ちなみに，なんの数字が被っている．というのは実は簡単に知ることができます．
sum = a_0 + a_1 + ... + a_n;とすると，
sum - (n * (n+1) / 2) の計算結果の値が2つでてきています．
ABC005 D-おいしいたこ焼きの焼き方
- [たこ焼きのタコは食べれる,二次元累積和,実装神]
某んちょんさんのコードを写経しました．
コード
何が素晴らしいかって，面積vを0〜n * n でループを回すんじゃなくて，長方形の左上と右下（伝われ！）の4点を4重ループで回して，x1,x2,y1,y2を決めて,その時の面積を求めることで val[v]を更新する．っていうところがイケメンだなって思いました．
さて，二次元累積和って難しいですよね
ABC086 D-Checker
- [二次元累積和,反転GG,条件の変換,激難,市松お粗末]
困りました，このモンダイについての考察は大嘘を含んでいます．見るな
このモンダイ，まだ自力できてないけどニャン
何が感動するかって，(2 * k) * (2 * k)のサイズしか考えなくて良くなることもそうなんだけど，
白がx[i] , y[i]にあるっていう条件は，黒がx[i]+k, y[i]にある (もしくはx[i],y[i]+k)っていうのと同値であると変形できるんす！！
(すげー)
もう一個同値としては，x[i], y[i]に黒があるっていう条件は， x[i] - 2k, y[i]に黒があるっていう条件と一緒(y[i] - 2kでも良い)ってことなんすね〜〜.
つまりx[i], y[i] 黒 -> x[i]%2k, y[i]%2k 黒 って変換をしちゃおうってね！
こっから先の二次元累積和は，難しい．また今度．
ABC155 D-Pairs
- [二分探索，lower_bound, upper_bound, 二分探索の自力実装,むずかしめ，条件の言い換え]
解説動画からの引用的な雑書きになる．
K番目に来る数をxとすると, xはx未満の数がK個未満であるもののうち，最大の値と言い換えることができます．
たとえば，1,2,3,3,4,5,6 っていうのが遭って，K = 2だとしよう
x未満の数がK個未満であるもののうち，最大の値という条件を見ていこう！
K = 2 だよ
1は，1未満（0以下)の数が0個(< K)なのでOK
2は2未満(1以下)の数が1個(< K) なので OK
3は,3未満(2以下)の数が2個( == K) なので NG
よって，条件を満たすものの最大の値は2で,実際の答えも2です
次に,K=3のとき(もう一回数列貼っておくね)
1,2,3,3,4,5,6
1は1未満（0以下)の数が0個(< K)なのでOK
2は2未満(1以下)の数が1個(< K) なので OK
3は3未満(2以下)の数が2個(< K) なので OK
4は4未満(3以下)の数が4個(>= K) なので NG
よって，条件を満たすものの最大の値は3で，実際の答えも3だからOK~~
とまあ，この条件の言い換えが重要で，x未満の数がK個未満であるもののうち，最大の値という条件には単調性が生まれるんですよね（日本語知らん)， X < Y のとき，Yが条件を満たしていたら,Xも条件を満たしているんですよね
天才かよ．と思いました．
後は，x未満の数が何個あるか数えるパートですね．
これは，a_0 からa_1, ... ,a_nに対してそれぞれ何個あるかの和を求めます．
今,a_iについてa_i * a_j < x となるようなjの最大値を知りたいです!!
一回簡単のためにa_iは正の数としておきましょう．あ，あと数列aはソート済みってことにしといて．
はいじゃあ，a_i * hoge < x のとき，式変形をして
hoge < x / a_i ですね
つまり，x/a_i は条件を満たしてくれる，そして， x/a_i + 1 は条件(a_iとの積 < x)を満たしてくれません
x/a_i + 1 = searchとでも置いておきましょう．
はい．今，aがソート済みであるとき， search以上の値が最初に出てくる位置，はlower_boundを用いて求めることができますね．
これで，a_iに対して a_i * hoge < x となるhogeが何個あるかは求めることができます．
lower_boundで求まった位置をjとすると，a[j-1]までならa_i * a[j-1] < x なので，hogeはj個あります．
iを0からn_1までやって，hogeが合計何個あるかをtmp個としましょう
この時tmp < K だったら，xはx未満の数がK個未満であるものです．
ハイ次，さっきは，aが全て正の数だと言っていましたが，aに負の値が含まれているときを考えよう．
-5,-3, -3, -2, -1, -1, 0, 4 , 5 みたいなときや
まぁなんかテキトウに，x = 11とでもして a_0=-5)に対して，a_0 との積が11未満になるものの数を数えよう．
これをさっきと同じふうに search = (x/a_i + 1)としてしまうと，search = (11/(-5) + 1) = -1?になります(負の値の除算分からん)で，正の値のときと同じように，search以上の値が最初に出てくる位置(j)を求めると, j = 3 と出てきますね(a_j = -1)
でもでもでもでも，さっき(aが正だけのとき)は， j = 3 として出てきたら，
a_i * a_0 もa_i * a_1 もa_i * a_2 も全部x未満だったじゃん？でも今回は違うんだよ
だってほら，a_i (=-5) * a_0 (= -5) = 25じゃん
x = 11 じゃん．
25 > 11 じゃん
つまり，a_i < 0 のときは，aを右からみて何個取れるか，って考えなきゃいけないんだ！！
俺はここで実装つまらせて泣いて泣いて泣いて泣いてたんだけど,でも実はこれってupper_boundを使えばよくて(DA?GOの口調)...
aが昇順になってることから，まぁ二分探索で位置求めるのが楽っていうのはそれはそうです．
探す値が -1 っていうのは間違ってますね．
ここでは，a_i * (探す値) >= xとなってほしいのに， a_i * (-1) = -5 * -1 = 5 で，x(=11)よりも小さいです．
だからどうやら，a_iが負の時は，探す値を x/a_i - 1としなきゃいけないみたいですね(へー)
今回は，11/(-5) - 1 = -3 としてsearchが取れて，-5 * -3 = 15 > 11 なのでなるほど確かにそのようになっていますね．
-5,-3, ( * )-3, -2, -1, -1, 0, 4 , 5の中から-3を探す時，米印をつけた方の-3の位置を見つけて欲しいです．
なんでかっていうと,a_iが-5のときに a_i * hoge < x になるものは，
-5,-3, -3, [-2, -1, -1, 0, 4 , 5] のように[]で囲った部分でしゅ
だから，upper_boundで，-3以上となるindexのなかで最大のものを…(あれ？嘘じゃん),-3以下となる値で一番右の位置を求めないといけないじゃん．
ABC093 D-Worst Case
- [二分探索,良い位置,二項の積の性質]
面白いモンダイですね．
とりあえずまぁ，二分探索を使うということが分かったという前提（はい)でやっていきます
今，高橋くんよりスコアの低い人物がX人はokかngかを判定したいです．
X人に対して，1試合メと2試合目で何位だったかを考えると，1試合目では1位からX位（とちゅうでA[i]があるならX+1位まで)のX人,
2試合目では1位からX位（途中でB[i]があるならB[i]位を除いてX+1位まで)のX人としてあげるのがいいことは何となく分かると思います．
X位の人を使わないで Y位(X < Y)にしたって,スコアが大きくなるだけで損なだけだしね．
で，1試合目と2試合目の組？みたいなのを考えた時，1試合目で1位だった人は2試合目でX位ぐらい(2試合目として採用する順位の中で一番順位的に悪いやつ)だったことにしてって感じでやると，
X人についての1試合目のスコア * 2試合目のスコア っていうものの最大値を最小にすることが出来るっピ
まぁ，こんな感じで最大値の最小値が高橋くんのスコアよりモヒかければ，X人は達成出来る．って感じでやっていけばええんや．
がんばれ，俺は頑張った．
ABC182 E- Akari
- [まだ解説読んでない,分解，Lamp,実装がんばえ]
ランプを見つける度に上下を照らして，左右を照らして…ってやると脳がバグります（僕はバグりました)
そこで，ランプを2種類あると考えます．
左右のみを照らすランプと，上下のみを照らすランプの2つです．
H * W のマス目を2つ用意します．
1つは，左右のみを照らすランプを考えるようのマス目
もう1つは，上下のみを照らすランプを考えるようのマス目
それぞれのマス目の上で，左右のみマス目では，
ランプの隣が壁じゃなければ，そのマスの右もランプに感染させる．みたいなことをします．
すると，..o..#..みたいなマス目が(.は何もないます，oはランプ，#は壁)
..ooo#..に変化します．
次に，ランプの隣が壁じゃなければ，そのますの左もランプに感染させる．ってことをします．
するとooooo#..ってなります．
上下のみてらすランプがあるマス目でも，同じようなことをします．
この操作をした後に，H * W ます全部に対して， 左右のみランプ， 上下のみランプのマスのどっちかでランプとして感染済み(もしくは元からランプだった)なら，照らされるマスとしてカウントする．っていうことをやってやります
あとがき
さすがになげえ，ツカレタ．一回投稿，
