274.1

500>>>1000のセット。というか1000は知っていれば一瞬。このセットの500はアルゴリズム的に目新しいことは特にないかも知れないけれど、プログラマ的にはいかに綺麗に(結果的に正確に)解けるかが重要な問題だと思う。やっておいて損はない。(プログラマ的には)

問題文が適切に理解できなかった場合、最初の実装に引きずられる形で変なコードが残ることが多い。そういうときはシステムテストに通りそうな気が全くしないし、実際に良く落ちる。

250

入力文字列のpermutationのうち、回文になるものの中で辞書順で先頭のものを答えよ、という問題。

多分50文字くらいの入力なので、next_permutationは使えないと思う。取り敢えず出てくるものの個数を数えて、奇数のものがいくつあるか調べておく。(このとき奇数のものを連結した文字列を作っておくと良い。)奇数のものが2つ以上あれば回文にはできない。奇数のものが一つならば、それを中心に回文を作る。後は大きい順に内側に並べていくだけ。

500

XとYのみからなる文字列がある。Xの数とYの数が等しくて、先頭から任意の文字数選んだ時に、Yの数がXの数を超えないような文字列をDyckと呼ぶ。ある文字列がDyckならば、隣接するDyckな部分文字列二つをスワップしても、全体としてDyckなままである。このようなスワップで誘導される文字列で同値類を作り、辞書順で先頭のものをその代表元とする。ある文字列が与えられた時にDyckならばその文字列が属する同値類の代表元を答えよ、という問題。

どうやって再帰的に実装できるか、がこの問題のキー。まず、全体をDyckな文字列に分割する。もし一つしかなければ、それはXで始まってYで終わるので、先頭と末尾を除いてもう一度この問題を解かせる。そうでなければ、それぞれについてこの問題を解かせ、ソートしてから結合すれば良い。

この手の問題はコーナーケースをケアしながら細かく実装していくことも可能だけれど、大抵そういう実装は細かいバグを埋め込むので、いかにすっきり書くかが重要になってくると思う。

1000

円形に数字が並んでいる。各ステップで、i番目の数字にi+1番目の数字(最後のは0番目)を足しこむという処理を同時に行う。このステップをK回行った後に、どういう風に数字が並んでいるか答えよ、という問題。足し算は100を法として行う。

Kは当然のごとく1Gとか書いてある。これは極めて単純な状態遷移なので、遷移行列を書いて行列乗算するだけ。