ABC182 F Valid payments
よくよく考えれば，それはそう・・・
問題
解法
なんか難しく書いてある（解説も）けど，結局は普段の買い物を考えてみるといい（例えば普通10円玉を使って支払う時に，10円玉のお釣りが出るような払い方はしない）
そうすると，下の桁から端数の扱いでその硬貨を使う使わないの遷移が出てくる
例．財布の中に1円玉，10円玉があるときに
12円は12円（1円玉を使う）で支払うか20円（1円玉を使わない）で支払うかどっちかになるはず
要するに，その硬貨を使うときは使える分だけ使えばいい，使わないときは次の世代に対してその不足分に足りるような分だけ足してやればいいというのがわかるので，あとはこの遷移をそのまま実装する
ABC187F Close Group
メモ化再帰めっちゃ遅くてビビった
問題
解法
要するに繋がってる同士でグループわけができればいい
1つにならない場合は適当にグループ分けして，その分けたグループ内でもできる限り少ないグループ分けになればよさそう→そういうDPを考える（ここまではできた）
集合S内の部分集合を辿っていく際はこう書けばいいらしい
for(int T=S;--T&=S;)
or
for(int T=S;T>0;T=(T-1)&S)
あとは
f(S):集合Sにおけるグループ分けの最小数
Sはそのままで条件を満たす→1
otherwise f(S)=f(S^T)+f(T)としてこれのminをとってやればOK
ABC186F Rook on Grid
むずかった・・・ 解説AC
問題
上を見よう
解法
A:→↓でいけるやつ
B:↓→でいけるやつとして
A∨Bが求まればいいので
A∨B=A+B-(A∧B)で求めればいい．
AとBはそれぞれ各列or各行において最小となる成分を事前に計算しておけば良し（ここまではできた）
A∧Bについては，左の列から見ていった時に出てきた障害物より右側はBで行くことができないのでそこの部分を省く
BITにy=0において行けるところまでの高さ分だけ1を加えておいて，上記の考察をもとに障害物が出てきたところでそこの高さの部分の列を差し引いてやればいい感じに求まる
座標圧縮してfenwick_treeで数え上げるやつ
某動画を見て以来（初めて見たとき茶コーダーとか）どういうことなんだろうって思ってたやつ 忘れないように
何がしたいの
i<jかつA_i<A_jを満たすような組み合わせの数え上げ
例：
A={1,1000,10,10}
→(0,1),(0,2),(0,3)で3つ（例がカスかもしれん・・・）
前提知識
座標圧縮
配列があって，要素が小さい順に（でかい順に振ることもあるのかな知らない）番号を振るやつ
例：
A={1,1000,10,10}
→{0,2,1,1}
fenwick_tree
segment treeの簡易版みたいな奴らしい 一点更新と区間和取得ができたりする 自分の構築次第でfenwick_tree上で二分探索とかできる（とりあえず今回はAtCoder Libraryのやつをまんま使う）
fw.add(x,p):a[x]+=p
fw.sum(l,r):a[l]+a[l+1]+...+a[r-1]
どうするの
1.長さnのfenwick_treeを宣言しておく
2.座標圧縮する
3.0から座標圧縮で対応するところまでの区間和を取得して現在の答えに足す(fw.sum(0,k)みたいな）
4.座標圧縮で対応するところに1足す(fw.add(k,1)みたいな）
5.3-4を最後まで繰り返す
イメージ
4がカウントしてるとみなすと良さそう
要素を順番に追加しながら操作してるのでi<jの順序関係はこれで満足してて，自分のところより小さいのを数えてやればA_i<A_jとなってるのをめでたくいい感じに数えられて，最高！
実際にやってみよう
ABC187 B - Gentle Pairs
つい先日開催されたABCのB問題ですが，これを使って解くことができます．
解法
まず，満たすべき傾きの条件-1<=(y_j-y_i)/(x_j-x_i)<=1は，abs(y_j-y_i)<=abs(x_j-x_i)と同値でした．故にこれを満たすような(i,j)の個数を求めてやる必要があります．
これの絶対値をそのまま外そうとすると，左辺の絶対値の中身の正負，右辺の絶対値の中身の正負の場合わけで４通りのパターンが出てしまいます．
しかしここでよくよく考えてみると，最終的な点のプロット状況が決まれば，入力で与えられるi,jの順番自体はどうでもいいことが分かります．（結局言わんとしてるのは傾きの絶対値が１以下になるような直線をできるだけたくさん結べってだけなので）
よって，i<jならばx_i<x_jとみなしても差し支えないことがわかります．そうすると右辺の絶対値の中身が必ず正になるので場合分けが２通りですみます．
そうしてそれぞれの場合で式を展開して変形してみると，以下のようになるかと思います．
(i)(y_i<=y_j) and (x_i-y_i)<=(x_j-y_j)
(ii)(y_i>=y_j) and (x_i+y_i)<=(x_j+y_j)
とりあえず変数が散らばってるのは気持ち悪いので一方の辺に寄せてみました．これを見てみるとx+y,x-yと言う形が見えるかと思います．ここから45度回転が見えるのでx'=x-y,y'=x+yとして45度回転させてみます．（賢い方はここの辺りの考察が無くても図から回転させる発想が出てたかもしれないですが）
そしてさらに先ほど言った平面上の点はどのような順番で見ても問題ないと言うところからi<jならばx'_i<x'_jになるようにindexを振ってやると，結局ある頂点から見たときにこんな区画にいるような頂点との組み合わせが条件を満たすと言うことがわかります．
雑な手書きでごめんなさい．
あとはx',y'それぞれについて座標圧縮して，あるx'=x'_kまで要素を追加したらx'=x'_k上の各点について上のような状況を満たす点の個数をカウントしてやればいいです．これは，ある点vのx’座標，y'座標を圧縮した結果をそれぞれx'_v,y'_vとすれば，fw.add(y'_v,1)をx'=x'_vを満たす各点について行なった後に，さらにそれぞれの点についてfw.sum(0,y'_v+1)-1としてやればよさそうです．（-1は自分を除く）
座標圧縮にO(NlogN),各要素の追加や総和を求めるごとにO(logN)なので，結局O(NlogN)でこの問題を解くことができます．
本来の想定解法はO(n^2)なので，めちゃめちゃ高速になってるのがわかります．（制約が小さいので，あまり数字には出て来づらいのですが） ただABC-Bでこのレベルを求められたらちょっと参りますね・・・
また今回学ぶにあたって色々な方々の提出を拝見させていただきました．皆さまありがとうございました．
EDPC G - Longest Path
考えたこと
まあそりゃDPなんだけど
閉路がないってことは何も生えてこない頂点が存在するはず→これを基準にDPを組み立てていくと良さそう
この位置にあったので身構えてたけど，思いの外シンプルだった
ABC085 D - Katana Thrower
考えたこと
貪欲っぽいけど嘘が怖いなぁ
とりあえず貪欲が見えたらDP疑ってみる→HPをいくら削ったとか，どの刀を投げたかとかみたいなのを状態で持とうとしたりしたけど，まあ制約的に無理（当たり前）
どうやったら状態数減らせるか→普通に考えて投げたときのダメージがでかいやつを投げるのが一番いいに決まってる
冷静に考えれば投げつけるの最後に回せば一度も使わない制約いらなくね？
→解けた・・・と思いきや投げるだけで終わるパターンがあって，それも考慮する必要がある
あとPythonだとreverseがlist[::-1]なの忘れがち（heta）(reversed=Trueを使え）
DPではなかったけど，結果的にDPを考えようとしたのが役に立った
