SRM 650 Div2
結果
oox 1088 -> 1081
Easyの計算量の見積もりを間違って全探索でいけないと思っておかしなことをしてしまった．久しぶりにEasyとMedでハマってしまった．
[Easy: TaroJiroDividing ]
問題
dividing gameをプレイする．dividing gameとは与えられた正の数Xを次の手順にしたがって紙に書いていく．始めにXを書く．次にXが奇数ならゲームを終了して，偶数ならばXを2で割って繰り返す．
e.g. X = 12 ならば紙には 12, 6, 3 と書かれる．
TaroとJiroにはそれぞれ1以上1,000,000,000以下の整数AとBが与えられる．それぞれがdividing gameを行った時に両方の紙に共通に書かれている整数の数を答えよ．
解法
dividing gameを最大で何回行うのかを考えます．一回の繰り返しで1/2倍になるので繰り返す回数をNと置くと，
から Nは30回を越すことはありません．したがって解放は，プレイヤーが実際にゲームを行って両方の紙に含まれる数を数えるシミュレーションとなります．
ソースコード
class TaroJiroDividing { public: int getNumber(int A, int B) { set<int> check; while (true) { check.insert(A); if (A % 2 == 0) A = A / 2; else break; } int ans = 0; while (true) { if (check.count(B) == 1) ++ans; if (B % 2 == 0) B = B / 2; else break; } return ans; } };
[Medium: TaroFillingAStringDiv2 ]
問題
'A'，'B'，'?'からなる文字列Sが与えられる．文字列Sのuglinessとは連続する'A'または'B'のペアの数．
e.g. S = "ABABAABBB" なら"AA"のペアの数が1，"BB"のペアの数が3でSのuglinessは4となる．
Taroは文字列内のすべての'?'を'A'または'B'に変更する．変更後にuglinessが最小となる文字列のuglinessを求める．
解法
文字列Sのuglinessをug(S)と書きます．
S = "A?B" の場合は ug("AAB") = 1, ug("ABB") = 1 となり'?'をどの文字にしても変わりません．
S = "A??B"の場合は ug("AAAB") = 2, ug("AABB") = 2, ug("ABAB") = 0, ug("ABBA") = 1 となり "ABAB"と隣と異なる文字にした場合が小さくなります．
同様に，"A?A", "A?B"のそれぞれのパターン（対称性を考慮して）に対して，'?'が偶数個と奇数個入っている文字列のuglinessを調べると左の文字と異なるように'?'を変更することが最善だと分かります．
したがって，左の文字と異なるように左から'?'を変更していくという貪欲法で問題を解きます．しかし，"??A"のように一番左が'?'の場合には変更ができないので，同様に右の文字と異なるように右から'?'を変更していきます．
しかし，これに対しても"???"のような場合には変更されないのでこの場合は一番左を'A'として初めの貪欲法を使います．
（もっとスマートな方法がありそう・・・）
ソースコード
class TaroFillingAStringDiv2 { public: int getNumber(string S) { const int n = S.size(); S += "-"; // 左の文字とことなるように左から'?'を変更する for (int i = 0; i < n; ++i) { if (S[i] == '?') { if (i != 0 && S[i - 1] != '?') { if (S[i - 1] == 'A') S[i] = 'B'; else S[i] = 'A'; } } } // 右の文字とことなるように右から'?'を変更する for (int i = n - 1; i >= 0; --i) { if (S[i] == '?') { if (i != n - 1 && S[i + 1] != '?') { if (S[i + 1] == 'A') S[i] = 'B'; else S[i] = 'A'; } } } // "???"の場合．一番左の文字を'A'に変更して， // 左の文字とことなるように左から'?'を変更する if (S[0] == '?') S[0] = 'A'; for (int i = 0; i < n; ++i) { if (S[i] == '?') { if (i != 0 && S[i - 1] != '?') { if (S[i - 1] == 'A') S[i] = 'B'; else S[i] = 'A'; } } } int ans = 0, idx = 0; while (idx < n) { int len = idx + 1; while (S[idx] == S[len]) ++len; ans += max(0, len - idx - 1); idx = len; } return ans; } };
