TopCoderOpen 2021 Round4 : Easy MagicTrickWithCards

Easyをそこそこの時間で解いたらレートが上がった。
https://community.topcoder.com/stat?c=problem_statement&pm=17104&rd=18770

問題

52枚の表を向いたカードの山がある。各カードは異なる文字が書かれている。
ここに以下の操作を行う。

• おおよそ3等分し、3つの山に分ける。
• 真ん中の山のX枚目のカードの文字を覚える。
• 真ん中をひっくり返す。順番も表裏も逆になる。
• 3つの山を、また1つにまとめる。
• おおよそ半分に分け、おおよそリフルシャッフルする
• 適当な箇所で1回カットする

この処理の後、山のカードの表裏の様子が与えられる。
2番目の手順で覚えたカードは、山の何枚目に来ているか。

解法

もし「おおよそ」がない場合、カットの前の時点では、表裏交互が1/3、表のみのカードが1/3、また表裏交互が1/3の順で並ぶ。
また、X枚目のカードは、後者の表裏交互の塊の(52/3-X)枚目の裏面のカードとなる。

実際にはこの後カットが行われるが、表のみのカードが続く場所は容易に確定できるので、そのあと(52/3-X)枚目の裏面のカードを答えよう。

class MagicTrickWithCards {
	public:
	vector <int> findTheirCard(vector <string> queryCards, vector <int> queryX) {
		vector<int> R;
		int i,x,y;
		FOR(i,queryCards.size()) {
			string S=queryCards[i];
			int num=0;
			FORR(c,S) {
				if(c!='-') c='o';
				else num++;
			}
			int ma[52]={};
			int be=0;
			FOR(x,52) {
				FOR(y,52) if(S[(x+y)%52]=='-') break;
				ma[x]=y;
				if(ma[x]>ma[be]) be=x;
			}
			int lef=num-queryX[i];
			FOR(x,52) {
				if(S[(x+be)%52]=='-') {
					lef--;
					if(lef==0) {
						R.push_back((x+be)%52);
						break;
					}
				}
			}
			assert(R.size()==i+1);
		}
		return R;
	}
}

まとめ

TCOのRound4というかなり重要な場面で、こういう問題出してくるのか…。