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