SRM初め、SRM644参加しました。…が不具合でコンテスト中に中止、今回のコンテストはunratedになりました。
ただ、一応プラグインを利用していたため、手元に一部の問題文とサンプルはあり、サンプルテストはできたので、
(Systemtest通るかは不明ですが)、簡易解説と一緒にコードを貼っていきます。
2015年の初SRMは、21時という日本人的には好条件の開始時間でしたが、まさかのunratedでした…
今回は、結構いい感じに進めてた感じがあった(systemtestに通るとは言っていない)ので、ちょっと残念です。あまりこういったunratedというかtopcoderの中止の場合の取り扱いに詳しくないのですが、このSRM644はどうなるのでしょうか。もし後日同番号に違うセットが割り当てられるのか、SRM645になるのかとか、このセットのpracticeルームが開かれるのかとかどうなんでしょうか。(問題に不備なら別として、システムの問題であればpracticeは開かれると思いますが…)
些細なことですが、なぜ250の問題お好み焼だったんだろう…実際に行っていたらしいです。(writerのtozangezanさんのブログ記事)
もし、後日practiceが開かれたらこの解法とコードは、検証して上げ直します。
後日確認したら、practice開かれてました。250と500はシステムテストも通ってました。
250 : OkonomiyakiShop
問題概要
お好み焼きのサイズの配列、Osizeが与えられる。
サイズの差がK以下のお好み焼きの組み合わせが何通りあるか返す。
解法
この問題は、Osizeの最大要素数が50なので、全探索で全ての組み合わせを試して、差がK以下組み合わせの数を数えるだけでOKです。
ただし全探索する際には、{Osize[0] – Osize[0]}のように同じお好み焼きで比較しないことや,{Osize[0] – Osize[1]},{Osize[1] – Osize[0]}のように同じ要素同士の組み合せを反転したものは重複して数えないので、その箇所だけ注意が必要です。
コード
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 OkonomiyakiShop { | |
| public: | |
| int count(vector<int> osize, int K) { | |
| int cnt=0; | |
| for (int i=0; i<osize.size(); i++) { | |
| for (int j=i+1; j<osize.size(); j++) | |
| { | |
| if(abs(osize[i]-osize[j])<=K) | |
| cnt++; | |
| } | |
| } | |
| return cnt; | |
| } | |
| }; |
500 : LostCharacter
問題概要
小文字の文字列の集合、strが与えられる。
ただし、この集合の文字列には劣化して読めない文字(?で表す)が存在する。
この?に任意の文字を入れた時に、その文字列が辞書順で最小の順序のインデックスを全ての文字列で探索し、その値の配列を返す。
解法
?がない場合は、単純にソートして辞書順のインデックスの配列を返すだけです。
?がある場合は、その文字列がなり得る最小のインデックスを返す必要があります。
全ての文字列を順番に見ていき、その対象の文字列の?を全て’a'(辞書順最小)に置換し、それ以外の文字列の?を全て’z’にした上で、ソートする。そしてソート後の対象の文字列のインデックスが、その文字列がとり得る最小のインデックスなのでそれを保存して、これを全ての文字列に対して繰り返します。すると、全ての文字列の最小のインデックスを得ることができるので、これを返せば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
| class LostCharacter { | |
| public: | |
| vector<int> getmins(vector<string> str) { | |
| vector<int> ans(str.size()); | |
| for(int i=0;i<str.size();i++) | |
| { | |
| vector<string> tmp=str; | |
| string target; | |
| for(int j=0;j<tmp.size();j++) | |
| { | |
| for(int k=0;k<tmp[j].size();k++) | |
| if(tmp[j][k]=='?') | |
| { | |
| if(i==j) | |
| tmp[j][k]='a'; | |
| else | |
| tmp[j][k]='z'; | |
| } | |
| } | |
| target=tmp[i]; | |
| sort(tmp.begin(),tmp.end()); | |
| ans[i]=find(tmp.begin(),tmp.end(), target)-tmp.begin(); | |
| } | |
| return ans; | |
| } | |
| }; |
1000 : TreeCutting
500を解いている最中にコンテストが中止になったので、問題文すら見れませんでした。後日、practiceで解けたら追記します。