178.1

350

^^をエスケープシーケンスと考えて、文字列を処理した結果、最終的に得られる文字列をint配列として答えよという問題。

書いてある通りに実装するだけ。特に間違えるポイントもない。

500

ランダム遷移のオートマトンが、長さN以下の入力が等確率で与えられた時に、入力を受理する確率を答えよという問題。

遷移状況を持っていれば、K文字の時に各ステートにある確率から、K+1文字の時にどう遷移するかが分かるので、それを逐次計算すれば良い。また、確率の重みは文字数が増えるごとに、文字の種類だけ増える。

1000

画面を二色に塗る時に、塗っていい回数から最小の誤り数を求めよという問題。同じ場所を二度塗ってはいけない。塗る方向は横方向のみ。

各行について、K回塗った時にNマス違っている、というのを計算する。後は全部でM色あれば、C行についてDマス違っている、というDPをやるだけ。2パターンのDPが必要で、おそらく前者の方が実装が面倒。