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

Medium筋トレ3日目: SRM566

SRM566 Medium "PenguinEmperor"
■時間
５時間ほど。

■試した解き方
daysPassedが小さければ、各町にいける経路数を配列に持って更新していけばいいだけなので簡単。
しかしdaysPassedが最大で10^18なので、これは現実的ではない。

numCities+1日目に動くのと1日目に動くの同じだということに着目する。
つまり、numCities日動いた場合の各町の経路数をキャッシュして、それを(int)(daysPassed/numCities)乗すれば、numCities*(int)(daysPassed/numCities)日目まではすぐに計算できる。
　→2乗を掛算していく方法使えばO(log(daysPassed/numCities))でできる。
残りは地道に更新していけばいい。

⇒以上までは分かったが、最大のケースでtimeoutしてしまうためeditorial見た。ちょこちょこ無駄を消して（実は最初の実装でマトリクスとか使ってた）、大丈夫になった。

1st submit:
OK

■Editorialの解き方
同じかんじ。

■反省
解き方は一発で分かったが、細かい実装でえらく時間食った。
これを11分で解く人とか魔人。

Medium筋トレ2日目: SRM568, SRM567

SRM568
　→できんかった。

SRM567 Medium "StringGame"
■時間
１時間ほど。

■試した解き方
各文字列の各文字のヒストグラム（文字頻度）を作る。
文字列sが他の全ての文字列t0,t1,... に勝てるかどうか調べたい場合を考える。
もしある文字aにおいて、
文字列sでのaの頻度hist[s,a]が他の全ての文字列tでのaの頻度hist[t,a]以上であれば、
aを一番前に持ってくればそこで負けることはない。
更にhist[s,a]>hist[t,a]となるようなtがある場合、文字列tには勝てる。
次に、まだ倒していないtに勝てるような文字bを選ぶ、・・・を繰り返し、全ての文字列に勝てるようならばsを結果として返す、そうでなければ返さない。

1st submit:
System Fail
→テストケースに無かった特定のケースで失敗。

2nd submit:
OK

■Editorialの解き方
同じかんじ。

■反省
提出率52%、成功率49%なのでかなり簡単な問題。
System Failはしたものの、初めて時間内に解けたかもしれない。
次は一発System Failを目指したい。

Medium筋トレ1日目: SRM573, SRM570, SRM569

SRM573, SRM570
　→できんかった。そのうち再チャレンジする。

SRM 573 Medium "TheJediTest"
■時間
３時間ほど。

■試した解き方
Editorialと似たGreedy。ただし、計算の前にstudentsをKの余りだけにした状態にしていた。

1st submit：
System Fail
→余りだけを処理するのではなく、全体で計算しないといけなかった。
その後Editorialを読んで、何回か往復して最終的にSytem Pass。

■Editorial
Greedy。何故これが最小になるのかは（感覚的には分かるが）ちゃんと整理できてない。

■反省
Greedyで解くことは最初からなんとなく分かったが、Div1のMediumがそんなに簡単なわけないと思い、別の方法を探して時間を浪費した。
最終的にSample caseではパスしつつSystem Failしてしまったのは、Greedyで出来る必然性が整理できてないから。どうすれば本番の短時間でGreedyを自信持って提出できるのだろう？

本番：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の敗北なのできっちり倒していきたい。

筋トレしよう〜その２：目指せ赤。

■目標
前回設定した目標は思いがけなく早く達成できた。

6/14　→次のSRM（582）でEasy解く　　⇒解いた

7月中　→Easy解く率80%ぐらいキープ　⇒本番ではいまのとこ100%

8月中　→黄色目指す　　　　　　　　　⇒もう黄色になっちゃった

またTopcoder筋トレのおかげで、レーティングも安定して上がるようになった。

次は赤コーダーを目指したい。

ここ曰く、赤コーダーになるためにはMediumがだいたい解けないといけないようなので、これからMediumの問題を対象に筋トレを行っていく。

■筋トレスケジュール

（変わらず、今度はMedium解いていく）

■マイルストーン

7月中　→時間制限なしでMediumの過去問8問ほど解く

8月中　→本番でMedium一回でもいいから解く

10月中　→本番でMediumを50%ぐらい解く

来年4月ぐらい　→赤コーダー

本番：SRM584 Div1

Easy "Egalitarianism"

■時間

10分ぐらい？

■問題

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

■試した解き方

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

■結果

無事System Test通過。

Medium "Excavations"

■時間

60分ぐらい？

■問題

（あとで書く）

■試した解き方

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

（あとで書く）

■結果

System Fail（時間切れ）

全体結果

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

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

ようやく黄色になった。

反省

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