258.1

英語力は最大のプログラミング能力のようです。問題やたらと長いし...。

250

ローン残高と、月々の支払額と、残り期限が与えられるので、利率を求めよ、という問題。

利率をバイナリサーチ。利率が実際よりも少ないと支払いを行うと途中で値が負になるし、多いと支払いが終わらない。

500

3文字の任意の文字列を二つ選び、元の文字列中にその文字列が存在したらそれよりも一文字少ない特殊な文字列に置き換えることができるとするとき、変換結果の最短の文字数を答えよという問題。

元の文字列から3文字の部分文字列を選び、それらの中から重複を許して2個選ぶ。それらの出現位置の最初のものから順番に置換していって、置換した回数だけ文字数が減る。置換できる数が最多のものを返せば良い。

重複を許さないで2個選ぼうとすると、元の文字列の長さが3のときに2個選べなくてひどい目にあう。任意の3文字の文字列のペアについて計算するとすれば、この心配はなくなるけれど、文字数の6乗になるので、当然終了しない。(今回の問題は3^18になる。)

1000

100マスの双六がある。あるマスに止まると別のマスへ移動する、というマスがあり、それぞれのプレイヤーの現在位置が与えられる。このとき、各プレイヤーの勝利する確率を答えよ、という問題。

100x100の遷移行列を作成し、それに従ってプレイする。ある瞬間にプレイヤーがゴールする確率と、今までに他のプレイヤーがゴールしていない確率の積をプレイヤーごとに積み重ねていくことで、各プレイヤーの勝率が計算できる。ある瞬間にそのプレイヤーが勝利する確率は、各状態の確率に遷移行列をかけた結果、終了状態に到達している確率。この分をゴールするたびに引いて、normalizeすれば良い。毎回normalizeするのは面倒なので、ゴールしていない確率を覚えておけば良い。

問題自体は非常に簡単なのだけれど、サイコロを振る数が2個らしいので、どうやっても結果が合わなかった...。