279.1

SRM

200

入力文字列のアルファベットについて、大文字と小文字が交互に並ぶように変換せよ、という問題。


大文字か小文字かの状態を覚えておいて、アルファベットならば適切な方に変換していくだけ。

575

N(<=15)桁の整数が与えられる。各桁に出現する数字の回数が等しい整数のうち、M(<=50)で割り切れるものの個数を答えよ、という問題。


先頭から順番に数字を決めていく。既に使った数字と、その時点でMで割った余りを覚えておいてDPするだけ。次に使う数字が決まれば、それまでの余りを10倍してその数字を足したものをMで割った余りが、新しいMで割った余りになる。


同じ数字を複数回含む整数の場合、重複カウントに注意する必要があるが、特定の数字を選択する場合には前の方から選ぶ、というような規則を追加しておけば問題ない。(多分実装する上でそれが一番楽。)

1000

整数列をスワップを用いてソートすることを考える。許可されるスワップ操作を、ソート後の配列における適切な位置にある数が増えるもの、とするとき、実行可能なスワップ回数の最大値を答えよ、という問題。


スワップの対象になり得る数字は、自分のソート後の位置を占有しているものか、自分が相手のソート後の位置を占有しているかのいずれか。これを推移的に用いて同値類分解すると、すべての可能なスワップ対象が求まり、この中の要素は適宜順番を選ぶことスワップ対象になり得る。(そうでないものとスワップする場合、ソート後の位置が適切なものの数が増えることは決してない。)なのでこの同値類の内部でのみ考える。


既に正しい位置にいるものはスワップの対象にならない。(自分と同じ数字以外を持ってくると必ず適切な位置のものは増加しないし、自分と同じ数字とのスワップで適切な位置のものが増加することは起こりえない。)なので他の要素間でのスワップのみ考える。


同値類の要素数をN個とし、要素の種類をMとする。このとき、N個の要素が適切な位置にいない。M=2のとき、要素をAとBの二つとすると、スワップはAとBとの間でしか起こらず、また、これは双方とも適切な位置にくることを保証している。なので、N/2回だけスワップができる。M>=3のとき、一番出現回数の多い要素Aを適切な位置にスワップすることを考える。相手となる要素Bの個数がM個よりも小さい時、Aが占有している場所はM個あるので、少なくとも1個はBの適切な場所でないものが存在する。なのでBが適切な位置に来ないようなスワップを行うことが可能である。(Bの個数がM個で、しかもAの占有している位置がすべてBにとって適切な位置であると仮定すると、これはM>=3の仮定に反することになる。)これを繰り返すとN-M回のスワップができ、M種類の要素がそれぞれ一個ずつ残る。後は一個ずつあわせるようにスワップしていくことになりM-1回、全部でN-1回のスワップが行える。適切な位置のものは必ず1個以上増えるので、N個の要素のスワップとして最大のものはN-1以下(最後は必ず2個増える)であることが保障されるので、これより良い方法はないことが分かる。後は各同値類についての合計を計算すればおしまい。


スワップする要素を適切に選べば、適切な位置のものが一つだけ増えるようなものを優先的に行うだけのgreedyでうまくいくらしい。(本当にうまくいくかどうかは知らない。)グラフ系の問題かと思って確実に解ける方法がないか探したものの、結局greedyな問題だった。