本番：SRM587 Div1

Easy "JumpFurther"

■時間
4分22秒

■問題
階段のふもとから、1ターン目では1回昇るかそのままいる、２ターン目では2回昇るかそのままいる、・・を入力N回目まで続けるとする。段kは壊れているため、そこに止まることが出来ない場合、到達できる最大の段はなにか。

■試した解き方
そのまま全段を昇った場合に段kを踏んでしまうなら、1段目を飛ばすことにする。
結果、踏む場合：N(N-1)/2　踏まない場合：N(N-1)/2-1
■結果
無事System Test通過

■反省
特に言うことなし。
全パターン試していた人がいたので、challengeで倒せた。
Medium "TriangleXor"
■時間
1時間

■問題
三角形のxorの面積

■試した解き方
非常に地道な方法：
領域を上部、横、下部に分け、
それぞれ補助線引きながらtanとか駆使して面積計算・・・
ポイントとしては、1x1の正方形を想定すると計算が楽（あとでWかければいい）
■正しい解き方
終了後、式を整理していったら６行ぐらいに圧縮できた。

public int theArea(int W) {
double sum=(W%2==0?0.25:0);
{
double prevS=0;
for(int i=1;i<=W;i++){
double s=i/(double)(i+W);
if(i%2==1)
sum+=(1.5-s)*(s-prevS);
else
sum+=(0.5-prevS)*(s-prevS);
prevS=s;
}
}
return (int)(sum*W);
}
→もうちょっとすっきりできそうだけど。

■結果
無事System Test通過

■反省
一発で「正しい解き方」で見つけた式を思いつくのは困難だった気がする。
今回は面積の精度の条件が甘かったので救われた。（ただの計算問題でも出来た）
普段の難しさだったら到底パスしてない。
全体結果
レーティング：1542→1700（158）
・Easyが非常に簡単だったため、回答成功率はかなり高かった。
　→そこそこ早く提出できて助かった。
・Mediumはいつも通りぐらいの回答率
　→計算で解ける問題は日本人のほうが慣れてる気がする。
・とにかく黄色コーダーを維持できてよかった。

本番：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人殺すとか。。。

本番：SRM585 Div1

Easy "TrafficCongestion"
■時間
40分ぐらいorz

■問題
perfect binary treeで表される街と道路のネットワークがある。持っている車を全て合わせて、全部の街にちょうど１回ずつしか通らないように走らせたい時、最小の車の台数はなにか。

■試した解き方
・greedyに解いた。なんとなく最小の数ってのは、一つ車を端から端まで走らせて（下図の「0番目の車」）、残った木をsubtreeとしてそれぞれの最小車数を足していけばいいんじゃないかと考えた。（これが最小となる証明は出来てない）

ある高さnの木の最小車数をN(n)とすると、
N(n)= 1+ 2*Σ[i=0~n-2].N(i)
となる。
nがでっかい（最大1000000）なので、全てのN(n)を覚えるのは現実的ではない。
なので漸化式に直す：
N(n)=N(n-1)+2*N(N-2)
N(0)=N(1)=1で始めて、任意のnまで計算する。

static final int MOD=1000000007;

public int theMinCars(int treeHeight) {

long pprev=1, prev=1;

for(int n=2;n<=treeHeight;n++){

long current= (prev+2*pprev)%MOD;

pprev=prev;

prev=current;

}

return (int)prev;

}

■結果
無事System Test通過。

■反省
greedyな解き方を思いつくのに時間かかりすぎた。
漸化式に直すのにも時間かかった。
こんな問題は１０分ぐらいで解きたい。

Medium "LISNumber"
■時間
Not Submitted。その後５時間ぐらいかけて解いた。

■問題
ある数列を渡された時に、その数列を「単調増加する数列」の最も短い列として表したときの列数をLISNumberと定義する。
数字が沢山渡された時、入力されたLISNumberとなる並び替え方の組み合わせ数を返せ。

■試した解き方
順番に小さい数字から足していった時に各LISNumberのパターン数を考えていく。
便宜的に、i番目の数字までを考慮した際のLISNumber=nのパターン数をN(i,k)と呼ぶ。

例えば入力が
0×3
1×2
2×11
3×5
4×7
でLISNumberが20の場合・・・

最初の「0」しか考えないとすると：
LISNumber=3となる数列は1パターン（0_0_0）
それ以外のLISNumberは0パターン存在する。

次に「0」「1」を考える時、
LISNumber<=2の数列を作る方法は存在しない。
LISNumber=3は、「0」の時のLISNumber=3の数列の中の数列の後ろに足していけば作れる。
（例えば0_0_0→01_0_01）
３カ所に2つの数字を置きたいので、N(1,3)= 3C2 × N(0,3) 。
LISNumber=4,5は、「0」の時のLISNumber=3の数列の頭か、各数列の中を分割するような位置に置いていけば作れる。
例えばLISNumber=4は1_01_0_0、LISNumber=5は1_1_0_0_0など。
LISNumber=4の場合は一つを既存の数列に結合するように置き、もう一つを新規の数列になるように置く必要があるので、
N(1,4)= 3C1 × 1S1 × N(0,3)
（where: nSkは「n個の箱にk個のボールを置く方法」。パスカル三角形的なので計算できる。）

このように一つずつ数字を足していき、最後N(|array|,n)を返せばいい。

■結果
OK（ただしSRM終了後）

全体結果
レーティング： 1521→1458（-63）
Easyに時間かけすぎたせいでレーティングが落ちてしまった。
また青に逆戻り。

コメント
・Easyは安定して解けるようにはなったが、スピード遅すぎる。
・Mediumは珍しく本番中に解き方が分かったので、少し満足。
・部屋で誰にもchallengeされなかったのにSystem Failしていた人がいた。こういうのはchallengeの敗北なのできっちり倒していきたい。

本番：SRM584 Div1

Easy "Egalitarianism"

■時間

10分ぐらい？

■問題

ある国の交友関係（無向グラフ）があり、どの国民も自分のどの友人との所持金の差がD以内でないと行けない場合、この国で起きる最大の格差はなにか。

■試した解き方

グラフの直径を計算するだけ。Warshall-Floydで実装。

■結果

無事System Test通過。

Medium "Excavations"

■時間

60分ぐらい？

■問題

（あとで書く）

■試した解き方

愚直にパターン足してった。

（あとで書く）

■結果

System Fail（時間切れ）

全体結果

レーティング： 1407→1521（+114）

Easyを早く出したおかげでレーティングがかなり上がった。

ようやく黄色になった。

反省

・「駄目なやり方だけど一応やっておくか」でやるとやっぱ駄目。

本番: SRM583 Div1

Easy "TravelOnMars"

■時間

10分ぐらい？

■問題

リング上に街があり、各街からは最大で一定の距離まで行ける電車が走っている。任意の場所から場所まで移動した場合、乗る最小の電車の数はなにか。

■試した解き方

ただのDijkstra。modにちょっと気をつけるだけ。

■結果

無事System Test通過。

Medium "TurnOnLamps"

■時間

submitせず

■問題

木構造で、全てのedgeに電灯が設置されている。また電灯のうち何個かは「重要な」（＝点いてほしい）電灯。電灯のON/OFFは木のノートを２つ指定すると、その間の最短パスの電灯が全て反転する。

重要な電灯が全てONになるためには最小で何回のオペレーションが必要か。

■試した解き方

だめぽ

■結果

submitせず

全体結果

レーティング： 1341→1407（+66）

青だとEasyできるだけでもそこそこ上がるのね。

筋トレ開始してから順調にまたレーティング上がり始めた。

反省

・Mediumはもうちょいで分かりそうなきがしたんだが・・・

本番: SRM582 Div1Easy "SpaceWarDiv1"

■時間

30分ぐらい？

■問題 SRM582 Div1 Easy "SpaceWarDiv1"

いろんな強さのモンスターがいて、モンスターを倒せる戦士がN人いる。戦士は自分以下の強さのモンスターは倒せるが、モンスターを倒すたびに「疲労度」が１点増える。モンスターを全員倒したときに一番疲労している戦士の疲労度が最小となるように倒していった場合、この疲労度の最小値はなにか。

■試した解き方

ちゃんと証明してない（ので今はあまり説明できない。あとでちゃんと埋める。）が、greedyで解ける：

戦士を弱い順にみていった時に、

今見ている戦士iの倒すべきモンスターは、残っているモンスターの総数をT、残った戦士の数をNとした場合、最大でもceil(T/N)。

　→それ以上倒しても、戦士iが倒せるモンスターは必ずiより強い戦士も倒せるので意味がない。

なので、

・戦士を弱い順にソート

・最大でceil(T/N)だけ自分以下の強さのモンスターを倒していく

・モンスターが残った場合は-1返す

（もしくは）一番多く倒した戦士の数を返す

public long minimalFatigue(int[] magicalGirlStrength, int[] enemyStrength, long[] enemyCount) {

Arrays.sort(magicalGirlStrength);

long numEnemyLeft=0;

for(long c:enemyCount)

numEnemyLeft+=c;

long max=0;

for(int girl=0;girl<magicalGirlStrength.length;girl++){

long norm=(long)Math.ceil(numEnemyLeft/(magicalGirlStrength.length-girl));

long tot=0;

for(int ei=0;ei<enemyCount.length;ei++){

if(enemyCount[ei]>0 && enemyStrength[ei]<=magicalGirlStrength[girl]){

long numDefeat=Math.min(norm, enemyCount[ei]);

tot+=numDefeat;

enemyCount[ei]-=numDefeat;

numEnemyLeft-=numDefeat;

norm-=numDefeat;

}

}

max=Math.max(max,tot);

}

if(numEnemyLeft>0)

return -1;

return max;

}

■結果

他の人と違う解き方をしていたせいでやたら狙われたが、無事System Test通った。

レーティング： 1221→1341（+120）
４回ぶりにレーティング上がった！

■Editorial
まだ載ってない。

■反省

・他の人は大体binary searchで最大値探してた。自分の方法はO(nt）で解けるので優秀だと思う。

・greedyの解法見つけたのはよかった。感覚的に証明出来る気がしたのでGOしたが、本来危険。