SRM691(Div1)に参加しました!が…
初めてのDiv1だ。゚(゚´ω`゚)゚。
— satanic@C++ (@satanic0258) 2016年5月30日
今回は色々意外なことがあったので日記として書いておきます。
(この記事に解説は含まれないので予めご了承下さい)
私が前回参加したのはSRM688だった、ということで気づいたら2回分参加忘れていたようです…
そういえばSRMのシステムあんまり覚えてない(白目)
— satanic@C++ (@satanic0258) 2016年5月30日
そのSRM688では、割といい成績を残せ(てしまっ)たので、SRM2回目にしてDiv1という魔境(?)に放り込まれることに。
ヒヤヒヤしていたらすぐに時間になってしまいました。
Coding Phase
Easy(300)
問題を解読するのにやや手こずりながらも色々考察をしてみる…
(テストケースを書いてみたり、DPで出来…ないなぁと色々やっています)
…その考察の結果、
テストケース通らず悲しみ
— satanic@C++ (@satanic0258) 2016年5月30日
結局、時間内に通すことは出来ませんでした…
個人的にグラフ理論関係の問題がまだ不慣れな部分もあってか、あまりどういうことしたら良いかを見出すことが出来ませんでしたね…(今後の目標ポイント)
Medium(500)
Hard(900)
Easyに下手に時間を掛けてしまい、気づいたら時間が終わってしまったので開けてすらいません。
点数が減ることを気にする以前に、解けなかったら意味がないのである程度考えてもわからなさそうだったら、さっさと他の開けちゃった方がいいですね…(今後の目標ポイント2)
(ちなみに、問題などを初めから順に埋めていこうという癖があるようで、大学受験時のセンター試験なども解く順番を替えていたらもう少し点が取れたのかもしれなかったですね…)
Intermission
結局何もできず終わりの鈴がなってしまいました…。
room内でeasy3人しか通してないのやばすぎでしょ
— satanic@C++ (@satanic0258) 2016年5月30日
しかし、roomの状況を見ると以外と他の人もあまりいい調子ではなさそう。
これで次のChallenge成功したら大逆転のチャンスが…?
…ということで、なんとか爪痕を残そうと改めて意気込みました(半ば諦めてはいましたが…↓)。
challengeで点稼ご(無理)
— satanic@C++ (@satanic0258) 2016年5月30日
Challenge Phase
Challenge Phaseが始まって数秒、突然Hardを通していた4人のコードが次々と撃ち落されていく光景が…
「なんだここは…恐ろしいroomだ…」
と思いながら、他の人のeasyはまだ通ったままになっていたので、粗探しをしまくりました(悪い顔)。
具体的には、Challenge Phaseが始まってからすぐにその人たちのコードを急いで写経して、テストケースをいくつか投げてみたりしていました。
すると、手元で書いていたケースが通らないコードを発見!
前回の反省を活かして、ちゃんとChallengeは出来るようにしておいたので、早速Challenge!
challenge初めてにして成功した!
— satanic@C++ (@satanic0258) 2016年5月30日
見事Challengeに初成功しました!
そのおかげで順位が一気に上がり、ガッツポーズをしながらChallenge Phaseを終えました…
最終結果
スコア
問題 | 満点スコア | 獲得スコア | かかった時間 |
Easy | 300 | 0.00 | --:-- |
Medium | 500 | 0.00 | --:-- |
Hard | 900 | 0.00 | --:-- |
Challenge数 | Challenge成功数 |
1 | 1 |
計:50.00
レート
ここでレートなんですが…
1231(青)→1524(黄)
ファッ!? pic.twitter.com/WoG8AwIUsA
— satanic@C++ (@satanic0258) 2016年5月30日
…もうこのとき「えっ!?嘘でしょ!?」とか素で叫んでしまいました…。
まさか無→青→黄と2回でトントン遷移してしまうとは…。
恐らく、0完で終わってそのまま0点だった人が多かったんじゃないですかね…?
そのため順位上では黄色コーダーの人を何人か抜き、こういう結果になったんじゃないかと予想しています…。
あとがき
たとえレートが上がろうが解法全然わかんないんですけど…
— satanic@C++ (@satanic0258) 2016年5月30日
しかし、レートは確かに上がりましたが、これは自分が圧倒的成長した訳でもなく、運が良かっただけなのでなんだか複雑な心境に…
解けなかったことには変わりないので、まだまだ頑張る必要があるようですね…!
数字の結果に惑わされず、これからも精進していきたいと思います👍
繰り返し自乗法
概要
の値を効率的に解きます。
使える状況
「をで割ったあまり」が欲しいときに、があまりにも大きいとその計算だけで時間がかかってしまうことがあります。そのような時には、この繰り返し自乗法を用いることで素早く求めることが出来ます。
説明
の値を求めたいとき、愚直な方法として次のような手法を考えることが出来ます。
using ll = long long int; ll PowMod(ll N, ll P, ll M){ ll ans = 1; for(ll i=0; i<P; ++i){ ans *= N; ans %= M; } return ans; }
しかし、上記のような方法だと回ループしてしまうため、などの場合では非常に時間がかかってしまいます。
そこで使うのが、繰り返し自乗法です。
繰り返し自乗法は、
「を一回一回掛けてmodを取るのでは時間がかかるので、まとめて掛けてしまおう!」
という考えをもとにしたアルゴリズムです。
この「まとめて掛ける」というのがどういうことか、具体的にのときについて考えながら説明します。
以下、求める値を、とし、また、""の計算をした時にはで割った余りを求める操作も一緒に行っているものとします。
ボトムアップ(小さい値から大きい値へと計算していく)な考え方
先ほどの愚直な方法では、次のような計算をしていることになります。
確かに、回、つまり回分の計算をしていることがわかりますね。
ここで、上で計算しているように、
となっていることから、
とまとめてしまい、あとは、
と出来るので、計算回数は最初のを計算する回と、まとめた後の回となっているので、見事に半分にすることが出来ていますね。
これをさらに、
とすることによりを求め、同様にを求め、…と繰り返すことで、最終的には
とまで式を短くすることが出来ます。
このとき、次の回しか計算をしていないことが分かりますね。
- を求める()
- を求める()
- を求める()
- を求める()
- を求める()
このように、の自乗を繰り返し計算した結果を用いて計算を行っているので、「繰り返し自乗法」と言うんですね。
コード(C++)
using ll = long long int; ll RepeatSquaring(ll N, ll P, ll M){ if(P==0) return 1; if(P%2==0){ ll t = RepeatSquaring(N, P/2, M); return t*t % M; } return N * RepeatSquaring(N, P-1, M); }
コードの説明
トップダウンな考え方の節で示した式を、そのまま関数に落とし込んでいるだけです。
具体例
の値を求める。
今回は、愚直な方法(関数PowMod_Simple)と繰り返し自乗法(PowMod_RepeatSquaring)でどのくらい性能の差があるかを、
の2点について見てみます。
#include <iostream> #include <algorithm> #include <chrono> using ll = long long int; ll count_ps = 0; ll PowMod_Simple(ll N, ll P, ll M){ ll ans = 1; for(ll i=0; i<P; ++i){ ++count_ps; ans *= N; ans %= M; } return ans; } ll count_prs = 0; ll PowMod_RepeatSquaring(ll N, ll P, ll M){ ++count_prs; if(P==0) return 1; if(P%2==0){ ll t = PowMod_RepeatSquaring(N, P/2, M); return t*t % M; } return N * PowMod_RepeatSquaring(N, P-1, M); } int main(){ std::ios::sync_with_stdio(false); std::cin.tie(0); //愚直な方法----------------------------- std::cout << "愚直な方法\n"; auto startTime = std::chrono::system_clock::now(); //処理部------ std::cout << "2^1000000000 mod 1000000007 = " << PowMod_Simple(2, 1000000000, 1000000007) << "\n"; std::cout << "再帰回数\t:" << count_ps << "\n"; //------------ auto endTime = std::chrono::system_clock::now(); std::cout << "処理時間:" << std::chrono::duration_cast<std::chrono::nanoseconds>(endTime - startTime).count() << "ns\n"; //--------------------------------------- std::cout << "------\n"; //愚直な方法----------------------------- std::cout << "繰り返し自乗法\n"; startTime = std::chrono::system_clock::now(); //処理部------ std::cout << "2^1000000000 mod 1000000007 = " << PowMod_RepeatSquaring(2, 1000000000, 1000000007) << "\n"; std::cout << "再帰回数\t:" << count_prs << "\n"; //------------ endTime = std::chrono::system_clock::now(); std::cout << "処理時間:" << std::chrono::duration_cast<std::chrono::nanoseconds>(endTime - startTime).count() << "ns\n"; //--------------------------------------- return 0; }
実行結果(一例)
愚直な方法 2^1000000000 mod 1000000007 = 140625001 再帰回数 :1000000000 処理時間 :22322817871ns ------ 繰り返し自乗法 2^1000000000 mod 1000000007 = 140625001 再帰回数 :43 処理時間 :2709ns
この結果からも分かるように、再帰回数、処理時間ともに、文字通り桁違いで小さく計算することが出来ていますね。
ちなみに、処理時間の「ns」は「ナノ秒(ナノ)」を表しているため、
- 愚直な方法 :22.322817871秒
- 繰り返し自乗法 : 0.000002709秒
の時間がかかっていることを表しています。
備考
愚直な方法は計算量がであるのに対し、繰り返し自乗法ではにまで抑えられています。
SRM688(Div2)に参加しました!
はじめてのSRM
— satanic@C++ (@satanic0258) April 15, 2016
競プロのカレンダーを見ていると、2016/04/16 00:00(日本時間)からSRMがあるということだったので、TopCoder SRMに初参戦してみました。
初参戦ということでレートは1200から始まり、Div2の問題を解くみたいですね。
さっそくスタート!
Coding Phase
Easy(250)
「括弧の深さ…これどっかでやったことあるな…」と思い、迷わずいもす法で解くことを決めました。
#include <algorithm> #include <string> #include <vector> class ParenthesesDiv2Easy { public: int getDepth(std::string s){ int n = s.size(); std::vector<int> depth(n, 0); std::vector<int> cumSum(n, 0); for(int i=0; i<n; ++i){ if(s[i]=='('){ ++depth[i]; }else{ --depth[i]; } } cumSum[0]=depth[0]; for(int i=1; i<n; ++i){ cumSum[i]=cumSum[i-1]+depth[i]; } std::sort(cumSum.begin(), cumSum.end()); return cumSum[n-1]; } };
サンプルケースも結構すんなり通ったので、これで提出。
これにはあまり時間がかかりませんでした。
Medium(500)
「深さがマイナスになってたり最後の深さが0になってなかったりしたらおかしいよな…」
みたいなことをベースに色々やりました。
確か「)」を「(」にしたらそれ以降の深さがすべてされて、
逆に「(」を「)」にしたらそれ以降の深さがすべてされる、
ということを基本に考えて以下のように書いてみました。
#include <algorithm> #include <string> #include <vector> class ParenthesesDiv2Medium { public: std::vector<int> correct(std::string s){ int n = s.size(); std::vector<int> depth(n, 0); std::vector<int> cumSum(n, 0); for(int i=0; i<n; ++i){ if(s[i]=='('){ ++depth[i]; }else{ --depth[i]; } } cumSum[0]=depth[0]; for(int i=1; i<n; ++i){ cumSum[i]=cumSum[i-1]+depth[i]; } std::vector<int> ans; for(int i=0; i<n; ++i){ if(cumSum[i]<0){ ans.push_back(i); for(int j=i; j<n; ++j){ cumSum[j]+=2; } } } if(cumSum[n-1]!=0){ for(int i=n-2; i>=0; --i){ if(cumSum[i]<2 && cumSum[i+1]>=2){ ans.push_back(i+1); for(int j=i+1; j<n; ++j){ cumSum[j]-=2; } i=n; if(cumSum[n-1]==0){ break; } } } } return ans; } };
ちょいちょい調整しながらサンプルケースが全部通ったところで提出。
割と時間がかかってしまいましたが、そのままHardへと進んで行きました。
Hard(1000)
LとRで指定された範囲外の各括弧の数を記録しておいて…とかやった気がします(遠い目)。
何回やっても結局サンプルケースがすべて通ることなくタイムオーバー。
あとちょっと…なような気がしてましたがはたして本当にそうだったのかはわかりません。
Challenge Phase
(この前の5分休憩の時にトイレ行ってたらもうこのフェイズ始まってて焦ったのは秘密)
このChallenge PhaseというものがTopCoder特有(?)で、とても新鮮でしたね。
「他の人のコード見て判断って、こんなん本当に出来るのかな」とちょっと不安もありました。
ところが、
「あれ、なんでここで0代入してるんだ…。これ間違ってるんじゃないのか?」みたいなのを発見して、これはいきなりチャレンジ成功!?…とか思ってたんですが…
他の人のコードでこれなら通らない!ってやつ見つけたのにChallengeの方法が分からなくて終わってしまった(泣)
— satanic@C++ (@satanic0258) April 15, 2016
となってしまいました(白目)。
結局どうしたら良いのかもよく分からず…
自分の環境ではArenaがなんだか重かったので、もしかしたら表示バグでも起こしてたのかもしれませんね。
というわけで、次のSRMでの目標が早速出来てしまいました(笑)。
次のSRMは2016/04/24 01:00(日本時間)なので、そこでChallengeにリベンジしてみたいと思います。
最終結果
スコア
問題 | 満点スコア | 獲得スコア | かかった時間 |
Easy | 250 | 236.15 | 06:57 |
Medium | 500 | 284.99 | 29:55 |
Hard | 1000 | 0.00 | --:-- |
計:521.14
レート
1200(白)→1231(青)