SRM560 Easy "TomekPhone"
■時間
10分ほど
■試した解き方
Greedyに、多く使われる文字順に、今与えられる一番低い位置を与えていくだけ。
1st submit：
OK
■editorial
→同じ感じ。もうちょっとすっきりした書き方。
■反省
Greedyで出来るかどうか、一瞬躊躇ってしまった。
これぐらいの問題は2,3分で解きたい。
SRM560 Medium "DrawingPointsDivOne"
■時間
2時間ぐらい・・・
■試した解き方
1回目：
与えられた点群の一つ一つの点を広げていった時に、他の点から発生した四角形とぶつかったらアウトになる。そのため、間に点が存在しない点ペア間の最小マンハッタン距離を計算すればいい、と勘違い。
→testも通らなかった
Editorialの解説だけ確認：
まず、1ステップを行うというのは、四角形を左下方向に1単位だけ縮小させる動作、というふうに考えられる。
あるkステップ戻った時に、元の点群に存在しないようなk×kの正方形ができてしまったら、kは駄目ということが分かる。
なので、kを1から順番に試していけば、最小のkが分かる、はずだがこれだと遅いので、さらにkをbinary searchする。
1st submit：
timeoutするケースが存在
あるkの時のボードの塗り方が少し無駄な実装になっていたので、これを修正
2nd submit:
OK
■反省
・1ステップの動作を「左下への縮小」と考えるのは、その気になれば思いついたはず。別の表現方法に固執したため見落とした。
2014年3月2日日曜日
2013年11月21日木曜日
Easy筋トレ1日目: SRM562, 561
前回の筋トレ以降、仕事の都合上全く練習できずにいたら、恐ろしくレーティングが下がり始めました。
SRM562 Easy "PastingPaintingDivOne"
■時間
４０分ほど？
■試した解き方
各斜め線の挙動を考える（斜め線間での干渉はないため、一本の斜め線（例： (0,3),(1,4),(2,5),...）毎にしか考える必要がない。
線の中で、一番左上の透明でないピクセルは必ずT回コピーされる。
それ以降のピクセルは一回しか現れない。
ただし、透明のピクセルの場合は自分よりも（最大距離T-1で）右下で透明ではない、最初のピクセルの色になる。
以上の条件で、足すだけ。
大体O(w*h)で解ける。
1st submit:
OK
■Editorialの解き方
シミュレーション的解き方。実際にコピーしてみて、前回と同じレイアウトになったらそれ以降は掛算で計算。あんまきれいじゃないよな？
■反省
やたら時間かかってしまった。
斜め線の中を、一番左上のピクセルと、それ以外の２ケースだけで考えればいいことに気づかず、もっと色々なケースがあると勘違いしてしまったため。
過去５回、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の割り当て方を考える所に悩んでしまった。
■時間
４０分ほど？
■試した解き方
どの問題をどのサイズの風船にするかは、割当が2^15しかないので、全パターン試す。
割当が決まっている時に、実際に風船の色を割り当てる方法は、（証明してないが）なんとなくGreedyでいけそうな気がした。
1st submit:
OK
■Editorialの解き方
同じ。
■反省
これも時間かかってしまった。
実際のGreedyの割り当て方を考える所に悩んでしまった。
2013年8月2日金曜日
本番：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はいつも通りぐらいの回答率
→計算で解ける問題は日本人のほうが慣れてる気がする。
・とにかく黄色コーダーを維持できてよかった。
■時間
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はいつも通りぐらいの回答率
→計算で解ける問題は日本人のほうが慣れてる気がする。
・とにかく黄色コーダーを維持できてよかった。
2013年7月28日日曜日
本番：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人殺すとか。。。
■時間
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人殺すとか。。。
2013年7月27日土曜日
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分で解く人とか魔人。
■時間
５時間ほど。
■試した解き方
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分で解く人とか魔人。
2013年7月21日日曜日
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を目指したい。
→できんかった。
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を目指したい。
2013年7月20日土曜日
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を自信持って提出できるのだろう？
→できんかった。そのうち再チャレンジする。
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を自信持って提出できるのだろう？
登録:
投稿 (Atom)