SRM652参加しました。…ただ、新生活でちょうど引っ越しタイミングと重なったため、微妙な参加に…
今回のSRMは開催日の朝に深夜バスで到着→管理会社から新居の鍵を受け取る→SRM参加というよくわからないスケジュールでSRMに参加してました…が、結構慌ただしかったのやら疲れてたのやらで、失敗してしまいました。引越し日にもSRMに参加する競プロ趣味プログラマーの鏡
(rating: 995 -> 961)
- 250 : AC
- 500 : no submit
- 1000 : no submit
- Challenge WA : 1
250 : SquareScoresDiv2
文字列Sが与えられる。文字列S内から同一の文字だけが連続する部分文字列(1文字以上)を何種類存在するかをカウントする。また、同じ文字列でも開始箇所が違う場合、違う文字列として扱う。
解法
この問題では、同じ文字が連続する箇所の部分文字列長の階乗の合計が答えとなります。
例えば、”aaabbc”という文字列ではまず最初の”aaa”の部分で、”aaa”1つ、”aa”2つ、”a”3つが作成可能、すなわち6個の部分文字列が作成可能です。同じく”bb”では”bb”1個,”b”2個、”c”1個でその合計である10が答えです。
コード
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 ValueOfString { | |
| public: | |
| int findValue(string s) { | |
| int sum=0; | |
| for(int i=0;i<s.size();i++) | |
| { | |
| int cnt=0; | |
| for(int j=0;j<s.size();j++) | |
| { | |
| if(s[i]>=s[j]) | |
| cnt++; | |
| } | |
| sum+=(s[i]-'a'+1)*cnt; | |
| } | |
| return sum; | |
| } | |
| }; |
500 : OneEntrance
問題概要
N個の部屋と、その部屋をつなぐ無向の経路が複数与えれれる。
この部屋群の入り口はsであり、この部屋群の全てに荷物を運びたい。ただし1度荷物をおいた部屋は通れないため、奥の部屋から順番に置く必要がある。この時、荷物の置き方の順序は何通りあるかを答える。
解法
部屋の数は少ない(N<=10)ため、全ての順序について考えても10!(=3628800)通りしか無いため、全ての順序を作成したうえで、その順列通りに配置できるかを調べれば出来そうというところまでは行ったのですが、本番中に実装できませんでした。
本番中に見てみたら、その方針で行けそうだったため、ちゃんと解いておきたいところです。
1000 : TreeCutting
Mediumで詰まってしまい、hardまで進めませんでした。後日practiceで解けたら追記します。