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

コード

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

コード

1000 : NoRightTurnDiv2

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