SRM351

1548->1516

また，青に戻りそう．今回のセットはわりと重い部類に入って，得点のある人の方が少なかった．

250点 金銀銅の3種のコインがあって，金貨1枚を両替すると銀貨9枚になり，銀貨11枚で金貨1枚になる．
同様な関係が銀貨と銅貨においてもなりたつ．
今所有している金，銀，銅貨から必要とされている金，銀，銅貨の枚数を得るために必要な両替の回数はいくつか答えよ．

価値の高い硬貨から必要枚数を充足するようにしていけばよく，その方針だとバグなしでかけるのだが，自分は金銀銅の差の正負から8通り場合分けして，力任せに解こうとしたのだが案の定バグをいれて，撃沈．

500点 A,B,Cからなる文字列が与えられた時，たとえば"AAABBBCCC"みたいな文字列．swapを繰り返すことによりつくられる文字列の集合の中で"AABABCBCC"のようにA,B,Cいずれも3回連続しないような文字列からなる集合を考える．この集合の文字列ともとの文字列とのハミング距離の最小をだせ．

解法をまだ理解していない．

5/30 追記：結局swapを繰り返すことにより得られる文字列の集合というのはもとの文字列とA,B,Cの数が同じものの全体なので，前二つの文字と残りのA,B,Cの数についてメモ化しながら全探索してやると4*4*50*50*50 = 2000万ぐらいなので十分間に合う．