Codeforces Round #558 (Div. 2)
ばたや
A. Eating Soup
問題：ｎ人が円状にならんでいるとき、ｍ人を退席させる。非連続にわかれる最大の個数を求めよ
考察：
n/2までは増えてそれからは減りそうです。
奇数のときでn/2付近が怪しいので実験して丁寧に解きましょう
B1. Cat Party (Easy Edition)
B2. Cat Party (Hard Edition)
問題：ｎ個の整数列がある。ｋ個目までで、1要素削除したとき、出現する数字のそれぞれの出現回数が等しくなるようにしたい。最大のｋを求めよ
考察：
1要素削除して回数が一致する場合を考えます。
まず出現回数の種類は2種類以下の必要があります。
はじめに2種類のときです。多いほうの出現回数の出現回数が1回で、差が1のときOKです。また、1回の出現回数が1回のときもOKです。
わけわからないので具体例を出します。以下はそれぞれの整数の出現回数を列挙したものです
1-1：3,3,3,4
1-2：1.3,3,3
こんな感じです。
次に1種類のときです。
出現回数の出現回数が1回か、出現回数が1のときOKです
具体例です
2-1：4
2-2：1,1,1,1,1,1
出現回数のmapと、出現回数の出現回数のmapを持てばO(NlogN)で実行可能です。
実装にすごい苦労して1時間くらいかかっちゃいました。
下手すぎる
こういう愚直に場合分けするのはIQが試されてる感じがして苦手です。なぜならIQ低いので。
C1. Power Transmission (Easy Edition)
C2. Power Transmission (Hard Edition)
問題：ｎ個の点がある。任意の頂点対を取り、2つを通る直線を引く。直線の交差する数を求めよ
考察：
直線の傾きと切片をすべて出します。
どちらも一致するものを削除します。
もし傾きが同じなら交わらないです。
傾きが違うもの*傾きが同じもの
これをすべての傾きで行えばよいです。
O(N^2logN)程度で実行可能です。
実装：
long doubleでやると破滅します。しました。
直線を表すとき、xの増加量：yの増加量で判別すればよいです。
それぞれをa,bとかおきます。式をガチャガチャすると切片cで表せます。
比を取る際にgcdで割ったり-1をかけたりします。
gcdの関数に0であるときの注意をしておきましょう。すべての点はdistinctなのですべて0になることはないです。
2点を通る直線を表す
ax-by=c
a=y1-y2
b=x1-x2
c=x2y1-x1y2
これを毎日3回、ロシアの方角に向かって唱えることにしました。
D. Mysterious Code
問題：文字列cの*を好きな文字に置き換えたとき、連続する部分列が、文字列sに一致する数-文字列tに一致する数の最大値を求めよ
解説：
KMP法を使うらしいです。
KMP法：
KMP配列を前計算し、文字列の中に出現するパターン文字列を求めるアルゴリズムです。
KMP配列とは、パタンのｋ文字目がパタンの接頭辞と一致するかの判別を示します。
あるｋ文字目が一致しないとき、また1文字目から確かめるとO(NM)になってしまいます。したがってどこまで戻ればいいかを記録します。
一致するなら1つ進み、一致しないなら一致するまで戻って1つ進みます。
もしｋ文字目がｃのとき、どのような遷移をするかをすべて求めます。
与えられた文字列を見ながらその遷移を行ったとき、パタンの最後まで見れれば一致しているといえます。
これを*がどの文字になるかで遷移を計算します。
パタンｓとｔそれぞれの何文字目を見ているか、与えられた文字列分があり、遷移は前計算をすることでO(1)です
したがってO(|c||s||t|)で解くことができます。
なんとなーくKMP法についてわかったようなわかってないような。
コードを空で書いたり応用することは不可能な段階なので、しっかり復習したいと思います。
