SRM448 DIV2

英語の関係でリアルタイムの参加は無理、くやしいのうｗ

250pt

BlackJackにおけるトランプの数字と種類が"2C","AD","TH"という情報で与えられ、
その与えられた全てのカードの数字の和を求める問題。
普通にループ回して値を当てて足すだけ。

500pt

1..nまで順に数字が書かれたmainデッキ（一番上が1）をm回シャッフルしたときの一番上のカードの番号を求める問題。
シャッフル方法は、mainデッキの一番上から1枚ずつ、左、右、左…と2つのデッキに分ける。
配り終わったら、左デッキの一番上から1枚ずつmainデッキに戻し、戻し終わったら右デッキも同様に戻す。
5枚、2回のシャッフルだと、
初期状態　 1,2,3,4,5
1回目　　　2,4,1,3,5
2回目　　　4,3,2,1,5
answer: 4
この様にシャッフルされる。
n,mがともに最大値が100万なので、普通にシミュレーションするとO(n*m)になるから遅い。
初期状態を分けるとき、左デッキが奇数、右デッキが偶数の集合になる。
右デッキに注目すると、2回目は奇数を除いてnを超えない範囲で2^(2*a) {a>0}の集合になっている。
右デッキの偶数の集合は　2^(シャッフル回数目 * a) {a>0}　（たぶんこんな感じ）
mainデッキの一番上のカードは必ず右デッキの1枚目になる。
ここから先が曖昧、ぶっちゃけよくわからない。親切な方、是非とも教えてください。
値がnを超えたとき、次に来る偶数に対応する値が循環して回ってくるっぽいので、
nが奇数のときはn、nが偶数のときはn+1で割った余りが対応する値になる。
このアルゴリズムならO(m)で求めることが出来る。


エレガントに書かれた方のコードを拝見して、自分なりに解釈しました。
とてもこのアルゴリズムは思い付かないなぁ。数学の力を感じます。

1000pt

むーりｗ