TopCoder SRM 652 Div2 参加記


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です。ただし、この手の問題でありがちな、自身の文字をカウントに含む、含まないは問題ごとに変わってくる(今回の問題では含む)ので、注意が必要です。

コード


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通りました。

コード


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で解けたら追記します。


コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です

このサイトはスパムを低減するために Akismet を使っています。コメントデータの処理方法の詳細はこちらをご覧ください