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

コード

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

Leave a Comment


NOTE - You can use these HTML tags and attributes:
<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>