SRM642参加しました。
簡易解説と一緒にコードを貼っていきます。
今回は珍しく午前中の回でしたが、終了時間と同時に用事が入っていたので、またしても慌ただしい参加回でした。
SRM深夜だと辛いけど、だからといって午前中ならいいというわけでは無い
— ik-fib (@ik11235) December 17, 2014
今回はmiddleで詰まってしまい、なんとかSAMPLEが通るコードは書けたものの、Systemtestで落ちました。
終了後、Systemtestが通ってた他の人のコードを読んだら、すぐに解法が分かったのですが、本番中にその解法が全く浮かばず、かなり重いコードを書いてしまっていました。
そのせいで復帰後初めてレートが落ちる結果に…(845->805)
250 : ForgetfulAddition
問題概要
1-9までの数字のみの文字列expressionが与えられるので、この文字列を任意の一で2つに分割する。分割した文字列をそれぞれの数値として扱い、2つの数字を足した際、最小となる合計値を出力する。
解法
文字列が分割可能な地点で全て分割、加算をしてその値が一番小さい値を返せばOKです。
コード
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| inline int toInt(std::string s) {int v; std::istringstream sin(s);sin>>v;return v;} | |
| class ForgetfulAddition { | |
| public: | |
| int minNumber(string expression) { | |
| int ans=9999999; | |
| for(int i=1;i<expression.size();i++) | |
| { | |
| string a=expression.substr(0,i); | |
| string b=expression.substr(i); | |
| // cerr<<a<<"+"<<b<<endl; | |
| ans=min(ans,toInt(a)+toInt(b)); | |
| } | |
| return ans; | |
| } | |
| }; |
500 : LightSwitchingPuzzle
問題概要
I個のライトのオンオフが文字列で与えられる。(‘Y’がON,’N’がOFF)
ライトのスイッチはx番目のスイッチを押すと、x,2x,3x…のライトのON,OFFが反転する。
全てのライトを消すためには最低何個のスイッチを押す必要があるかを返す。
解法
もし1個目のライトがついていた場合、それを消すことができるのは1個目のスイッチのみです。(2個目以降は,2x(x>1)のため、x以上のライトしか消せない)
そのため、1番目のライトがついていた場合、必ず1番目のスイッチを押します。
そして、1*xのライト(この場合全てのライト)が反転して1番目のライトはOFFになります。
続いて、2番目以降のライトについて同様に考えます。
i番目のライトが付いている時、i番目のボタンは必ず押す必要があるので、そのボタンを押した回数をカウントした上で、xiのライトを反転する動作をI個目のライトまで続けます。
最終的にスイッチを押した回数が必要な回数になります。
コード
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| class LightSwitchingPuzzle { | |
| public: | |
| int minFlips(string state) { | |
| int ans=0; | |
| for(int i=0;i<state.size();i++) | |
| { | |
| if(state[i]=='Y') | |
| { | |
| ans++; | |
| for(int j=i;j<state.size();j+=(i+1)) | |
| { | |
| if(state[j]=='N') | |
| state[j]='Y'; | |
| else | |
| state[j]='N'; | |
| } | |
| } | |
| } | |
| return ans; | |
| } | |
| }; |
1000 : TallShoes
問題概要
0からN-1番までの番号がふられた街と、街と街をつなぐ道が存在する。
各道には、高さが定められており、この高さ以下でないと通れない。0番目の街からN-1番目の街へ移動できる最大の高さを求める。
ただし、k^2ドル使うことで高さの制限をKだけ上げる事ができる。この増加に使用できるコストの最大はBである。
解法
通った辺の高さ制限を全て保存しておき、そのなかの最小値の最大を基準としてダイクストラ法を行い、N-1まで到達するまで繰り返す。
その後、その辺の集合で一番小さい辺から手持ちのコストから制限を増やせるだけ増やしていくという解法は思い浮かびましたが、通してないため正しい解法かは分かっていません。
コード
まだ解けていないので、解け次第追加します。