160.1

昨日の続き。

1000

文字列のPermutationを考える。ある文字列のPermutationを元の文字列からの写像と考えた時に、その写像を適用して元に戻るまでの回数が最大となるような文字列を答えよという問題。ただし元の文字列はABCDEF...uvwxyzなる52文字の文字列のうちの頭のN文字である。

やるべきことは非常に簡単な問題で、入力Nに対して、整数配列を答えればおおむね終了。返すべき整数配列は、合計がNでそれらの最小公倍数を最大化するもの。メモ付き全探索できますか、という問題に他ならない。求めた配列の要素を小さい順にソートして、元の文字列をその文字数ずつ切り取り、1文字ずつローテーションしたものを返せば良い。

で、メモをハッシュテーブルを使って実装したところ、Javaのオーバーロードにはまった。equalsメソッドはObject型を引数にとるものの方をオーバーライドしないと、ハッシュテーブルのキーの比較メソッドとしては不適切。1.5でGenerics入ったからオーバーロードしている側でいいのかと思ったけれど、そのためには何かしらの指定をどこかでしないとダメなのかも。(本質的に無理なのかも。)