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;
    }
};ValueOfString.cpp

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;
  }
};ThePermutationGameDiv2.cpp

1000 : NoRightTurnDiv2

Mediumで詰まって問題を読めていないので、後日practiceで解けたら追記します。