221.1

ちゃんと真面目に考えてから実装しましょうね、という回。余りに手抜きを試してしまった...。

250

与えられた二つの整数A,BからA*k%B=1なるkを求めよ、という問題。

Bが小さいのでBまでループ回すだけ。実際にはもっとごちゃごちゃした問題だけれど、これさえやれば多分問題ないはず。

500

ある数を二つの桁のスワップや、特定の桁の+1および-1操作を行って目的の数にするための最小ステップ数を答えよという問題。

BFSするだけ、と言いたいところだけれど、速度的に自信が持てなかったので各種greedyを試してみた。結局スワップすることで一番得するスワップをやるというアプローチはダメ。スワップは得する状況でしか起こらないので、可能なスワップを全部試したうえで、可能なのがない時はハミング距離、みたいなのをやって、可能なスワップがなくなるまでBFSという感じがいいんだと思う。単純BFSだと100Mステップくらい計算しないといけない危険があるので。(実行時間より前にメモリが足りなくなる。)

整理すると、スワップは高々桁数-1回しかやらないはずなので、どこをスワップするか全探索しましょう、ということだと思う。無駄なスワップを計算しててもBFSするだけなのですぐに停止すると思う。

900

xとyからなる文字列を8連続のxや6連続のyを削除したり、xyをyyyyyxに置き換えたりという操作で、変換可能かどうかで同値類分解した結果の代表元を答えよ、という問題。

xyをyyyyyxに変換する操作を使って、xを右に寄せたときに、x%8とy%6の値で同値類分解可能。(高々48通りしか答えはないということ。)後はアルファベット順に小さいものから全部計算していって、どの同値類に入るかを計算するだけ。yが5倍になっていくのでint溢れに注意が必要。文字列ベースでやっていると重かった。