kojingharangの日記

SRM 648 Div1 250 AB

13:30 |

• A,Bからなる長さ N の文字列 s を、s[i]='A', s[j]='B', i＜j な (i, j) が K 個になるように作れ。無理なら "" を返す。
• 2≦N≦50, 0≦K≦N(N-1)/2

• BBB があったとして、そこに A を入れる操作を考えると
• BBBA なら +0
• BBAB なら +1
• BABB なら +2
• ABBB なら +3
• と、割と自由度が高く数字を増やせることがわかる。
• B が M 文字あるところに A を 1 個入れると 0〜M が作れる。
• 一度置いた A は次に置く A にとっては無視できるのでなんか作りやすそうだ。
• B の個数 0〜N それぞれについて、K を貪欲に減らしていきつつどこにAを入れるかを決めていけばよさそう。
• それで無理なら "" を返す
• 全 N, K について検証してから submit (心の平静が訪れた)

• Accepted

class AB {
	public:
	void check(string s, int N, int K) {
		assert(N==s.size());
		REP(i, N) RANGE(j, i+1, N) if(s[i]=='A'&&s[j]=='B') K--;
		assert(K==0);
	}
	string createString(int N, int K) {
		REP(b, N+1) {
			int k = K;
			int a = N-b;
			map<int, int> bn;
			REP(i, a) {
				int take = min(k, b);
				bn[take]++;
				k-=take;
			}
			if(k==0) {
				string s;
				int ob=0;
				FOR(e, bn) {
					while(ob<e->first) {
						s+="B";
						ob++;
					}
					REP(j, e->second) s+="A";
				}
				assert(N==s.size());
				reverse(ALL(s));
				check(s, N, K);
				return s;
			}
		}
		return "";
	}
};

ツイートする