SRM652参加しました。
今日は時間的には普段よりは参加しやすい時間でしたが、個人的に体調が不調気味だったのもあり、結構失敗してしましました。(たぶんレートも落ちた)
(rating: 1015 -> 995)
- 250 : AC
- 500 : no submit
- 1000 : no submit
- Challenge AC : 1
- Challenge WA : 1
250 : ValueOfString
問題概要
文字列Sが与えられる。文字列の各文字を以下のルールで点数化した時、文字列の文字の合計点数を返す。
- 文字のアルファベット位置(‘a’=1,…’x’=26)*文字列中にその文字以下の文字が出現する回数
解法
この問題は、文字の計算を単純に行うだけかつ、最大文字列長も高々50なので、貪欲に全ての文字について計算すれば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 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 : ThePermutationGameDiv2
問題概要
1からNまでの数値を使い、任意の順列pを作成する。
f(1)=p[1],f(x)=p[f(x-1)]となる関数fを用いて、
作成することが可能な全ての順列において f(x)=1になる最小のxを求める。
解法
単純に全ての順列を作成し、探索してしまうと35!(≒10^40)通りあるため、たとえ1つの順列に対してO(1)でf(x)が求められても間に合いません。
ただし、この順列は必ずどこかでループします。さらにそのループする周期は1〜Nの間、かつ全ての周期の順列が存在します。
そのため、1~Nの最小公倍数が答えとなります。
ただ私は、最小公倍数を求める実装でミスをしてしまい、計算時間が爆発するコードを書いていました。そのバグを時間内に解ききれず、結局submitできませんでした。
以下のコードは終了後に修正が終わり、おそらくあっているはずですがまだpracticeに投げ直して無いので、確証はありません。practiceでsystem test通りました。
コード
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 ThePermutationGameDiv2 { | |
| public: | |
| long long int lcm(long long int a,long long int b) | |
| { | |
| if (b==0 || a == 0 ) | |
| return 0; | |
| return ((a / gcd(a, b)) * b); | |
| } | |
| long long int gcd(long long int a,long long int b) | |
| { | |
| return b==0?a:gcd(b, a%b); | |
| } | |
| long long findMin(int N) { | |
| long long ans=1; | |
| for(int i=2;i<=N;i++) | |
| { | |
| ans=lcm(ans,i); | |
| } | |
| return ans; | |
| } | |
| }; |
1000 : NoRightTurnDiv2
Mediumで詰まって問題を読めていないので、後日practiceで解けたら追記します。