Educational Codeforces Round 68 (Rated for Div. 2)
大昔(2週間前)に爆死したやつに再チャレンジした
A Remove a Progression
問題：1からnまで数字が書いてある。x回目の操作では、残っている数字からx番目の数字を消す。x回の操作後のx番目の数字を求めよ
考察：
x番目を消した後x番目を求めるので、常に消した直後の数字を見ることになる。
x+1番目以降は、残っているx番目までは関係ない。
つまり言い換えれば、x回目の操作＝数字を2つ消すと同じである。
実際に消す数字と見る数字を1つ後ろにするので2つ消すことと同じになる
答えが出ることが保証されているため答えは2*xである
B Yet Another Crosses Problem
問題：白黒のグリッドが与えられる。あるマスを選び、その列と行が黒になるようにしたい。最適にマスを選んだとき、塗る最小のマスの数を求めよ
考察：
n*m<=4*10^5より、各行各列の黒の数を調べれば全探索が可能なことがわかる。
ここで、選んだマスが白だった場合、必要なマスをダブルカウントしているので１引く必要があることに注意する
C From S To T
問題：文字列s、t、pが与えられる。pの任意の文字を削除し、sの任意の箇所に挿入する(しなくてもよい)。文字列sをtに変えることはできるか。
考察：
まず元のｓを考える。ｓの中の文字と順序は変えることができない。
したがって、ｓの文字がｔに出てこなければならない。
ｓとｔを比べてｓにないがｔにある文字をｐから補填すると考える。
実装：
s[i]とt[j]を比べる
s[i]!=t[j]：
pからt[j]を引く。なければNO
j++;
s[i]==t[j]：
i++;
j++;
もしｓかｔを最後まで見れない場合ＮＯ。見れればＹＥＳである
D 1-2-K Game
問題：AliceとBobの2人ゲームを考える。はじめ整数Nからスタートする。各手番でプレイヤーは、数字を1,2,kのどれかだけ減らすことができる。操作を行えない場合負けである。お互いが最適に動いたときどちらが勝つか。
考察：
ゲーム問題は各状態での勝ち負けを列挙するとよいのでします。
簡単に１か２だけで考えてみましょう。
0 1 2 3 4 5 6 7 8・・・k
LWWLWWLWW・・・？
もし１か２減らして相手をLoseにできれば、自分はWinです。
逆に、１減らしても２減らしても相手がWinになってしまう場合はLoseです。
では、k減らすときはどうなるでしょうか。
減らす前Loseだったはずだが、k減らした先がLoseなら、Winになります
そうでなければ、１か２を選ぶ場合と変わりません。
k減らす前も後もLoseになるのはk%3==0のときです。k%3==1or2のときは、上のような周期に合わせて答えを出力すればよいです。
k%3==0のとき：
0 1 2…k-2、k-1、k、k+1
LWW…W W W L
Winが間に入り、Loseが現れる周期がズレたことがわかります。
このあとも確かめると1ずつズレていきます。
したがってn%(k+1)==kならWin、それ以外なら上と同じく%3の値で勝ち負けを決めます。
感想：
ゲーム問題難しいですよね。
コード書いて数が小さい範囲を全列挙すると、法則が見える場合があるので良いと思います。
Grundy数も一応勉強したんですけど、なんだかうまく使いこなせる気がしませんでした。
E Count The Rectangles
解説ACしました。
問題：N本の線分が引かれている。線分はx軸かy軸に平行である。このとき、長方形はいくつできるか。長方形の1辺は、線分の一部分でもよい（厳密に一致する必要はない）
考察：
あんまり考察がはかどりませんでした。
制約的にx軸平行かy軸平行の線分を2本選ぶを全探索か、1本選んで全探索かなと思いました。
解説：
ある1方向を固定して考える
解説では下側を固定していました。
下側の線分をline[i]としましょう。
まず状況の整理をします。長方形を作るとはどういうことでしょうか。
line[i]と交点を持つy軸平行の線分が2本あります。
そしてその2本と交点を持つx軸平行の線分があることが条件です。
更に言うと、下側のline[i]と上側のline[j]の、どちらとも交点を持つy軸平行の線分を数える。これをsとしたとき、line[i]、line[j]によって作られる長方形はs*(s-1)/2個になります。
これはsC2です。
なので、下側line[i]を固定したとき、上側にある全てのline[j]で、交点を持つ線分の数を求めていきます。
では実際の解法です。
はじめに、line[i]のx座標の範囲で、配列を持つ必要があります。各xで、y軸平行な線分といくつ交点を持つかを記録します。
あとでline[j]の範囲で区間和を取るので、SegmentTreeが良いでしょう。
次に線分N本をy座標昇順で、クエリ形式にして見ていきます
0．y軸平行の線分の下の点
1．x軸平行の線分
2．y軸平行の線分の上の点
0がline[i]以下で、x座標の範囲内にあるなら、0のあるx座標のカウントを+1します
2で、下の点がline[i]以下の場合、これ以降この線分は考えません。なのでカウントを-1します。
1では、line[i]との共通するｘの範囲で、0,2で求めたカウントを足しsとします。先ほど言った通り合計値にs*(s-1)/2を足します
0,1,2の付け方がバラバラに見えますが、これはy座標が同じ場合の処理順を指します。
端点を許すためこの順番にすると都合が良いです。
実装：
Submission #58157065 - Codeforces
かなり汚い実装になっています。ご了承ください。
まず、座標の入力では+5000して整数値に直しています。結局あとでゼロ正規化しているのであんま要らなかったです。
上でline[i]は各クエリのうち、1に該当するので一緒くたにしてしまいます。
y軸平行の場合：
(y_min,0)(x,y_max)
(y_max,2)(x,y_min)
x軸平行の場合：
(y,1)(x_min,x_max)
クエリ2では、下の点がいるので後ろに保存していますが、クエリ0では要りません。一応入れた程度です。
クエリ処理に関しては特に難しいことはしていなくて、範囲に気を付けながら処理していけばよいです。
計算量に関していうとO(N^2）なので間に合います。
厳密にはO(N^2logN)な気がします。まあ重たい配列操作とかないので間に合いました。
(この前に重たい配列操作などして無限にTL出した)
感想：
いつだったかのABC-EにRoadworksという問題があって、それはセグ木で通したんですけど、似たようなクエリ処理が想定解でした。
ちゃんと解説読んでないけど似た解法なのかなーとかも思いましたね。
尺取りに近い実装なのかなと思います。
はじめ二次元累積和も考えたんですけど座標が10^4なので、まあ無理かなと。座圧も効かないし。
atcoderのk-DMCも尺取りで通せなかったので、かなりつらいですね。
もしかしたら尺取りが苦手なのかもしれないです。考察力足りないだけだと思うけど
どこか一方を固定というのにはたどり着けていたのでそこは良かったかな。
y軸平行な線分を、端点と端点で分解というのは良い典型かもしれないです。
固定、分解など。なんか使えそう。
FGは気が向いたらやります。難しそうだし。
全体の感想
この回のエデュフォはDのゲーム問題を誤読して(1～k減らせるとおもってた)、結構ひどかった回でした
まあE通せそうになかったですね難しかった。
Google翻訳の利便性を知ったのでこういう誤読はなくせると思います
なんで今まで使ってなかったんだろ。
