Easy筋トレ1日目: SRM562, 561

前回の筋トレ以降、仕事の都合上全く練習できずにいたら、恐ろしくレーティングが下がり始めました。

過去５回、Easyを凡ミスや、単純に閃かなかったなどの理由でSystem Failし続けています。

というわけで、急遽筋トレ再開します。

SRM562 Easy "PastingPaintingDivOne"
■時間
４０分ほど？

■試した解き方
各斜め線の挙動を考える（斜め線間での干渉はないため、一本の斜め線（例： (0,3),(1,4),(2,5),...）毎にしか考える必要がない。
線の中で、一番左上の透明でないピクセルは必ずT回コピーされる。
それ以降のピクセルは一回しか現れない。
ただし、透明のピクセルの場合は自分よりも（最大距離T-1で）右下で透明ではない、最初のピクセルの色になる。
以上の条件で、足すだけ。
大体O(w*h)で解ける。

1st submit:
OK

■Editorialの解き方
シミュレーション的解き方。実際にコピーしてみて、前回と同じレイアウトになったらそれ以降は掛算で計算。あんまきれいじゃないよな？

■反省
やたら時間かかってしまった。
斜め線の中を、一番左上のピクセルと、それ以外の２ケースだけで考えればいいことに気づかず、もっと色々なケースがあると勘違いしてしまったため。

SRM561 Easy "ICPCBalloons"
■時間
４０分ほど？

■試した解き方
どの問題をどのサイズの風船にするかは、割当が2^15しかないので、全パターン試す。
割当が決まっている時に、実際に風船の色を割り当てる方法は、（証明してないが）なんとなくGreedyでいけそうな気がした。

1st submit:
OK

■Editorialの解き方
同じ。

■反省
これも時間かかってしまった。
実際のGreedyの割り当て方を考える所に悩んでしまった。

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

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