Hatena::Grouptopcoder

hotpepsiの練習帳

2017-04-06

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

ゲスト



トラックバック - http://topcoder.g.hatena.ne.jp/firewood/20170406