本番：SRM586 Div1

Easy "PiecewiseLinearFunction"

■時間
9分40秒

■問題
x軸方向に等間隔な点列が与えられ、それらの間は直線で結んだグラフを考える時、
ある直線y=kを定めた時のこのグラフとの交点の最大数を求めろ。

■試した解き方
値自体は大きいが、値の数は50個までしかないので、違う答えとなるy値のレンジもその数しか存在しない（と勘違い）
全ての渡された点のy値について、その直線を引いた場合の交点数を試して、最大数を返す。

■結果
Challengeでfail。

■正しい解き方
ありえる線は、各点を通る線ではなく、（各点を通る線）、（各点のちょっと上を通る線）、（各点のちょっと下を通る線）だった。
なので+0.5, -0.5を試してもいいし、
全部のy値を×2してから+1, -1を試すのでもいい。

■反省
分かったと思って焦りすぎた。
Easyを提出した17人中11人がChallengeで死亡。
単純な例題{(0,0),(1,1),(2,0),(3,1)}でも検証できたはずなので、もう少し冷静になるべきだった。

Medium "History"
■時間
55分

■問題
色々な国があり、それぞれのカレンダーは年の始まる日と年の長さは全員同じだが、年の呼称はそれぞれずれている。
今以下の情報が分かっているとする：
・各国に過去に存在した王制の開始〜終了年度（その国の単位で）
・ある王制同士が戦争をしたという記録（つまり同時期に存在した）
この時、渡された２つの王制同士の間に戦争が起こりえたかYかNで返せ。

■試した解き方
各国A,B間の最小と最大のカレンダーのずれmind(A,B), maxd(A,B)を管理していく。
最初は全て：mind(A,B)=-∞ maxd(A,B)=∞
各戦争の情報が入力されるたびに、当該国家間のずれを更新できる。
（２つの王制が同時に存在した瞬間が両端にある場合から最大、最小のずれを計算し、現在のずれを狭められるなら更新）
更に、他の国Cの情報を使ってA,B間のずれを更に狭められる：
C= min(A,C)+A　〜　max(A,C)+A　と
B= min(C,B)+C　〜　max(C,B)+C　が分かっている場合、
B= (min(A,C)+min(C,B))+A　〜　(max(A,C)+max(C,B))+A　が導出できる。
今分かっている範囲が
B= min(A,B)+A　〜　max(A,B)+A　だった場合、
min(A,B) <- max( min(A,B), (min(A,C)+ min(C,B)) )
max(A,B) <- min( max(A,B), (max(A,C)+max(C,B)) )で更新できる。
多分Warshall FloydのようにO(n^3)で更新しきれる。
（不安だったので、全A,B,Cについて更新するのを繰り返し、更新されなくなったらストップした。）

最後に入力された戦争があり得るかは、入力された２つの王制の範囲が被っているか試せばいい。

■結果
無事System Test通過

■反省
やり方は一瞬で分かったが、範囲の更新にイージーミスではまって、実装にえらく時間かかった。
残り時間あと１０分で終わったので、かなり厳しかった。
Mediumは今まで時間を考えずに練習していたので、しょうがないかもしれんが・・・

全体結果
レーティング：1458→1542（74）
・全体でEasyはChallenge死がめちゃくちゃ多く、部屋の20人中4人しかポイント獲得していなかった。
・Easyのアホミスをしていなければかなりレーティングが上がったことが予想されるだけに悔しい。
・Mediumは、初めて本番で通ったので嬉しい。
　　→回答率、正答率はそこまで高くなかった様子なのが不思議。2軍レベルの問題だと思ったのだが。
・部屋にEgor（！）がいて、Egor無双が見れて感動した。Challengeで11人殺すとか。。。