hotpepsiの練習帳

SRM 710

23:51

Div1 Easy (300) ReverseMancala

問題

• マンカラはコマを穴から穴へと動かして遊ぶゲームである。ここではコマを石、穴をスロットとする
• N個のスロットがあり、円環状に並んでいる
• ゲームは1ターンずつ進行する
• 操作Aまたは操作Bのいずれかの操作が可能である
• 操作Aは、まずひとつ以上の石が入ったスロットを選び、石を全て手に移す
• 次に、時計回りで隣にあるスロットに、石をひとつずつ置いていく
• 石がなくなったら終了
• 操作Bは、まず石が一つ以上存在するスロットを選ぶ
• 次に、反時計回りで、石をひとつずつ取っていく
• スロットに石が入っていなかったら、そこに手持ちの石をすべて置いて終了
• 状態startとtargetが与えられる
• startからtargetにするための手順を求める

方針

• 何となく均等にできそう
• いろいろやってみるが終了
• (終了後)
• ある場所X以外からAの操作をひたすら実行すると、X一箇所に集めることができる
• Bの操作はAの逆である
• targetからXに集める操作を求めておいて、逆順にBを実行するとXからtargetにできる
• startからXに集める操作とくっつけて完成
• 逆順にするときはindexの値が最後に置いた場所になるので、そこを何とかする
• https://github.com/firewood/topcoder/blob/master/srm_7xx/srm_710/ReverseMancala.cpp

結果

--- 0pt 42nd/226 rating 1683 -> 1649 (-34)

部屋で誰も提出できなかった珍しい回。連続プラス点が7回で終わってしまった。

マンカラは実在のゲームだったらしい。

https://togetter.com/li/1088982